Bits: AND, OR, XOR and shifts

Numbers are bits underneath

Computers store integers in binary, base 2. Each position is a bit, and bit i is worth 2 to the power i. Bit 0 is the rightmost one. So 13 is 8 + 4 + 1, which is 1101 in binary. In Python, bin(13) gives '0b1101', int("1101", 2) gives 13, and f"{13:08b}" gives '00001101', padded to 8 digits.

The operators

Check, set, clear and toggle one bit

A mask is a number with 1s only in the positions you care about. 1 << i is a mask with only bit i set. Combine it with the right operator:

n = 0b1010                     # 10
print((n >> 1) & 1)            # check bit 1   Output: 1
print(n | (1 << 0))            # set bit 0     Output: 11
print(n & ~(1 << 3))           # clear bit 3   Output: 2
print(n ^ (1 << 2))            # toggle bit 2  Output: 14

The n & (n − 1) trick

Subtracting 1 from n flips its lowest 1 bit to 0 and turns all the 0s below it into 1s. AND-ing with n then removes exactly that lowest 1 bit. For 12 = 1100, 11 = 1011, and 12 & 11 = 1000 = 8.

A power of two (1, 2, 4, 8…) has exactly one 1 bit, so removing it leaves 0. The test is n > 0 and n & (n − 1) == 0; the n > 0 part rules out 0 and negative numbers. A related trick, n & −n, keeps ONLY the lowest 1 bit: 12 & −12 is 4.

Counting set bits

The number of 1 bits is called the popcount (population count). Three ways in Python: bin(n).count("1"); n.bit_count(), available since Python 3.10; or Brian Kernighan's method, which repeats n &= n − 1 until n is 0 and counts the steps. Kernighan's loop runs once per 1 bit, not once per bit, which interviewers like.

def count_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

print(count_bits(13), bin(13).count("1"), (13).bit_count())   # Output: 3 3 3

Warning: Python integers are unbounded

In Java, C++ and similar languages, an int has a fixed width such as 32 bits, and negative numbers use two's complement. Python integers grow as large as needed. They behave as if a negative number had infinitely many 1 bits on the left. This changes several things you may have learnt elsewhere.

print(~5)                    # Output: -6   (~x is always -x - 1)
print(bin(-5))               # Output: -0b101   (a sign, not two's complement)
print(-1 >> 1)               # Output: -1   (shifting a negative never reaches 0)
print(-5 & 0xFFFFFFFF)       # Output: 4294967291   (the 32-bit pattern of -5)

JavaScript goes the other way: its bitwise operators first convert numbers to 32-bit signed integers. So (2 ** 31) | 0 is −2147483648, and >>> is an extra "unsigned" right shift that fills with 0s: −1 >>> 0 is 4294967295.

Real use: permission flags

Many systems pack several yes/no settings into one number. Linux file permissions are the famous example: read = 4 (100), write = 2 (010), execute = 1 (001). chmod 7 means 111, all three; 6 is 110, read and write; 5 is 101, read and execute. chmod 754 gives the owner 7 (rwx), the group 5 (r-x) and everyone else 4 (r--). To test "can write?", check perms & 2 != 0. Feature flags in apps and settings in games are often stored the same way.

Common mistakes

• Writing 2 ^ 3 for "two to the power three". In Python and JavaScript, ^ is XOR, so 2 ^ 3 is 1. Fix: 2 ** 3, or 1 << 3.
• Forgetting brackets in JavaScript, Java or C: there, n & 1 == 0 means n & (1 == 0). Python happens to group it as (n & 1) == 0, but brackets make every language safe.
• Testing a power of two without n > 0, so 0 passes. Fix: n > 0 and n & (n − 1) == 0.
• Expecting ~x or bin(x) to show 32-bit patterns in Python. Fix: mask with & 0xFFFFFFFF.
• Off by one with bit positions: the rightmost bit is bit 0, not bit 1.