Bit Manipulation

Every integer in your program is a sequence of bits. Most of the time, you interact with those bits through arithmetic operators. But when you reach down and manipulate bits directly — flipping, masking, shifting — you unlock solutions that are faster, more memory-efficient, and often strikingly elegant. Let’s build this toolkit piece by piece.

Bitwise Operators in Java

Java provides seven bitwise operators. Here’s each one with its truth table and behavior:

AND (`&`) — Both bits must be 1

int a = 0b1100;  // 12
int b = 0b1010;  // 10
int result = a & b; // 0b1000 = 8

Each bit in the result is 1 only if both corresponding bits are 1. Use AND to mask out specific bits or test if a bit is set.

OR (`|`) — Either bit can be 1

int a = 0b1100;  // 12
int b = 0b1010;  // 10
int result = a | b; // 0b1110 = 14

Each bit in the result is 1 if at least one corresponding bit is 1. Use OR to set bits unconditionally.

XOR (`^`) — Bits must differ

int a = 0b1100;  // 12
int b = 0b1010;  // 10
int result = a ^ b; // 0b0110 = 6

Each bit in the result is 1 if the corresponding bits are different. XOR is the star of bit manipulation interviews — more on this shortly.

NOT (`~`) — Flip every bit

int a = 0b00000101;  // 5
int result = ~a;      // 0b11111010... = -6 (in 32-bit two's complement)

Inverts every bit. In two’s complement, ~n equals -(n + 1).

Left Shift (`<<`) — Multiply by powers of 2

int a = 3;           // 0b0011
int result = a << 2; // 0b1100 = 12 (3 × 2² = 12)

Shifts bits left by k positions, filling with 0s from the right. Equivalent to multiplying by 2^k.

Right Shift (`>>`) — Signed divide by powers of 2

int a = -12;          // 0b11110100 (in 8-bit for clarity)
int result = a >> 2;  // 0b11111101 = -3 (preserves sign bit)

Shifts bits right by k positions, filling with the sign bit from the left. Equivalent to dividing by 2^k and rounding toward negative infinity.

Unsigned Right Shift (`>>>`) — Zero-fill divide

int a = -1;            // 0xFFFFFFFF (all 32 bits set)
int result = a >>> 1;  // 0x7FFFFFFF = 2147483647

Shifts bits right by k positions, filling with 0s from the left regardless of the sign bit. Critical when treating integers as unsigned bit patterns.

Essential Bit Tricks

These patterns come up repeatedly. Internalize them.

Check if the kth bit is set

boolean isSet = ((n >> k) & 1) == 1;

Shift the target bit to position 0, then AND with 1 to isolate it.

Set the kth bit

n = n | (1 << k);

Create a mask with only the kth bit set, then OR it with n.

Clear the kth bit

n = n & ~(1 << k);

Create a mask with the kth bit cleared (all others set), then AND with n.

Toggle the kth bit

n = n ^ (1 << k);

XOR flips: if the bit was 1, it becomes 0; if 0, it becomes 1.

Check if power of 2

boolean isPowerOfTwo = n > 0 && (n & (n - 1)) == 0;

A power of 2 has exactly one bit set. Subtracting 1 flips that bit and sets all lower bits. AND produces zero only when the original had a single bit set. The n > 0 guard handles zero, which is not a power of 2.

Clear the lowest set bit

n = n & (n - 1);

Removes the rightmost 1-bit. This is the foundation of Brian Kernighan’s bit-counting algorithm.

Isolate the lowest set bit

int lowest = n & (-n);

In two’s complement, -n flips all bits and adds 1. The AND with n isolates the lowest set bit. This operation is the backbone of Fenwick trees (Binary Indexed Trees).

Count set bits (Brian Kernighan’s Algorithm)

int countSetBits(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1); // clear lowest set bit
        count++;
    }
    return count;
}

Each iteration removes exactly one set bit. Runtime: O(number of set bits) — far better than iterating through all 32 bits.

Java also provides the built-in Integer.bitCount(n) which uses a parallel bit-counting technique for O(1) performance.

XOR Properties

XOR has three properties that make it indispensable:

Self-inverse: a ^ a = 0 — XORing a value with itself cancels it out.
Identity: a ^ 0 = a — XORing with zero changes nothing.
Commutative and associative: order doesn’t matter.

These properties enable the classic swap trick:

// Swap x and y without a temporary variable
x ^= y;  // x = x ^ y
y ^= x;  // y = y ^ (x ^ y) = x
x ^= y;  // x = (x ^ y) ^ x = y

Neat for interviews, though in production code a temp variable is clearer and equally fast.

Classic Problems

1. Single Number

Problem: every element in the array appears twice except one. Find the unique element.

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

XOR all elements. Pairs cancel out (a ^ a = 0), leaving the single element. O(n) time, O(1) space.

2. Single Number II

Problem: every element appears three times except one. Find the unique element.

XOR alone won’t work because a ^ a ^ a = a, not 0. Instead, count bits:

