Bit Manipulation

Learn bit manipulation in Python: AND, OR, XOR and shifts, bit masks for flags and subsets, counting set bits, and classic XOR interview tricks.

• Intermediate
• 16 min read
• 4 objectives

Before this lessonLesson 14: Minimum Spanning Trees: Kruskal and Prim

Every integer in your computer is stored as a row of bits: zeros and ones. Most of the time you never think about that. But operating on the bits directly lets you pack many true/false flags into one number, test and change them in a single CPU instruction, and solve some puzzles in O(1) extra space that would otherwise need a hash set. Permissions systems, compression, hashing, graphics and networking (IP subnet masks) all rely on it.

Python makes experimenting easy: bin() shows binary, 0b literals write it, and Python integers never overflow, so you can focus on the ideas.

Binary in two minutes

Each position is a power of two, counting from the right starting at 2⁰. So 0b1011 is 8 + 0 + 2 + 1 = 11. The rightmost bit is bit 0, the "lowest" bit.

for n in [5, 11, 64, 255]:
    print(n, bin(n), format(n, "08b"))
print(0b1011, int("1011", 2))

5 0b101 00000101
11 0b1011 00001011
64 0b1000000 01000000
255 0b11111111 11111111
11 11

The six operators

• a & b (AND): 1 only where both bits are 1. Used to test or clear bits.
• a | b (OR): 1 where either bit is 1. Used to set bits.
• a ^ b (XOR): 1 where the bits differ. Used to toggle bits.
• ~a (NOT): flips every bit. In Python, ~a == -a - 1.
• a << k: shift left k places, the same as multiplying by 2^k.
• a >> k: shift right k places, the same as floor division by 2^k.

a, b = 0b1100, 0b1010
print(format(a & b, "04b"), format(a | b, "04b"), format(a ^ b, "04b"))
print(~a, 3 << 4, 100 >> 3)

1000 1110 0110
-13 48 12

Bit masks for flags

Give each permission its own bit: 1, 2, 4, 8 and so on (1 << i). A user's permissions are then a single integer. This is exactly how Unix file modes like chmod 755 work, and how Python's re.IGNORECASE | re.MULTILINE flags combine.

READ, WRITE, DELETE, ADMIN = 1 << 0, 1 << 1, 1 << 2, 1 << 3

perms = READ | WRITE                    # set two flags
print("can write:", bool(perms & WRITE))
print("can delete:", bool(perms & DELETE))
perms |= DELETE                         # grant
perms &= ~WRITE                         # revoke
perms ^= ADMIN                          # toggle
print(format(perms, "04b"))

can write: True
can delete: False
1101

The four idioms to memorise, for bit i of x: test x >> i & 1, set x | (1 << i), clear x & ~(1 << i), toggle x ^ (1 << i). All are O(1).

Counting set bits and the x & (x - 1) trick

Subtracting 1 from a number flips its lowest 1 bit to 0 and all the zeros below it to 1. So x & (x - 1) removes the lowest set bit. Repeating it counts the 1s in O(number of set bits), and a number is a power of two exactly when it has a single set bit.

def count_bits(x):
    count = 0
    while x:
        x &= x - 1        # drop lowest set bit
        count += 1
    return count

def is_power_of_two(x):
    return x > 0 and x & (x - 1) == 0

print(count_bits(0b101101), (45).bit_count())
print([n for n in range(1, 70) if is_power_of_two(n)])
print("lowest set bit of 40:", 40 & -40)

4 4
[1, 2, 4, 8, 16, 32, 64]
lowest set bit of 40: 8

In Python 3.10 and later, int.bit_count() counts set bits directly and is the one to use in real code. x & -x isolates the lowest set bit, which is the heart of the Fenwick tree data structure.

XOR tricks

XOR has three properties that make it magical: x ^ x == 0, x ^ 0 == x, and order does not matter. So if every value in a list appears twice except one, XOR-ing everything cancels the pairs and leaves the loner. O(n) time, O(1) space, no set needed.

from functools import reduce
from operator import xor

order_ids = [4021, 3310, 5577, 3310, 4021]
print(reduce(xor, order_ids))

# find the missing number in 0..n
seen = [0, 1, 3, 4, 5]
n = len(seen)
missing = reduce(xor, range(n + 1)) ^ reduce(xor, seen)
print(missing)

5577
2

Enumerating subsets with masks

A set of n items has 2ⁿ subsets, and the numbers 0 to 2ⁿ - 1 are exactly all n-bit patterns. Treat bit i as "item i is included" and a single loop walks every subset. This is an iterative alternative to the backtracking approach, and bitmask DP builds on it.

toppings = ["cheese", "olive", "basil"]
n = len(toppings)
for mask in range(1 << n):
    chosen = [toppings[i] for i in range(n) if mask >> i & 1]
    print(format(mask, "03b"), chosen)

000 []
001 ['cheese']
010 ['olive']
011 ['cheese', 'olive']
100 ['basil']
101 ['cheese', 'basil']
110 ['olive', 'basil']
111 ['cheese', 'olive', 'basil']

Time O(2ⁿ * n), so this is only practical for n up to about 20 to 25.

Recap

• AND tests and clears bits, OR sets them, XOR toggles them, shifts multiply or divide by powers of two.
• Bit masks pack many boolean flags into one integer with O(1) operations.
• x & (x - 1) drops the lowest set bit; use it for power-of-two checks and counting.
• XOR cancels pairs, finding a unique or missing value in O(1) space.
• Looping mask from 0 to 2ⁿ - 1 enumerates every subset.

# Write your solution here