Bit manipulation explained: operators, tricks and examples

What problem bit manipulation solves

An integer is a row of bits, and many problems are really about those bits: file permissions such as rwx, feature flags, network masks, pixel colors, compact sets of options, checksums and hashes. Bitwise operators let you read and change many bits at once in a single operation, which is compact in memory and very fast.

Interview questions also use bit tricks because they give elegant O(1)-space solutions, for example finding the one number that appears once when every other number appears twice.

The operators

Examples use a = 12 (binary 1100) and b = 10 (binary 1010).

a, b = 12, 10
print(bin(a), bin(b))         # 0b1100 0b1010
print(a & b, a | b, a ^ b)    # 8 14 6
print(~a, a << 1, a >> 2)     # -13 24 3
print(f"{a ^ b:04b}")         # 0110
print(int("1010", 2))         # 10

Single-bit operations

Bit positions are counted from 0 at the right (the least significant bit). The mask 1 << i has only bit i set.

Worked example: counting set bits

Brian Kernighan's method clears the lowest set bit until nothing is left, so it loops once per 1-bit, not once per bit position. Trace for x = 44 (binary 101100):

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

print(count_bits(44))     # 3
print((44).bit_count())   # 3
print((44).bit_length())  # 6

int.bit_count() is available since Python 3.10. int.bit_length() returns the number of bits needed to write the number in binary, without the sign.

Classic tricks in Python

from functools import reduce
from operator import xor

# Every number appears twice except one: pairs cancel out with XOR.
print(reduce(xor, [4, 1, 2, 1, 2]))   # 4

# Swap two integers without a temporary variable (for illustration only).
x, y = 5, 9
x ^= y; y ^= x; x ^= y
print(x, y)                            # 9 5

# Bitmask as a set: enumerate all subsets of 3 items.
items = ["a", "b", "c"]
for mask in range(1 << len(items)):
    print(mask, [items[i] for i in range(len(items)) if mask >> i & 1])
# 0 []
# 1 ['a']
# 2 ['b']
# 3 ['a', 'b']
# 4 ['c']
# 5 ['a', 'c']
# 6 ['b', 'c']
# 7 ['a', 'b', 'c']

Mask 0 is the empty set, 5 (binary 101) is ['a', 'c'], and 7 is all three items. Bitmask dynamic programming uses the same idea, with a mask as the state, for problems over up to about 20 items, such as the traveling salesman problem on small inputs.

Two more classics: x & 1 is 1 for odd numbers, and XOR of all numbers from 0 to n with all the values in a list finds the one missing number.

Time and space complexity

A bitmask uses one bit per possible element, so a set of 64 flags fits in a single 64-bit integer, compared with 64 separate boolean variables or list entries.

Common mistakes

• Negative numbers: Python integers behave as if they had infinitely many sign bits, so ~5 is -6 and bin(-5) is -0b101, not a two's complement string. To see 32-bit patterns, mask the value: -5 & 0xFFFFFFFF.
• Right shift of negative numbers in Python is arithmetic: -8 >> 1 is -4, and -1 >> 10 stays -1.
• Overflow in fixed-width languages: in Java or C, 1 << 31 on a 32-bit int becomes negative or undefined; use a 64-bit type and 1L << 40 or 1ULL << 40.
• Confusing logical and bitwise operators: and and or (&&, || in C-like languages) return truth values, while & and | work bit by bit.
• Readability: replacing x * 2 with x << 1 gives no speed benefit in modern compilers or in Python, and makes code harder to read.

Real-world uses

• Unix file permissions: chmod 754 sets three 3-bit groups (rwx = 4 + 2 + 1).
• Networking: IPv4 subnet masks, where ip & mask gives the network address of a CIDR block.
• Flags and options: Python's re.IGNORECASE | re.MULTILINE and enum.Flag combine options with OR.
• Graphics and colors: a 24-bit RGB value packs red, green and blue as (r << 16) | (g << 8) | b.
• Data structures and algorithms: Bloom filters, bitsets, Fenwick trees (which use i & -i), hashing and checksums.
• Interview problems: single number, counting bits, power of two, reverse bits, missing number, subsets via bitmask, sum of two integers without +.