int singleNumberII(int[] nums) {
    int result = 0;
    for (int bit = 0; bit < 32; bit++) {
        int sum = 0;
        for (int num : nums) {
            sum += (num >> bit) & 1;
        }
        if (sum % 3 != 0) {
            result |= (1 << bit);
        }
    }
    return result;
}

For each bit position, count how many numbers have that bit set. If the count isn’t divisible by 3, the unique number has that bit set. O(32n) = O(n) time, O(1) space.

3. Missing Number

Problem: array contains n distinct numbers from [0, 1, …, n]. One number is missing. Find it.

int missingNumber(int[] nums) {
    int xor = nums.length; // start with n
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}

XOR all indices (0 to n) with all array elements. Every number present pairs up and cancels, leaving the missing one.

4. Power of Two

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Already covered in the tricks section. Clean, O(1), and a favorite interview warm-up.

5. Counting Bits

Problem: for every number from 0 to n, compute the number of 1-bits.

int[] countBits(int n) {
    int[] result = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        result[i] = result[i & (i - 1)] + 1;
    }
    return result;
}

The recurrence: i has one more set bit than i & (i - 1) (which clears the lowest set bit). O(n) time, O(n) space.

6. Reverse Bits

Problem: reverse all 32 bits of an unsigned integer.

int reverseBits(int n) {
    int result = 0;
    for (int i = 0; i < 32; i++) {
        result = (result << 1) | (n & 1);
        n >>>= 1;
    }
    return result;
}

Extract the lowest bit of n, append it to result from the left. Repeat 32 times. Use >>> (unsigned right shift) to avoid sign extension.

7. Hamming Distance

Problem: count the number of positions where two integers differ in their binary representations.

int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y);
}

XOR highlights differing bits (they become 1), then bitCount counts them. One line.

Bitmask for Subset Enumeration

A bitmask of n bits can represent any subset of n elements. Bit i being 1 means element i is included.

For n elements, there are 2^n possible subsets — represented by integers from 0 to 2^n - 1.

void generateSubsets(int[] elements) {
    int n = elements.length;
    for (int mask = 0; mask < (1 << n); mask++) {
        var subset = new ArrayList<Integer>();
        for (int i = 0; i < n; i++) {
            if ((mask >> i & 1) == 1) {
                subset.add(elements[i]);
            }
        }
        System.out.println(subset);
    }
}

For elements = [1, 2, 3]:

mask = 0b000 (0) → []
mask = 0b001 (1) → [1]
mask = 0b010 (2) → [2]
mask = 0b011 (3) → [1, 2]
mask = 0b100 (4) → [3]
mask = 0b101 (5) → [1, 3]
mask = 0b110 (6) → [2, 3]
mask = 0b111 (7) → [1, 2, 3]

Bitmask DP

Bitmasks unlock dynamic programming on subsets. The Traveling Salesman Problem (TSP) and assignment problems use bitmask DP where the state includes which elements have been “used”:

// TSP: dp[mask][i] = minimum cost to visit all cities in 'mask', ending at city i
int[][] dp = new int[1 << n][n];

The state space is O(2^n × n), which is feasible for n ≤ 20 (about 20 million states). Without bitmask DP, the brute force is O(n!) — exponentially worse.

Enumerating Submasks of a Mask

To iterate over all submasks of a given mask (all subsets of a subset):

for (int sub = mask; sub > 0; sub = (sub - 1) & mask) {
    // process submask 'sub'
}
// Don't forget sub = 0 (empty subset) if needed

This technique is essential for bitmask DP optimizations where you split a set into two complementary subsets.

Two’s Complement

Java uses two’s complement for signed integers. Understanding this representation clarifies why certain bit tricks work.

For a 32-bit integer:

Positive numbers: standard binary representation.
Negative numbers: flip all bits and add 1. So -n = ~n + 1.
Range: -2³¹ to 2³¹ - 1 (i.e., -2,147,483,648 to 2,147,483,647).

Key consequences:

~n = -(n + 1) — bitwise NOT produces the algebraic negation minus one.
-n = ~n + 1 — this is why n & (-n) isolates the lowest set bit.
Overflow wraps around: Integer.MAX_VALUE + 1 == Integer.MIN_VALUE.

When working with bit manipulation, always remember Java’s int is 32 bits and long is 64 bits. Use long when bit positions exceed 31.

Interviewer Tips

XOR is the headliner. If an interviewer says “constant space” and the problem involves finding unique or missing elements, reach for XOR first.

Bitmask problems usually signal themselves with constraints like “n ≤ 20” — that 2^20 ≈ 1 million ceiling is the telltale sign.

The n & (n - 1) trick is a Swiss Army knife: power-of-two check, counting set bits, and clearing the lowest bit all derive from it.

Don’t memorize — understand. Know why n & (n - 1) clears the lowest set bit (subtracting 1 flips the lowest 1 and all trailing 0s). When you understand the mechanics, you can derive any trick on the spot.