Bit Manipulation
Tricks with ones and zeros.
Inside the computer, every number is stored as bits, ones and zeros. A few operators work on those bits directly. They're extremely fast, and a handful of tricks come up again and again in interviews.

- Numbers are bits
- Operators work on bits
- A few classic tricks
Bit tricks
Bin shows a number's bits. Ampersand keeps the bits that are on in both numbers. N and one tells you if a number is odd, by checking its last bit. N and N minus one is zero only for powers of two. And XOR, the caret, cancels out equal numbers, so XOR-ing a list where every number appears twice, except one, leaves just the lonely number. Run it.
print(bin(13), bin(6), bin(13 & 6))
print([n & 1 for n in [4, 7, 10, 13]])
print([n for n in range(1, 70) if n & (n - 1) == 0])
lonely = 0
for n in [4, 1, 2, 1, 2]:
lonely ^= n
print("the number without a pair:", lonely)0b1101 0b110 0b100 [0, 1, 0, 1] [1, 2, 4, 8, 16, 32, 64] the number without a pair: 4
Bit operators
Here are the operators. And, or, and XOR combine bits. Shift left by one doubles a number, and shift right by one halves it. They're useful for storing many true or false flags in one number, for permissions, and for some very fast algorithms.
| Operator | Meaning | Example |
|---|---|---|
| a & b | and | 13 & 6 = 4 |
| a | b | or | 13 | 6 = 15 |
| a ^ b | xor | 13 ^ 6 = 11 |
| a << 1 | double | 5 << 1 = 10 |
| a >> 1 | halve | 5 >> 1 = 2 |
Summary
Bit tricks check odd numbers, powers of two, and find a lonely number with XOR. Next, how to choose the right technique for a problem.
Key takeaways- n & 1 for odd
- n & (n-1) == 0
- x ^ x == 0