Bit Manipulation

Bit Manipulation | Algoryva

Intuition

A row of light switches

Picture eight light switches in a row. Each is on or off, and which are on can be read as a number: switch k carries the value 2^k when it is on. With switches 2 and 3 on you have 4 + 8 = 12. That is exactly binary: 12 is 1100.

Operations on the whole row at once are very fast: flip a single switch, check one, switch off the lowest one that is on, combine two rows. Because a computer stores integers this way, these operations are single machine instructions, and clever use of them turns loops into one-liners.

First, the naive way

Counting set bits one at a time

How many switches are on in a number? The direct way looks at the lowest bit, drops it, and repeats until nothing is left. Or convert to a text string of 0s and 1s and count the "1" characters.

Both work, and are fine for one number. But the loop does one step for every bit position, ones and zeros alike (32 or 64 steps), and the string version builds a whole string. If you must do it for millions of numbers, or for a number with a single bit set among many zeros, that is wasted work. The tricks below do one step per set bit, and often no loop at all.

python

def popcount_loop(x):
    count = 0
    while x:
        count += x & 1          # look at the lowest bit
        x >>= 1                 # drop it
    return count

def popcount_string(x):
    return bin(x).count("1")

print(popcount_loop(255), popcount_string(255))   # 8 8
print(popcount_loop(1 << 40), popcount_string(1 << 40))   # 1 1

Cost: One step per bit position (about 32 to 64 per number), regardless of how many bits are actually set.

The observation

One operation works on every bit at once

a & b, a | b and a ^ b combine two numbers bit by bit, all positions in a single step. A mask with exactly one bit set (1 << k) lets you address one switch: combine it with | to turn it on, with & ~mask to turn it off, with ^ to flip it, with & to test it.

Two arithmetic facts about the lowest set bit give most of the famous tricks: subtracting 1 from a number flips its lowest set bit to 0 and all the zeros below it to 1; negating a number (-x) keeps the lowest set bit and flips everything above it. So x & (x - 1) erases the lowest set bit, and x & -x keeps only the lowest set bit.

The concept

The operators and the idioms

Memorise these. They appear everywhere.

AND a & b: 1 only where both are 1 (use for testing and masking). OR a | b: 1 where either is 1 (use for setting). XOR a ^ b: 1 where they differ (use for flipping and cancelling). NOT ~a: flips every bit; in Python ~a == -a - 1.
Shifts: a << k multiplies by 2^k; a >> k divides by 2^k rounding down. 1 << k is the mask with only bit k set.
Test bit k: (x >> k) & 1. Set: x | (1 << k). Clear: x & ~(1 << k). Toggle: x ^ (1 << k).
Lowest set bit: x & -x. Erase it: x & (x - 1). Power of two: x > 0 and (x & (x - 1)) == 0.
XOR laws: x ^ x = 0, x ^ 0 = x, and XOR is commutative and associative, so in a long XOR any value appearing twice cancels out.
Subset as a mask: with n ≤ about 20 items, bit i of an integer says whether item i is chosen; range(1 << n) visits all 2^n subsets.
Precedence: in Python, + - bind tighter than << >>, which bind tighter than &, then ^, then |, and all of these bind tighter than comparisons. So x & 1 == 0 works as (x & 1) == 0, but 1 << k + 1 is 1 << (k + 1). In C, C++, Java and JavaScript comparisons bind than , and , so there is parsed as : a silent bug in C, C++ and JavaScript, and a compile error in Java. Parenthesise bit expressions so they read the same in every language.

See it move

Bits in motion

The top row is a = 12 written lowest bit first, so the number under each box is the bit position (position 0 is the 1s place, position 3 is the 8s place). Step through AND, OR, XOR, shifts, single-bit edits, and the two lowest-bit tricks. Highlighted boxes are the 1s in each result.

Worked by hand

12 and 10 by hand

Write both numbers in binary with the lowest bit on the right, as usual.

expression	binary	decimal
a = 12	1100	12
b = 10	1010	10
a & b	1000	8
a \| b	1110	14
a ^ b	0110	6
a << 1	11000	24
a >> 2	0011	3
a & -a (lowest set bit)	0100	4
a & (a - 1) (erase it)	1000	8

1
Why a & −a is the lowest set bit
12 is 00001100. Negating gives 11110100 (flip all bits, add 1). They agree only at bit 2, the lowest set bit, so ANDing leaves 00000100 = 4.
2

Implementation

The operators, run

Predict each output before reading the comment, especially the last line.

python

x = 12
print(bin(x), x & 10, x | 10, x ^ 10)   # 0b1100 8 14 6
print(x << 1, x >> 2, 1 << 5)   # 24 3 32
print(bool(x >> 2 & 1), bool(x >> 1 & 1))   # True False
print(x | (1 << 0), x & ~(1 << 2), x ^ (1 << 3))   # 13 8 4
print(x & -x, x & (x - 1))   # 4 8
print(~5, -5 & 0xFF, bin(-5 & 0xFF))   # -6 251 0b11111011
print(x.bit_count(), (x).())   
( &  == , ( & ) == )   
( <<  + , ( << ) + )

