Lesson 4 · Problem-solving methods

Bit Manipulation

Bit manipulation applies logical operations to an integer's binary representation. Fixed-width machine integers support compact flags and masks, while arbitrary-precision integers may require work across several machine words.

Bitwise Operators

The core operators are AND (&), OR (|), XOR (^), NOT (~), Left Shift (<<), and Right Shift (>>).

AND masks bits and OR sets bits. For nonnegative values without overflow, shifting left by k multiplies by 2^k and shifting right divides by 2^k using integer truncation. Signed shifts and overflow are language-specific.

1 << n represents 2^n when the shift fits
x & 1 checks if x is odd
Signed shifts require language-specific care

The XOR Trick

XOR returns 1 if the bits are different, and 0 if they are the same. This gives it two vital properties: a number XORed with itself is 0 (A ^ A = 0), and a number XORed with 0 is itself (A ^ 0 = A).

This is heavily used in algorithmic problems to find a unique number in an array where every other number appears exactly twice.

A ^ A = 0
A ^ 0 = A
Order of XOR operations doesn't matter

Key reference

Terms, operations, and practical uses

Core vocabulary

BitmaskAn integer used to represent a set of boolean flags or items, where each bit corresponds to one item's presence (1) or absence (0).
Bitwise XOR (^)An operation that outputs 1 only if the two input bits are different. Useful for toggling bits.
Shift (<<, >>)Moving bits to the left (multiplying by powers of 2) or right (dividing by powers of 2).

Common operations

Set a bitUse OR: mask | (1 << i) sets the i-th bit to 1.
Clear a bitUse AND with NOT: mask & ~(1 << i) sets the i-th bit to 0.
Check a bitUse AND: (mask & (1 << i)) != 0 checks if the i-th bit is 1.

Advanced tricks

Isolate Lowest Set BitThe expression x & -x returns the value of the lowest set bit in x.
Clear Lowest Set BitThe expression x & (x - 1) turns off the lowest set bit in x.
Check Power of 2A number is a power of 2 if x > 0 and (x & (x - 1)) == 0.

Code example

Check if a number is a power of 2

def is_power_of_two(n):
    if n <= 0:
        return False
    return (n & (n - 1)) == 0
print(is_power_of_two(8))

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

static boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

Inputn = 8 (Binary: 1000)

OutputTrue

Example

Run the example step by step

Output

Bitmasks as Sets

An integer can be viewed as a compact array of booleans. For example, the number 5 (binary 101) can represent a set containing items 0 and 2.

Within one fixed-width word, OR, AND, and membership tests take constant time. Wider arbitrary-precision masks require work proportional to the number of machine words they occupy.

Sets up to 32/64 items fit one common word
Union is OR and intersection is AND
Membership uses (mask & (1 << i)) != 0

Common Tricks

x & (x - 1) is a famous trick that clears the lowest set bit of x. If doing this once makes x zero, then x was a power of 2.

Brian Kernighan's algorithm uses this trick to count the number of set bits (Hamming weight) in a number by repeatedly clearing the lowest bit until the number is 0.

x & (x-1) clears lowest set bit
Check power of 2 in O(1)
Count set bits efficiently