Concepts

Bit manipulation treats an integer as a row of 0s and 1s and reads or changes individual positions directly. The CPU already stores integers in binary, so AND, OR, XOR and shifts usually compile to a single instruction. That makes bit tricks fast and compact, and it lets you express sets of on/off facts in very little code. This chapter covers binary representation, two's complement, the core operators and the vocabulary used in later chapters.

Binary representation

The integer 13 is 1101 in binary. The rightmost position is bit 0, and bit i is worth 2^i, so 1101 means 8 + 4 + 0 + 1.

Bit 0 is the least significant bit (LSB); the leftmost 1 is the most significant bit (MSB).

print(bin(13))             # 0b1101
print(format(13, "08b"))   # 00001101 (padded to 8 digits)
print(int("1101", 2))      # 13
print((13).bit_length())   # 4 bits needed

Two's complement

Almost every machine stores negative integers in two's complement: in n bits, -x is "flip every bit of x, then add 1", that is ~x + 1. With 8 bits, 5 is 00000101 and -5 is 11111011. One adder handles both signs and zero has a single encoding. An n-bit signed integer covers -2^(n-1) to 2^(n-1) - 1, so a 32-bit int runs from -2147483648 to 2147483647. A set top bit means the value is negative.

Core operators

x << k equals x * 2^k, and for non-negative x, x >> k equals x // 2^k. Because of two's complement, ~x == -x - 1.

a, b = 12, 10
print(a & b, a | b, a ^ b)   # 8 14 6
print(~a)                    # -13
print(3 << 2, 12 >> 2)       # 12 3
print(-12 >> 1)              # -6: arithmetic shift keeps the sign

Working with a single bit

All four basic single-bit operations use the mask 1 << i:

• set: x | (1 << i)
• clear: x & ~(1 << i)
• toggle: x ^ (1 << i)
• test: (x >> i) & 1, or (x & (1 << i)) != 0

x = 0b1010
print(bin(x | (1 << 0)))    # 0b1011
print(bin(x & ~(1 << 1)))   # 0b1000
print(bin(x ^ (1 << 3)))    # 0b10
print((x >> 3) & 1)         # 1

When to reach for it

• Representing a set of about 20 items as one integer and visiting every subset
• Packing many on/off states (permissions, options, feature flags) into one value
• Fast checks: power of two, odd or even, remainder modulo 2^k via x & (2^k - 1)
• XOR puzzles where every value appears in pairs except one

Vocabulary

• Mask: an integer with only the bits of interest set. A mask that encodes a set is a bitmask.
• Popcount: the number of 1 bits, also called the Hamming weight.
• Lowest set bit: the rightmost 1, obtained with x & -x.
• Logical vs arithmetic shift: a right shift that fills with zeros is logical; one that copies the sign bit is arithmetic.

Differences between languages

The same expression can behave differently across languages. Python integers are unbounded, so 1 << 100 is exact, and negatives act as if they had infinitely many leading 1s. JavaScript converts operands to 32-bit signed integers first, so 1 << 31 is negative and >>> 0 reads a result as unsigned. Java's int is also 32 bits, with >>> as the zero-filling shift. In C++, unsigned types keep you clear of overflow and undefined behavior. The implementation and real-world chapters cover the details.

Summary

Bit manipulation views integers as bit arrays and works on them with AND, OR, XOR, NOT and shifts. Negative numbers use two's complement, so -x == ~x + 1. Once set, clear, toggle and test feel natural and you think in masks, subset enumeration and bitmask DP follow easily.