Implementation

Counting bits and powers of two

Kernighan's trick counts set bits with one step per set bit: erase the lowest set bit until nothing is left.

Plan in plain steps

pseudocode

count = 0
while x is not 0:
    x = x with its lowest set bit erased   (x & (x − 1))
    count += 1

python

def popcount_loop(x):
    count = 0
    while x:
        count += x & 1
        x >>= 1
    return count

def popcount_kernighan(x):
    count = 0
    while x:
        x &= x - 1              
        count += 
     count

 (x):
     x >   (x & (x - )) == 

((), (), ( << ))   
([n  n  (, )  (n)])   
((), (-), ())   

 random
random.()
(((v) == (v) == v.()  v  (random.(**)  _  ())))

Implementation

XOR: cancelling, swapping, finding what is missing

Because x ^ x = 0 and XOR is order-independent, XOR-ing a whole list makes every value that appears twice vanish. What survives is the value that appears an odd number of times.

python

def single_number(a):
    result = 0
    for x in a:
        result ^= x             # pairs cancel: x ^ x = 0, and 0 ^ y = y
    return result

def missing_number(a):          # a holds 0..n with one value missing
    n = len(a)
    result = n
    for i, x in enumerate(a):
        result ^= i ^ x
    return result

print(single_number([4, 1, 2, 1, 2]))   # 4
print(single_number([7]))   # 7
print(missing_number([3, 0, ]))   
(([, , , , , , , , ]))   
a, b = , 
a ^= b
b ^= a
a ^= b
(a, b)   
( ^ ,  ^ ,  ^  ^ )

Implementation

A set in one integer: all subsets and submasks

With a few items, a whole subset fits in one integer. Looping mask from 0 to 2ⁿ − 1 visits every subset exactly once. A neat related trick enumerates only the submasks of a given mask.

python

