Bit Manipulation

A byte is 8 bits. Bitwise operators work directly on the binary representation of integers and run in $O(1)$ per word.

Operators

Common tricks

• Check bit i: (n >> i) & 1
• Set bit i: n | (1 << i); clear it: n & ~(1 << i); toggle it: n ^ (1 << i)
• Odd or even: n & 1
• Clear the lowest set bit: n & (n - 1); this also tests for a power of two (n > 0 && (n & (n - 1)) == 0)
• Isolate the lowest set bit: n & -n
• XOR properties: a ^ a = 0 and a ^ 0 = a, so XOR-ing all elements cancels pairs and leaves the single unpaired value

Recognition signals

• “Without extra space” with one unpaired element among pairs
• Counting set bits, reversing bits, or per-bit properties of numbers
• Subsets of a small set represented as a bitmask ($2^n$ states, $n \le 20$)
• Powers of two

Gotchas

• Operator precedence: parenthesize, for example (n & 1) == 0
• >> on negative numbers is an arithmetic shift in most languages; use >>> (JavaScript, Java) for a logical shift
• Looping with n >> 1 never ends for negative numbers in languages with sign extension
• JavaScript bitwise operators work on 32-bit signed integers; Python integers are unbounded, so mask with & 0xFFFFFFFF when emulating 32-bit behavior
• Counting bits by shifting is $O(\text{bits})$; n & (n - 1) loops only once per set bit

Templates

• Bit Operators: operators and counting set bits

Problems