Know this before you start: โShifts: x << 1 and x >> 1โ
Bit shifts
x << 1 moves every bit left: ร2. x >> 1 moves them right: halves and drops the remainder. 1 << i is a number with only bit i set.
The idea
Shifting left by k multiplies by 2แต, shifting right by k divides by 2แต (rounding down for positive numbers).
1 << i builds a mask with just bit i set, which combines with &, | and ^ to test, set, clear or toggle that bit.
Walking through a number's bits is a loop of x & 1 and x >>= 1.
See it step by step
Count the 1-bits of 11 (1011)
- 1011: last bit 1 โ count 1; shift โ 101
- 101: 1 โ count 2; shift โ 10
- 10: 0; shift โ 1: 1 โ count 3; shift โ 0, stop. Three 1-bits.
In code (Python)
print(5 << 1, 5 << 3, 40 >> 2) # 10 40 10
def count_ones(x):
count = 0
while x:
count += x & 1
x >>= 1
return count
x = 0b1010
x |= 1 << 0 # set bit 0 โ 0b1011
x &= ~(1 << 3) # clear bit 3 โ 0b0011
print(count_ones(11), bin(x)) # 3 0b11Each shift: O(1). Looping over bits: O(number of bits).
When you'll use it
- Reverse bits, count bits, powers of two, building masks, generating subsets.
Common mistakes
- Right-shifting negative numbers expecting zeros to come in (they keep the sign).
- Mixing up << with exponentiation for non-powers of two.