def subsets(a):
    n = len(a)
    return [[a[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]

def submasks(mask):
    out = []
    s = mask
    while True:
        out.append(s)
        if s == 0:
            break
        s = (s - 1) & mask
    return out

print(subsets([1, 2, 3]))   # [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
print(len(subsets((()))))   
((0b101))   
(((0b1111)), (((m))  m  ()))

Complexity

Costs

Bit tricks make constant factors small, but they do not change the shape of an algorithm: a subset enumeration is still exponential. They shine when they replace a loop (popcount, lowest bit), a dictionary (XOR cancelling), or an array of booleans (a mask).

A single bitwise operation

time O(1)space O(1)

One machine instruction for word-sized integers. (Python's big integers cost O(length).)

Test, set, clear, toggle one bit

time O(1)space O(1)

A shift and one bitwise operation.

popcount by looping every bit

time O(bits)space O(1)

One step per bit position.

popcount with Kernighan's trick

time O(set bits)space O(1)

Each step erases one set bit.

XOR over a list of n values

time O(n)space O(1)

One pass, one accumulator.

Enumerate all subsets of n items

time O(n × 2ⁿ)space O(n)

2ⁿ masks, up to n bits each to read.

All submasks of all masks (n bits)

time O(3ⁿ)space O(1)

Edge cases

Negative numbers in PythonThey behave as infinite two's complement. x >> 1 rounds toward negative infinity. Mask (& 0xFFFFFFFF) when you need a fixed width.
x = 0x & (x - 1) is 0 & -1 = 0; is_power_of_two needs the x > 0 guard; popcount of 0 is 0; x & -x is 0.
Shifting by a negative or huge amountA negative shift count raises ValueError. 1 << 1000 is fine in Python (big integer) but overflows in C++ and Java: use 64-bit and keep k below 63.
Fixed-width languagesIn C++/Java use 1LL << k for bit 40, beware signed overflow on 1 << 31, and use unsigned types when shifting right.
Operator precedenceIn Python x & 1 == 0 works, and 1 << k + 1 means 1 << (k + 1). In C, C++, Java and JavaScript == binds tighter than &, so x & 1 == 0 is a bug (or a compile error in Java) there. Parenthesise every mixed expression.
More than ~20 items in a subset mask2ⁿ masks are too many. A mask is still fine as a *set representation* (up to 63 items in one integer), just not for enumeration.

Common mistakes

Mistakes to avoid

Relying on operator precedence you have not checked, such as 1 << k + 1 (which is 1 << (k + 1), not (1 << k) + 1) or x & 1 == 0 in C++.
Parenthesise mixed bit and arithmetic expressions; precedence also differs between Python and the C family.
Using ^ for exponentiation (2 ^ 5).
^ is XOR: 2 ^ 5 = 7. Use ** for powers or 1 << k for powers of two.
Forgetting that ~x is negative.
~x == -x - 1. To clear a bit use x & ~mask (which is fine), but do not print ~x expecting a flipped 8-bit value.
is_power_of_two without x > 0.
0 passes (x & (x - 1)) == 0. Add the guard.

Recognize it in a contest

How to spot a bit-manipulation problem

Reach for it when the problem says or implies

“Every value appears twice except one” (or three times except one): XOR (or bit counts per position).
“Find the missing or duplicate number” with values in a tight range, in O(1) space: XOR.
n ≤ 20 items and you must consider subsets: a bitmask per subset, or bitmask DP.
Powers of two, parity, “is this a power of 4?”, “flip all bits”, “count 1 bits”, “lowest set bit”.
Toggling states of many switches or flags, or storing a small set of booleans compactly.
Problems on XOR of ranges or maximising an XOR (often using properties of XOR and binary tries).

Look elsewhere when

Worked problem

Two lonely numbers

The problem

In a list every value appears exactly twice, except two different values that appear once each. Find those two in O(n) time and O(1) extra space.

XOR the whole list: pairs cancel, leaving p ^ q where p and q are the two lonely values. Since p ≠ q, this is not 0, so some bit is 1 in it: that bit is one where p and q differ.
Pick that bit with x & -x (the lowest set bit of the XOR).
Split the numbers into two groups: those with that bit set, and those without. p and q land in different groups, and every pair stays together in one group.
XOR each group separately: the pairs cancel, leaving p in one and q in the other.

python

def single_two(a):
    x = 0
    for v in a:
        x ^= v                          # x = p ^ q, where p and q are the two lonely values
    low = x & -x                        # a bit where p and q differ
    p = 0
    for v in a:
        if v & low:
            p ^= v                      # this group holds exactly one of them (pairs still cancel)
    return sorted((p, x ^ p))

(([, , , , , ]))   
(([, ]))   
(([-, , , ]))

Worked problem

Bit counts for every number up to n

The problem

Return a list res where res[i] is the number of 1 bits in i, for every i from 0 to n, in O(n) total.

Calling popcount on every number would cost O(n log n).
Use a recurrence: the bits of i are the bits of i >> 1 (drop the last bit) plus the last bit itself, i & 1.
So res[i] = res[i >> 1] + (i & 1), and res[i >> 1] is already known because i >> 1 < i.

python

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)   # drop the lowest bit, then add it back if it was 1
    return dp

print(count_bits(5))   # [0, 1, 1, 2, 1, 2]
print(count_bits(0))   # [0]
print(count_bits()[-], ()[-])   
((c == (i).()  i, c  (())))

Wrap-up

Remember this

A number is a row of switches: bitwise operators act on every switch at once.
A mask 1 << k tests, sets, clears and toggles one bit; x & -x isolates and x & (x − 1) erases the lowest set bit.
XOR cancels equal values, finding a lonely or missing number in O(n) time and O(1) space.
A bitmask is a compact set; looping over all masks enumerates all subsets, practical up to about 20 items.
Parenthesise mixed bit expressions, because precedence differs from the C family (in Python 1 << k + 1 is 1 << (k + 1)), and remember Python integers are unlimited with infinite two's complement for negatives.

Cheat sheet

Test / set / clear / toggle bit k: (x >> k) & 1 · x | (1 << k) · x & ~(1 << k) · x ^ (1 << k)
Lowest set bit; erase it: x & -x · x & (x − 1)
Power of two: x > 0 and (x & (x − 1)) == 0
Popcount: x.bit_count() (3.10+) or loop x &= x − 1
XOR laws: x ^ x = 0 · x ^ 0 = x · order does not matter
Subsets: for mask in range(1 << n): bit i of mask = item i chosen

Top traps to avoid

Relying on operator precedence you have not checked, such as 1 << k + 1 (which is 1 << (k + 1), not (1 << k) + 1) or x & 1 == 0 in C++.
Using ^ for exponentiation (2 ^ 5).
Forgetting that ~x is negative.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is 12 ^ 10 (XOR)?
2.What does x & (x - 1) do?
3.What does 1 << 2 + 1 evaluate to in Python?
4.“Every number in the list appears twice except one; find it in O(1) extra memory” suggests:
5.How many masks does enumerating all subsets of 20 items visit?
6.Why does is_power_of_two need the x > 0 guard?
7.What does print(5 ^ 3) print?
8.How many set bits does 13 have? (print(bin(13).count('1')))
9.What does print(12 & 11) print?
10.What is the lowest set bit of 12, as printed by print(12 & -12)?
11.In [4, 1, 2, 1, 2], every value appears twice except one. What does XOR of all values print?
12.What does x & (x - 1) do?
13.What does print(1 << 10) print?
14.Counting set bits by repeatedly clearing the lowest bit takes how long?
15.What is x XOR x for any value x?

&

^

|

x & 1 == 0

x & (1 == 0)

Bit Manipulation

After this lesson you will be able to

Builds on

Unlocks

A row of light switches

Counting set bits one at a time

One operation works on every bit at once

The operators and the idioms

Bits in motion

12 and 10 by hand

The operators, run

Counting bits and powers of two

XOR: cancelling, swapping, finding what is missing

A set in one integer: all subsets and submasks

Costs

Edge cases

Mistakes to avoid

How to spot a bit-manipulation problem

Two lonely numbers

Bit counts for every number up to n

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Core39 problems

Application21 problems

Reading the code

Reading the code

Reading the code

Reading the code