Bit Manipulation

What bit manipulation is

Every integer your program stores is, underneath, a row of bits — switches that are each either 0 or 1. Bit manipulation is the practice of working on those switches directly instead of treating the number only as a quantity. It shows up in interviews because a handful of tiny operations can replace loops, sets, and extra arrays, turning O(n) bookkeeping into a couple of O(1) tricks. The numbers lesson introduced int as an ordinary whole number; here we look at the same value from a different angle, as a pattern of bits. Nothing about the number changes; we just gain a second set of tools for inspecting and combining values.

Binary representation

We normally write numbers in base 10, where each place is worth ten times the one to its right. Computers use base 2 (binary), where each place is worth two times the one to its right: 1s, 2s, 4s, 8s, and so on. A bit that is 1 means “add this place’s value”; a bit that is 0 means “skip it.” Take 13; in binary it is 1101:

place value:   8   4   2   1
bit:           1   1   0   1

Add the places whose bit is 1: 8 + 4 + 1 = 13. Python’s built-in bin function shows this, with a 0b prefix marking the digits as binary.

print(bin(13))   # -> 0b1101
print(bin(0))    # -> 0b0

The least-significant bit (LSB) is the rightmost one, the 1s place; we call it bit index 0. Counting leftward, bit index 1 is the 2s place, bit index 2 the 4s place, and so on, so “bit i” means the bit worth 2**i. This lesson deals only with non-negative integers, where this picture is exact; negatives get a short note near the end.

The bitwise operators

Six operators act on numbers bit by bit. The first three combine two numbers by lining them up and looking at each position independently; a small truth table gives the rule for one position.

AND & puts a 1 where both bits are 1; OR | where at least one is 1; XOR ^ (exclusive or) where the bits differ. One truth table gives all three rules per position, and the worked column applies them to 12 and 10:

a b | & | ^        12 = 1100
0 0 | 0 0 0        10 = 1010
0 1 | 0 1 1        &  = 1000  -> 8   (only the 8s column is 1 in both)
1 0 | 0 1 1        |  = 1110  -> 14  (every column with any 1)
1 1 | 1 1 0        ^  = 0110  -> 6   (the 4s and 2s columns differ)

print(12 & 10)   # -> 8
print(12 | 10)   # -> 14
print(12 ^ 10)   # -> 6

NOT ~ flips every bit of one number. Because Python integers are not a fixed width, the tidy way to state the result is the identity ~x == -(x + 1); the Python-specifics section explains why it comes out negative.

Left shift << slides every bit left by a given number of places, filling the right with zeros; each shift multiplies by 2, just as appending a 0 to a decimal number multiplies by 10. Right shift >> slides every bit right, dropping bits that fall off the end; each shift divides by 2 and discards any remainder, the same as // 2.

print(~12)      # -> -13   (equals -(12 + 1))
print(3 << 2)   # -> 12    (0011 -> 1100, that is 3 * 4)
print(1 << 4)   # -> 16    (a single 1 at bit index 4, worth 2**4)
print(13 >> 1)  # -> 6     (1101 -> 0110, that is 13 // 2)

1 << i is worth memorizing on its own: a number with a single 1 at bit index i and zeros elsewhere. It is the building block for the next section.

Single-bit operations

With 1 << i in hand, four recipes let you inspect or change one bit without disturbing the others. Let x = 0b1010 (which is 10) run through all four; each line below starts fresh from x.

• Test bit i — shift it down to index 0, then mask the rest off with & 1.
• Set bit i — OR with a single-bit mask: OR-ing with 1 forces a 1, OR-ing with 0 changes nothing.
• Clear bit i — invert the mask with ~ so every position except i is 1, then AND: AND keeps a bit where the mask is 1 and zeros it where it is 0.
• Toggle bit i — XOR with a single-bit mask: XOR with 1 flips a bit, XOR with 0 leaves it alone.

x = 0b1010
print((x >> 1) & 1)   # -> 1    test bit 1: it is set
print((x >> 0) & 1)   # -> 0    test bit 0: it is clear
print(x | (1 << 0))   # -> 11   set bit 0:    1010 -> 1011
print(x & ~(1 << 1))  # -> 8    clear bit 1:  1010 -> 1000
print(x ^ (1 << 2))   # -> 14   toggle bit 2: 1010 -> 1110

Keep the pattern in mind: OR to set, AND-with-NOT to clear, XOR to toggle, and shift-then-AND-1 to test.

Key idioms and why they work

x & (x - 1) clears the lowest set bit

Subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into 1. AND-ing the original with that keeps only the bits above the lowest 1, erasing exactly that bit:

  x     = 1100   (12)
  x - 1 = 1011   (11)
  &     = 1000   (8)   -> the lowest 1 is gone

Because each application removes one set bit, you can count set bits by repeating until zero — the loop runs once per 1, not once per bit position:

def popcount(x):
    count = 0
    while x:
        x &= x - 1   # drop the lowest set bit
        count += 1
    return count

print(popcount(13))   # -> 3   (1101 has three 1s)
print(popcount(255))  # -> 8   (11111111)

The same idiom gives a clean power-of-two test: a power of two has exactly one bit set, so clearing it must leave zero.

