Bit Manipulation

Every integer is stored as a pattern of bits, binary digits that are 0 or 1. Bit manipulation means working with those bits directly. It lets you store a set of yes/no flags in one number, test properties such as "is this a power of two?" in a single step, and solve some interview puzzles in O(1) extra space that would otherwise need a dictionary.

In this lesson you will read and write binary in Python, learn the six bitwise operators, use a handful of classic tricks, store sets of options as bitmasks, generate every subset with a counter and solve problems with XOR.

Binary in Python

In binary, each position is a power of two: the rightmost bit is worth 1, then 2, 4, 8 and so on. So 1011 in binary is 8 + 0 + 2 + 1 = 11. Python can convert both ways and write binary literals with the 0b prefix:

n = 45
print(bin(n))                    # '0b101101'
print(f"{n:08b}")                # padded to 8 bits
print(int("101101", 2))          # binary text -> int
print(0b1111, 0xFF)              # binary and hexadecimal literals
print(n.bit_length())            # bits needed to write 45
print(n.bit_count())             # how many 1 bits (Python 3.10+)

0b101101
00101101
45
15 255
6
4

bit_count() counts the 1 bits, often called the popcount. It was added in Python 3.10; in older code you will see bin(n).count("1"), which does the same thing more slowly.

The bitwise operators

The bitwise operators work on each bit position separately:

Shifting left by k multiplies by 2ᵏ; shifting right by k divides by 2ᵏ and rounds down. Python integers have no fixed size, so 1 << 100 is fine, and ~x is always -x - 1 (Python behaves as if negative numbers had infinitely many 1 bits on the left).

a, b = 0b1100, 0b1010
print(a & b, a | b, a ^ b)
print(f"{a & b:04b} {a | b:04b} {a ^ b:04b}")
print(~a, 5 << 3, 100 >> 2, -7 >> 1)

8 14 6
1000 1110 0110
-13 40 25 -4

Note -7 >> 1 is -4, not -3: right shift rounds down, like //.

Classic bit tricks

These one-liners appear constantly in interviews and in low-level code:

def is_odd(n):          return n & 1 == 1
def is_power_of_two(n): return n > 0 and n & (n - 1) == 0
def lowest_set_bit(n):  return n & -n
def get_bit(n, i):      return (n >> i) & 1
def set_bit(n, i):      return n | (1 << i)
def clear_bit(n, i):    return n & ~(1 << i)
def toggle_bit(n, i):   return n ^ (1 << i)

def count_ones_kernighan(n):
    count = 0
    while n:
        n &= n - 1          # removes the lowest 1 bit
        count += 1
    return count

print([x for x in range(1, 70) if is_power_of_two(x)])
print(is_odd(77), lowest_set_bit(40), f"{40:b}")
n = 0b10010
print(get_bit(n, 1), f"{set_bit(n, 0):b}", f"{clear_bit(n, 4):b}", f"{toggle_bit(n, 2):b}")
print(count_ones_kernighan(255), (255).bit_count())

[1, 2, 4, 8, 16, 32, 64]
True 8 101000
1 10011 10 10110
8 8

Why does n & (n - 1) work? Subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1. AND-ing with the original then clears exactly that lowest 1 bit. A power of two has only one 1 bit, so the result is 0. Brian Kernighan's counting loop uses the same step and runs once per 1 bit, not once per bit position.

Bitmasks: a set in one number

A bitmask uses each bit as a yes/no flag. File permissions on Linux are a well known example: read is 4 (100), write is 2 (010) and execute is 1 (001), so "read and write" is 4 | 2 = 6. With up to a few dozen options, a bitmask is a very compact set: union is |, intersection is &, and membership is one & test.

Python's enum.Flag gives the same idea readable names:

from enum import Flag, auto

READ, WRITE, EXECUTE = 4, 2, 1
mode = READ | WRITE
print(mode, bool(mode & WRITE), bool(mode & EXECUTE))
mode |= EXECUTE          # add a permission
mode &= ~WRITE           # remove one
print(mode, f"{mode:03b}")

class Topping(Flag):
    CHEESE = auto()
    PANEER = auto()
    ONION = auto()
    CORN = auto()

order = Topping.CHEESE | Topping.PANEER | Topping.CORN
print(Topping.ONION in order, Topping.PANEER in order)
print(order.value, f"{order.value:04b}")

