Bit Manipulation

[!NOTE] This module explores the core principles of Bit Manipulation, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Concept: Speaking the CPU’s Language

Bit manipulation is not just for hackers. It’s how the CPU actually thinks. Every number is just a sequence of 0s and 1s. Manipulating them directly is the fastest operation a computer can perform.

2. The Essentials

Common Operators

& (AND): Both must be 1.
| (OR): At least one is 1.
^ (XOR): Different bits return 1. (My favorite).
~ (NOT): Flip all bits.
<< (Left Shift): Multiply by 2.
>> (Right Shift): Divide by 2.

3. The Magic Tricks

A. Extract the Lowest Set Bit (LSB)

Formula: x & -x

Example: 10 is 1010. -10 (Two’s complement) is 0110.
1010 & 0110 = 0010 (which is 2).
Use Case: Fenwick Trees (Binary Indexed Trees).

B. Clear the Lowest Set Bit

Formula: x & (x - 1)

Example: 1010 & 1001 = 1000.
Use Case: Counting set bits (Brian Kernighan’s Algorithm) or checking if a number is a power of 2.

C. XOR Swap

Formula: x ^= y; y ^= x; x ^= y;

No temp variable needed!

4. Hardware Truth: The ALU

Why is this faster than normal math? Inside the CPU, the ALU (Arithmetic Logic Unit) has specific circuits for these gates.

Addition: Requires carry propagation logic (slower).
Bitwise AND/OR/XOR: Parallel operation on all bits instantly (fastest possible instruction).
Branching: if (x % 2 == 1) might cause a Branch Misprediction in the instruction pipeline. x & 1 does not. It flows straight through.

5. Deep Dive Strategy Lab: Bit Manipulation

Intuition Through Analogy

Think of this chapter like optimizing a distributed service under SLO. The goal is not to memorize a fixed trick, but to repeatedly answer:

What is the bottleneck?
Which constraint dominates (time, memory, latency, correctness)?
Which representation makes the bottleneck easier to eliminate?