def is_power_of_two(x):
    return x > 0 and (x & (x - 1)) == 0

print(is_power_of_two(16))  # -> True    (10000)
print(is_power_of_two(18))  # -> False   (10010, two bits)
print(is_power_of_two(0))   # -> False   (guarded by x > 0)

x & -x isolates the lowest set bit

Where x & (x - 1) removes the lowest set bit, x & -x keeps only that bit and zeros everything else, returning its place value:

print(12 & -12)   # -> 4   (1100 -> keeps 100)
print(10 & -10)   # -> 2   (1010 -> keeps 10)

It works because of how negatives are stored (two’s complement): -x is ~x + 1, which leaves only the lowest set bit aligned between x and -x. Remember it as “isolate the lowest 1.”

XOR properties and the single-number trick

XOR has three properties that make it a workhorse:

• a ^ a == 0 — a value XOR-ed with itself cancels to zero.
• a ^ 0 == a — XOR-ing with zero changes nothing.
• It is commutative and associative, so the order you XOR a batch does not matter.

Put these together: XOR a list where every value appears twice except one, the pairs each cancel to 0, and the lone value survives.

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n   # pairs cancel; the unique value remains
    return result

print(single_number([4, 1, 2, 1, 2]))   # -> 4
print(single_number([7]))                # -> 7

This finds the answer in O(n) time and O(1) space — no hash set, no sorting.

Bitmasks as subsets of a small set

A single integer can stand in for a subset of a small collection: let bit i mean “item i is included.” An integer with n usable bits encodes any of the 2**n possible subsets, and you can walk all of them by counting from 0 up to 2**n - 1; each number, read as a bit pattern, is one subset.

def subsets(items):
    n = len(items)
    result = []
    for mask in range(1 << n):            # 1 << n is 2**n: every subset
        subset = [items[i] for i in range(n) if (mask >> i) & 1]
        result.append(subset)             # keep item i when its bit is set
    return result

print(subsets(["a", "b"]))
# -> [[], ['a'], ['b'], ['a', 'b']]

The membership test (mask >> i) & 1 is the same “test bit i” recipe from earlier. Reading the four masks makes the encoding concrete:

mask 00 -> []          mask 10 -> ['b']
mask 01 -> ['a']       mask 11 -> ['a', 'b']

This is the foundation of state-compression dynamic programming, where a subset of visited cities or chosen items is stored as one integer key. The point for now: “a set of up to ~20 flags” fits in one integer, and the bit operations above become your set operations.

A note on Python specifics

Python ints are arbitrary precision: they grow as large as memory allows and never overflow, with no fixed 32- or 64-bit width. Because of that unbounded model, ~x == -(x + 1): Python treats an integer as having infinitely many leading sign bits, so flipping them all yields a negative value. Many interview problems, though, assume a fixed 32-bit integer, where ~5 would be a large positive pattern. To emulate that, mask the result to 32 bits with & 0xFFFFFFFF (a value whose lowest 32 bits are all 1) — but reach for this only on those “assume 32-bit” problems.

print(~5)                # -> -6           (equals -(5 + 1))
print(~5 & 0xFFFFFFFF)   # -> 4294967290   (the low 32 bits of ~5)

Worked trace

Each row below starts fresh from x = 10, whose binary is 1010; the operations do not chain:

Common pitfalls

• Operator precedence. The bitwise operators bind looser than arithmetic and the shifts. 1 << 2 + 1 is 1 << 3 (8), not (1 << 2) + 1, because + runs first; and x & 1 << 1 means x & (1 << 1), since << binds tighter than &. When you mix shifts with &, |, ^, or arithmetic, parenthesize.
• & vs == precedence. x & 1 == 0 parses as x & (1 == 0) because == binds tighter than &. Write (x & 1) == 0 to test whether the lowest bit is clear.
• Testing a bit forgets the mask. x >> i alone still carries every higher bit; finish with & 1 to reduce it to 0 or 1.
• Signed vs Python’s unbounded ints. ~x is negative and there is no overflow. If a problem assumes fixed-width 32-bit integers, mask with & 0xFFFFFFFF yourself, or your answer will disagree with C or Java.
• Confusing the two lowest-bit idioms. x & (x - 1) removes the lowest set bit; x & -x keeps only it. They look alike and do opposite things.

Big-O summary

Each operation acts on a machine-word-sized integer in constant time. On Python’s arbitrary-precision ints the true cost scales with the bit width w, so the honest bound is O(w) — but for fixed-size interview integers that is effectively O(1).

Practice

1. Write count_bits(x) two ways: once by shifting right and testing x & 1 each step, once with the x & (x - 1) idiom. Confirm both agree for 0, 1, 255, and 1023, and note which loop runs fewer times on a sparse number like 1 << 20.

2. Given a list where every value appears twice except two distinct values that each appear once, find both. (Hint: XOR everything to get a ^ b, use x & -x on that to find a bit where they differ, split the list by that bit, and XOR each group separately.)

3. Use a bitmask loop to print every subset of ["red", "green", "blue"], and check you get all 2**3 == 8 subsets, including the empty one. Then modify it to print only the size-2 subsets using popcount(mask) == 2.