6 True False
5 101
False True
11 1011

auto() gives each member the next power of two (1, 2, 4, 8), so every option owns one bit.

Generating subsets with a counter

With n items, the numbers from 0 to 2ⁿ - 1 cover every possible pattern of n bits, and each pattern is one subset: bit i says whether item i is in. This produces all subsets with a simple loop, no recursion needed (compare with Backtracking).

Kabir has ₹400 and can choose from four snacks at a cinema. Which combinations fit his budget?

snacks = [("popcorn", 250), ("cola", 120), ("nachos", 180), ("samosa", 60)]
budget = 400
n = len(snacks)

options = []
for mask in range(1 << n):                      # 0 to 15
    chosen = [snacks[i] for i in range(n) if mask >> i & 1]
    cost = sum(price for _, price in chosen)
    if cost <= budget and mask.bit_count() >= 2:
        options.append((cost, [name for name, _ in chosen]))

for cost, names in sorted(options, reverse=True)[:5]:
    print(cost, names)
print(len(options), "combinations of 2 or more snacks fit")

370 ['popcorn', 'cola']
360 ['cola', 'nachos', 'samosa']
310 ['popcorn', 'samosa']
300 ['cola', 'nachos']
240 ['nachos', 'samosa']
6 combinations of 2 or more snacks fit

mask >> i & 1 reads bit i of the mask (the shift happens before the &). This method is O(2ⁿ × n), so it only suits small n, up to about 20. Bitmasks also power an advanced technique called bitmask DP, where the DP state includes "which items have been used so far" as one integer.

XOR puzzles

XOR has three properties that make it special: x ^ x == 0, x ^ 0 == x, and the order of XOR operations does not matter. So if you XOR a list of numbers in which every value appears twice except one, the pairs cancel out and only the single value is left.

from functools import reduce
from operator import xor

# Every locker key was issued twice except one; which locker has a single key?
issued = [14, 7, 22, 9, 7, 14, 31, 9, 22]
print(reduce(xor, issued))

# Roll numbers 1..10 should be present; one student is absent
present = [3, 7, 1, 10, 2, 9, 5, 4, 8]
missing = reduce(xor, range(1, 11)) ^ reduce(xor, present)
print("Absent roll number:", missing)

31
Absent roll number: 6

Both answers use O(n) time and O(1) extra space, where a dictionary of counts would need O(n) space. For the missing number, sum(range(1, 11)) - sum(present) also works in Python, but in languages with fixed-size integers a large sum can overflow while XOR never does.

Common mistakes

• Operator precedence across languages. Python applies & before ==, so n & 1 == 1 works. In C, C++ and Java, == comes first, so the same expression means n & (1 == 1). Write (n & 1) == 1 with brackets so the code is clear in every language.
• Expecting ~5 to be a small positive number. In Python it is always -6.
• Using bit tricks where clear code would do. n % 2 == 1 is just as fast in practice and easier to read; use bits when they genuinely simplify the problem.
• Enumerating subsets with bitmasks for large n. 2ⁿ grows explosively; 30 items already means over 100 crore subsets.

Key points

• bin(), int(text, 2) and f"{n:b}" convert to and from binary; bit_length() and bit_count() measure bits.
• &, |, ^, ~, << and >> work bit by bit; shifts multiply or divide by powers of two.
• n & (n - 1) clears the lowest 1 bit: it tests powers of two and counts bits quickly.
• A bitmask stores a set of flags in one integer; enum.Flag gives the flags names.
• Counting from 0 to 2ⁿ - 1 enumerates every subset of n items.
• XOR cancels pairs, finding a single unmatched or missing value in O(1) extra space.

DAYS = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]

def mask_of(days):
    m = 0
    for d in days:
        m |= 1 << DAYS.index(d)
    return m

def names(mask):
    return [DAYS[i] for i in range(7) if mask >> i & 1]

a = mask_of(DAYS[:6])
b = mask_of(["Mon", "Wed", "Fri", "Sun"])

print("Both:", names(a & b))
print("At least one:", (a | b).bit_count(), "days")
print("Only B:", names(b & ~a))

Both: ['Mon', 'Wed', 'Fri']
At least one: 7 days
Only B: ['Sun']