AI Hints
Home›DSA in Python Tutorial›Puzzles, Bits and Strategy
DSA in Python · Lesson 101 of 132

Bit Manipulation

Tricks with ones and zeros.

⏱ 2 min read▶ Video at 2:00:55🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Bit Manipulation
From the video: Bit Manipulation
  • 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.

bits.pypython
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)
Output
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.

OperatorMeaningExample
a & band13 & 6 = 4
a | bor13 | 6 = 15
a ^ bxor13 ^ 6 = 11
a << 1double5 << 1 = 10
a >> 1halve5 >> 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
Next up: Choosing a Technique — which tool for which problem