Bitwise Basics

Description

Every int is 32 bits, and some questions are easiest to answer at that level. Which number in this list appears only once? Is this number a power of two? Which of these 20 features are switched on? Each has an obvious answer with a hash set or a loop over values. Each also has a shorter answer that works on the bits directly, in O(1) extra space. This skill covers the core operations, XOR cancellation, bitmasks as sets, and the traps around negative numbers and shifts.

We'll go from simple to more technical:

1. The pattern: AND, OR, XOR, shifts, and the tricks built from them (x & (x - 1), x & -x).
2. A second flavor: an int as a set of up to 32 items.
3. Where bits show up in production (flags, permissions, hashing, compact sets).
4. What breaks it: negative numbers, shift distances, precedence, edge values.

The approach

int singleNumber(int[] nums) {          // every value appears twice except one
    int result = 0;
    for (int num : nums) {
        result ^= num;                  // x ^ x == 0 and x ^ 0 == x
    }
    return result;
}

def single_number(nums: list[int]) -> int:   # every value appears twice except one
    result = 0
    for num in nums:
        result ^= num                          # x ^ x == 0 and x ^ 0 == x
    return result

XOR is commutative and associative, so the order doesn't matter: every pair cancels to 0 wherever its two copies sit, and only the lone value survives. The same cancellation finds the missing number in 0..n (XOR all indices with all values) and swaps two variables without a temporary. It does not cancel a value that appears three times (x ^ x ^ x == x); that needs per-bit counting (below).

The other identities worth knowing cold:

x & (x - 1)       // clears the lowest set bit:   12 (1100) -> 8 (1000)
x & -x            // keeps only the lowest set bit: 12 (1100) -> 4 (0100)
n > 0 && (n & (n - 1)) == 0      // n is a power of two (exactly one bit set)
(x >> i) & 1      // reads bit i

x & (x - 1)                     # clears the lowest set bit:    12 (1100) -> 8 (1000)
x & -x                          # keeps only the lowest set bit: 12 (1100) -> 4 (0100)
n > 0 and (n & (n - 1)) == 0    # n is a power of two (exactly one bit set)
(x >> i) & 1                    # reads bit i

x & (x - 1) counts set bits in one step per 1 bit (Brian Kernighan's method). x & -x works because -x is ~x + 1 in two's complement: every bit above the lowest 1 is flipped, so only that bit survives the AND. With two lone values a and b among pairs, XOR-ing everything gives a ^ b; any 1 bit in it (say x & -x) is a bit where a and b differ, so splitting the numbers on that bit separates a from b.

n & 1 and n >> 1 equal n % 2 and n / 2 only for non-negative n: -7 % 2 is -1 (so n % 2 == 1 misses negative odd numbers) while -7 & 1 is 1, and -7 >> 1 is -4 (it rounds down) while -7 / 2 is -3 (it rounds toward zero).

A second flavor: a bitmask as a set

An int is a set of up to 32 small integers - bit i is 1 when i is in the set:

mask | (1 << i)       // add i
mask & ~(1 << i)      // remove i (x ^ (1 << i) toggles it - it would add i if absent)
(mask & (1 << i)) != 0   // contains i? parentheses required
a | b, a & b, a & ~b  // union, intersection, difference - one instruction each
Integer.bitCount(mask)   // size

for (int mask = 0; mask < (1 << n); mask++) {    // every subset of n items (n <= 30)
    for (int i = 0; i < n; i++) {
        if (((mask >> i) & 1) == 1) { /* item i is in this subset */ }
    }
}

mask | (1 << i)          # add i
mask & ~(1 << i)         # remove i (mask ^ (1 << i) toggles it - it would add i if absent)
(mask & (1 << i)) != 0   # contains i?
a | b, a & b, a & ~b     # union, intersection, difference
mask.bit_count()         # size (Python 3.10+)

for mask in range(1 << n):          # every subset of n items
    for i in range(n):
        if (mask >> i) & 1:
            pass                    # item i is in this subset

Subset enumeration visits 2^n masks - about a million for n = 20 - so it suits small n. When the question is about each bit position across many numbers, count per position instead: in "every value appears three times except one", each position's count of 1s is a multiple of 3 plus the lone value's bit, so count % 3 rebuilds the answer bit by bit.

Where you'll see it

Permission and feature flags packed into an int (flags | FLAG_X to set, flags & ~FLAG_X to clear, (flags & FLAG_X) != 0 to test); Unix file modes (chmod 755 is rwx = 4 + 2 + 1 for the owner, r-x = 4 + 1 for group and others); Java's EnumSet, which stores a set of up to 64 enum constants in a single long; BitSet and Bloom filters; IP subnet checks (address & netmask). Java's HashMap keeps a power-of-two table size so it can pick a bucket with hash & (size - 1) - which, unlike hash % size, is never negative for a negative hash code.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why does XOR-ing every element find the value that appears once among pairs - and why doesn't it work when the others appear three times?

2. What does n & (n - 1) do, and why does the power-of-two test also need n > 0?

3. while (n != 0) { count += n & 1; n >>= 1; } - what happens for n = -1, and what are two fixes?

Key takeaways

• XOR cancels values that appear an even number of times, in any order - lone value, missing number, and (split on a differing bit) two lone values.
• x & (x - 1) clears the lowest set bit; x & -x isolates it. Power-of-two tests need n > 0.
• An int is a set of up to 32 small integers: | adds, & ~ removes, & tests, and masks 0 to 2^n - 1 enumerate subsets.
• >> keeps the sign, >>> fills zeros; & 1 and >> 1 match % 2 and / 2 only for non-negative numbers.
• Shift distances wrap (1 << 32 == 1), and ==/!= bind tighter than & - use 1L and parentheses.
• When value tricks fail, count each bit position (sign bit included).