Bit Manipulation

18 Mar 2026

Introduction

So far, we have been working with abstract high-level concepts: objects, arrays, pointers, and hash maps.

But beneath all of that, a computer only understands two things: ON and OFF. 1 and 0.

Integers in Java (and most languages) are represented by 32 bits. The number 5 is not stored as a generic concept of “five”. It is stored in binary as 00000000 00000000 00000000 00000101.

Bit Manipulation is the art of using special operators to change these 1s and 0s directly. Why would you want to do this? Because bitwise operations execute at the hardware processor level, making them the fastest operations the computer can possibly perform.

The Core Operators

Here are the tools you have to manipulate bits:

1. AND (`&`)

Returns 1 only if both bits are 1. It is useful for masking (turning specific bits off).

  0101 (5)
& 0011 (3)
-------
  0001 (1)

2. OR (`|`)

Returns 1 if either bit is 1 (or both). It is useful for setting specific bits to 1.

  0101 (5)
| 0011 (3)
-------
  0111 (7)

3. XOR (`^` Exclusive-OR)

Returns 1 if the bits are different, and 0 if they are the same. XOR is essentially a “toggle” switch. Note two crucial properties of XOR:

Any number XOR itself is 0: A ^ A = 0
Any number XOR 0 is itself: A ^ 0 = A
```
0101 (5)
^ 0011 (3)
-------
0110 (6)
```

4. Left Shift (`<<`)

Shifts all bits to the left, adding 0s on the right. Shifting left by 1 is the same as multiplying by 2. 00000101 (5) << 1 becomes 00001010 (10).

5. Right Shift (`>>`)

Shifts all bits to the right. Shifting right by 1 is the same as integer division by 2. 00000101 (5) >> 1 becomes 00000010 (2).

Classic Bit Manipulation Tricks

Bit manipulation seems like obscure voodoo until you see how elegantly it solves specific problems.

Trick 1: Checking if a number is Even or Odd

You could use the modulo operator (x % 2 == 0). But modulo involves division, which is mathematically slow. Look at binary numbers: 2 is 0010, 4 is 0100, 5 is 0101, 9 is 1001. Notice anything? If the rightmost bit is 1, the number is odd. If it’s 0, the number is even.

We can use the & operator to isolate the rightmost bit:

public boolean isEven(int n) {
    return (n & 1) == 0;
}

Trick 2: Brian Kernighan’s Algorithm (Counting 1s)

How many 1 bits are in a number? You could shift right and check the last bit 32 times. But Brian Kernighan discovered a trick: n & (n - 1) always flips the lowest (rightmost) 1 bit to a 0.

Let n = 12 (1100). 12 & 11 $\rightarrow$ 1100 & 1011 = 1000 (The rightmost 1 vanished!).

public int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1); // Delete the rightmost '1'
        count++;
    }
    return count;
}

If the number has only three 1s, this loop runs exactly 3 times, not 32 times. Incredibly efficient.

Trick 3: Checking if a number is a Power of 2

Powers of 2 in binary only ever have a single 1 bit. 2 = 0010, 4 = 0100, 8 = 1000.

Using the trick above, if we remove the rightmost 1 from a power of 2, the number must immediately become 0.

public boolean isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

Example Problem: Single Number

This is the most famous bit manipulation interview question. Problem: Given an array of integers where every element appears exactly twice except for one, find that single one. You must do it in $O(n)$ time and $O(1)$ extra space.

Array: [4, 1, 2, 1, 2]

A Hash Map takes $O(n)$ extra space.
Sorting takes $O(n \log n)$ time.

The XOR Solution: Remember the two properties of XOR? A ^ A = 0 and A ^ 0 = A. Because XOR is commutative (order doesn’t matter), if we XOR all the numbers in the array together, the duplicates will cancel each other out to 0. The only thing left will be the single number!

4 ^ 1 ^ 2 ^ 1 ^ 2 $\rightarrow$ (1 ^ 1) ^ (2 ^ 2) ^ 4 $\rightarrow$ 0 ^ 0 ^ 4 $\rightarrow$ 4.

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

This is a mathematically beautiful $O(n)$ time, $O(1)$ space solution.

Practice Problems

Single Number – LeetCode #136 — The problem we just solved. Write it out yourself!
Number of 1 Bits – LeetCode #191 — Implement Brian Kernighan’s Algorithm.
Missing Number – LeetCode #268 — An array contains n distinct numbers taken from 0, 1, 2, ..., n. One is missing. Try solving this cleverly with XOR.

What’s Next?

We just finished Phase 4! We have covered the most powerful algorithmic techniques: DP, Greedy, Backtracking, Recursion, and Bit Manipulation.

Next, we enter Phase 5: The Final Challenges, where we tackle the hardest graph algorithm (A* Search) and complex string searching algorithms to cap off the series. Let the real games begin!