Bit Manipulation Tricks

Tries & Bit Manipulation, lesson 2 of 3

Bit Manipulation Tricks

Read, set and clear bits, cancel pairs with XOR and enumerate subsets with masks.

14 min, 0 of 4 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Every int is a row of bits; bit i is worth 2 ** i. Python gives you three ways to look at them:

bin(13)            # '0b1101'
format(13, "08b")  # '00001101'
int("1101", 2)     # 13

Bit problems show up in interviews as "do it in O(1) extra space", "every element appears twice except one", "count the 1 bits", or "try every subset of a small set". The operators are the whole toolbox:

Example

The six operators

:04b in an f-string prints binary padded to 4 digits. Change a and b and predict each line before you run it.

Tricks worth memorising

Goal Expression
read bit i (x >> i) & 1
set bit i `x
clear bit i x & ~(1 << i)
toggle bit i x ^ (1 << i)
drop lowest set bit x & (x - 1)
isolate lowest set bit x & -x
power of two? x > 0 and x & (x - 1) == 0

Why does x & (x - 1) work? Subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1. ANDing with the original wipes out exactly that bit:

x     = 101100
x - 1 = 101011
and   = 101000   (lowest 1 gone)

XOR is the star. a ^ a == 0, a ^ 0 == a, and the order doesn't matter. XOR a whole list and every value that appears twice cancels out.

Example

Peel off set bits one at a time

The loop runs once per 1 bit, not once per bit position. This is Brian Kernighan's trick, the standard answer to "count the set bits".

Quiz

What does this print?

Masks as subsets. With n items, each number from 0 to 2**n - 1 is a different yes/no choice for every item: bit i set means "item i is in". Looping over range(1 << n) enumerates all 2ⁿ subsets with no recursion. Fine for n up to about 20.

Example

All subsets with a bitmask

Read the mask right to left: bit 0 is "a". Masks are also handy as compact, hashable "visited sets" in DP (dp[mask]).

Quiz

What does this print?

Quiz

What does this print?

Exercise

Count subsets with a target sum

Write count_subsets(nums, target) returning how many subsets (chosen by position) add up to target. Use a bitmask loop over range(1 << len(nums)). The empty subset has sum 0.

count_subsets([1, 2, 3], 3) is 2: {1, 2} and {3}.