Bit Manipulation

Learn about Bit Manipulation with interactive visualizations and depth. Master AND, OR, XOR, shifts, and hardware-level operations for problem optimization.

1. The Hook: Speaking the CPU’s Native Language

Imagine you are building a high-performance network switch or a massive-scale database like Redis. You need to track the boolean state of millions of users (e.g., “is online”) while minimizing memory and maximizing CPU throughput. If you store each state as a standard Boolean (which typically consumes 1 whole Byte, or 8 bits, due to memory addressing), you are wasting 87.5% of your memory!

Bit manipulation is the art of packing data densely and manipulating it instantly. It is not just a trick for coding interviews; it is how the CPU actually thinks. Every number is fundamentally a sequence of 0s and 1s. Manipulating them directly using logical gates is the fastest operation a computer can perform, bypassing heavy Arithmetic Logic Unit (ALU) cycles and complex branching logic.

2. Interactive Bit Lab

To truly understand bits, you have to play with them. Below is an 8-bit simulator. Toggle the bits to see how the decimal integer value changes.

8-Bit Toggle Sandbox

Decimal: 0

3. The Essentials: Operators Truth Table

Here are the primary tools in your bitwise arsenal.

| Operator | Symbol | Description | Analogy | | :— | :— | :— | :— | | AND | & | Returns 1 only if both bits are 1. | Like a strict bouncer: you need an ID and a ticket to enter. | | OR | \| | Returns 1 if at least one bit is 1. | Like an open party: either an ID or a ticket gets you in. | | XOR | ^ | Returns 1 only if the bits are different. | Like a light switch: toggling it changes the state. | | NOT | ~ | Inverts all bits (0s become 1s, 1s become 0s). | Like a photographic negative. | | Left Shift | << | Shifts bits left, filling with 0s. Mathematically: $x \times 2^k$. | Pushing a line of people forward. | | Right Shift | >> | Shifts bits right. Mathematically: $\lfloor x / 2^k \rfloor$. | Pushing a line of people backward. |

Watch out for Arithmetic vs. Logical Right Shift! In languages like Java, >> preserves the sign bit (Arithmetic shift), while >>> fills with 0s regardless of sign (Logical shift). C++ behavior for negative numbers using >> is implementation-defined!

4. The Magic Tricks: Bitwise Idioms

These are standard idioms every Senior Engineer recognizes on sight.

A. Extract the Lowest Set Bit (LSB)

Formula: x & -x

Why does this work? In Two’s Complement representation, -x is achieved by flipping all the bits of x (~x) and adding 1. This cascading addition flips all trailing 1s back to 0s until it hits the first 0, which it turns to a 1. That 1 perfectly aligns with the lowest 1 in the original x.

Step-by-Step: 10 & -10

Hover to see the binary extraction of the LSB.

  • x = 10 (00001010)
  • ~x = 245 (11110101)
  • -x = ~x + 1 = (11110110)
  • x & -x = 00000010 (which is 2)

Use Case: This is the foundational operation for navigating Fenwick Trees (Binary Indexed Trees).

B. Clear the Lowest Set Bit

Formula: x & (x - 1)

Subtracting 1 from a number flips its lowest set bit and all bits to the right of it. ANDing this with the original number clears that bit entirely.

  • Analogy: Imagine a line of dominos. Subtracting 1 knocks down the lowest standing domino. ANDing the result clears it away.
  • Use Case: Brian Kernighan’s Algorithm for counting set bits in $O(k)$ time (where $k$ is the number of set bits, much faster than $O(\log N)$). Also, checking if a number is a power of 2: if ((x > 0) && ((x & (x - 1)) == 0))!

C. The XOR Swap

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

XOR has two magical properties:

  1. Self-Inverse: A ^ A = 0
  2. Identity: A ^ 0 = A

By leveraging these, you can swap two variables without needing a temporary allocation. While modern compilers optimize temp variables away anyway, understanding why this works proves your grasp of XOR associativity.

5. Hardware Truth: The ALU

Why go to all this trouble? Let’s look inside the CPU.

When you write a + b, the CPU routes this through an adder circuit in the ALU (Arithmetic Logic Unit). An adder requires carry propagation—the result of bit 0 might affect bit 1, and so on. This takes time (propagation delay).

When you write a & b or a ^ b, the CPU routes it through parallel logical gates. Every bit is evaluated simultaneously and entirely independently. It is mathematically impossible for an operation to be faster in a classical computer.

Furthermore, consider branching:

// Slower: branching logic
if (x % 2 == 1) { ... }

// Faster: direct bitwise operation
if ((x & 1) == 1) { ... }

The modulo operator %% is a complex division instruction. More importantly, heavy branching logic can cause a Branch Misprediction in the CPU’s instruction pipeline, costing 10-20 CPU cycles to flush and reload. Bitwise operations are deterministic and branchless.

6. Case Study: The Single Number Problem

Let’s apply this to a real problem using the PEDALS framework.

The Problem

You are given an array of integers where every element appears exactly twice, except for one element which appears exactly once. Find that single one. Constraint: You must implement a solution with a linear runtime complexity and use only constant extra space.

Process Requirements

  • We must find the unique number.
  • O(N) time complexity.
  • O(1) space complexity (no HashMaps!).

Data Model & Architecture

If we used a HashMap, we could track counts, but that violates O(1) space. What if we use our bitwise superpowers? Recall the magical properties of XOR:

  • A ^ A = 0 (Two identical numbers cancel each other out).
  • A ^ 0 = A (Any number XOR’d with 0 remains unchanged).
  • XOR is commutative and associative: A ^ B ^ A = (A ^ A) ^ B = 0 ^ B = B.

Scale & Execution

We simply XOR all numbers together. All pairs will cancel out to 0, leaving only the single unique number!

public int singleNumber(int[] nums) {
  int result = 0;
  for (int num : nums) {
    result ^= num;
  }
  return result;
}

This elegant solution scans the array once (O(N)) and uses only a single integer variable for memory (O(1)). It perfectly demonstrates how low-level bit manipulation yields optimal high-level algorithmic efficiency.