Bit manipulation — arithmetic in binary
Bit manipulation
Python ints are arbitrary precision. 1 << 200 is legal. ~n returns -n - 1 (two's complement of infinite-width int), not a 32-bit flip. Mask with & 0xFFFFFFFF for fixed width.
The operators
& AND · | OR · ^ XOR · ~ NOT · << left-shift · >> right-shift · n.bit_length() · n.bit_count() (3.10+) · bin(n)
XOR is the interesting one: addition mod 2. x ^ x == 0, x ^ 0 == x. Powers half the tricks.
Four tricks worth memorising
n & (n - 1) clears the lowest set bit. Loop until zero = counted set bits in O(popcount) time. Kernighan's algorithm.
n & -n isolates the lowest set bit. Two's complement. Useful for iterating set bits or Fenwick trees.
XOR finds the odd one out. Array where every value appears twice except one — XOR everything, pairs cancel.
Power of two test. n > 0 and n & (n - 1) == 0. Exactly one bit set.
Common pitfalls
~non Python int. Returns-n - 1. Mask if emulating 32-bit.- Precedence.
&binds looser than==.(x & 1) == 0, notx & 1 == 0. - XOR swap. Fails on same variable slot. Use tuple swap.
Try it
- Write
is_power_of_four(n)— true only for 1, 4, 16, 64. Hint: power of two AND set bit at even position (n & 0x55555555). - Given list where every value appears three times except one, find the loner in O(n) time and O(1) space.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Write
count_set_bits(n)that returns the number of 1-bits in the binary representation of the non-negative integern(also called the Hamming weight). - Exercise 2
Write
is_power_of_two(n)that returns True ifnis a positive power of 2 (1, 2, 4, 8, 16, ...), else False. Use a single bit trick, not a loop. - Exercise 3
Every number in
numsappears exactly twice except one that appears once. Writesingle_number(nums)that returns the lonely one in O(n) time and O(1) extra space using XOR.