Bit Manipulation: tricks with bits

Цели урока

• Understand AND, OR, XOR, NOT and shifts
• Apply tricks: power-of-two check, popcount, bit manipulation
• Solve problems with XOR (Single Number and variations)
• Use bitmasks for sets and DP

Предварительные знания

• Binary number system
• Basic programming

Bit operations are the language of the CPU. They are the fastest operations and often yield compact solutions.

• XOR tricks are a favourite topic in FAANG interviews
• Bitmask DP turns exponential problems into tractable ones

HAKMEM and Kernighan's bit trick

Bit tricks come from an era when every CPU cycle and every byte of memory counted. In 1972 the MIT AI Lab produced the famous HAKMEM collection (AI Memo 239), where Bill Gosper and colleagues gathered dozens of clever bit and arithmetic hacks. One of the best known, counting set bits with the expression n & (n - 1) that clears the lowest set bit in a single step, is often tied to Brian Kernighan's name. These tricks still live on in low-level code, cryptography, and coding interviews.

Why Bit Operations?

Bit operations work directly with the **atoms of information**. Each bit is 0 or 1, on/off, yes/no. They let you manipulate these atoms directly, bypassing all abstractions.

Bit operations are the **fastest operations** a computer can do. They execute in 1 CPU cycle - faster than addition, multiplication, or division.

**Why does this matter in practice?**

1. **Memory savings**: instead of an array of 32 booleans (32 bytes), use one 32-bit integer (4 bytes). 8× smaller!

2. **Speed**: operate on 32 flags in 1 cycle instead of 32 separate checks.

3. **Compactness**: some problems collapse to a couple of bit operations instead of loops.

**Metaphor: a control panel**

Take a panel with 8 switches. Each can be ON (1) or OFF (0). The state of the whole panel is an 8-bit number. For example, if switches 0, 2, and 3 are on:

Bit operations let you: turn switches on, turn them off, toggle them, check their state - all in O(1).

Basic Operations: AND, OR, XOR, NOT

There are 4 basic bitwise operations. Each works on bits **independently** - bit 0 of one number with bit 0 of the other, bit 1 with bit 1, and so on.

**AND (&) - logical AND**

Result = 1 only if **both** bits = 1. Like a bouncer: lets you in only if you have BOTH a ticket AND an ID.

**OR (|) - logical OR**

Result = 1 if **at least one** bit = 1. Like a two-way light switch: the light is on if either switch is on.

**XOR (^) - exclusive OR**

Result = 1 if the bits **differ**. XOR has the most interesting set of properties among bit operations.

**NOT (~) - bitwise negation**

Flips all bits: 0 → 1, 1 → 0.

Remember: AND for checking/clearing bits, OR for setting bits, XOR for toggling and clever tricks.

Shifts: Multiply and Divide Without Multiplication

**Left shift (<<)** - shifts all bits left, fills zeros from the right. This is **multiplication by a power of two**.

Why? Think of decimal: 5 × 10 = 50 (appended a zero on the right). In binary: appending a zero on the right multiplies by 2.

**Right shift (>>)** - shifts bits right, discards the rightmost bits. This is **division by a power of two** (rounding down).

Shifts are 10-100× faster than regular division. Compilers automatically replace n * 2 with n << 1.

**Creating a mask: 1 << i**

The expression `1 << i` produces a number with a single 1-bit at position i. This is a 'mask' for working with a specific bit.

Practical Bit Tricks

Now let's put the knowledge to work. Here are the most useful bit patterns.

**1. Parity check: n & 1**

The last bit (bit 0) determines parity. If it is 0 - the number is even; if 1 - odd.

**2. Power-of-two check: n & (n - 1) === 0**

A classic bit trick. Powers of two have exactly one 1-bit. And n - 1 flips all bits from that 1 down to zero:

**3. Working with individual bits**

**4. Counting set bits (popcount)**

Kernighan's algorithm does exactly k iterations, where k is the number of set bits. For sparse numbers this is much faster.

XOR Magic: the Single Number Problem

XOR has unique properties that make it incredibly useful for certain problems.

**Three key XOR properties:**

**Classic problem: Single Number (LeetCode #136)**

Given an array where every number appears **twice** except one unique number. Find that unique number.

Naive solution: HashMap for counting - O(n) memory. But with XOR we can do it in O(1) memory!

**Visualization: why pairs disappear**

**Other uses of XOR:**

XOR is a 'reversible' operation. If you know a ^ b = c, you can recover a = c ^ b or b = c ^ a. This is the basis of XOR encryption.

Bitmasks: a Set in a Single Number

A **bitmask** is using an integer as a **set**. Each bit represents one element: 1 = element present, 0 = element absent.

**Example: set {0, 2, 3}**

**Set operations via bits:**

**Practical example: generating all subsets**

**Bitmask DP: TSP in O(n² × 2^n)**

The Traveling Salesman Problem is normally O(n!), but with bitmasks it reduces to O(n² × 2^n). Idea: dp[mask][i] = minimum path visiting the cities in mask, ending at city i.

Bitmask works for n ≤ 20-25 (2^25 ≈ 33M states). For larger n, approximate algorithms are needed.

Итоги

• AND (&) - for checking and clearing bits
• OR (|) - for setting bits
• XOR (^) key identity: a^a=0, a^0=a
• Shifts - fast multiply/divide by powers of 2
• n & (n-1) removes the lowest set bit
• Bitmask - a set represented as a single integer

Related Topics

Bits connect to CPU architecture and cryptography

• CPU Architecture — Bit operations are the base level
• Cryptography — XOR encryption
• Data Compression — Efficient encoding

Связанные уроки

• ds-24-bloom-filter — Bloom filters set and test individual bits
• alg-22-backtracking — Bitmask DP encodes visited subsets as bits
• crypto-14-aes — Block ciphers are built from bit operations
• dm-01 — Bitwise AND, OR, XOR realize Boolean algebra
• comp-01-intro