20 — Bit Manipulation

Bit problems are pattern recall, not derivation. Learn what the operators do, learn eight tricks, and the section becomes mechanical.

Java specifics matter more here than anywhere else: int is a signed 32-bit two's-complement value, and Java has no unsigned int.

Binary, briefly

Every integer is stored as bits — powers of two:

  13  =  0000 1101
          │    ││└─ 1  (2^0)
          │    │└── 0  (2^1)
          │    └─── 1  (2^2) = 4
          └──────── 1  (2^3) = 8      →  8 + 4 + 1 = 13

Negative numbers use two's complement: flip every bit of the positive value and add 1. The leftmost bit is then the sign bit — 1 means negative.

   5  =  0000 0000 ... 0000 0101
  -5  =  1111 1111 ... 1111 1011

Why two's complement: addition works identically for positive and negative numbers, so the hardware needs only one adder. It's also why the range is asymmetric — there's one more negative value than positive, and hence why -Integer.MIN_VALUE overflows (03).

Operators

  12  =  1100
   10 =  1010
       --------
12 & 10 = 1000  = 8      (only where both are 1)
12 | 10 = 1110  = 14     (where either is 1)
12 ^ 10 = 0110  = 6      (where they differ)

>> vs >>> — the Java-specific trap

-8 >> 1;    // -4            arithmetic: copies the sign bit inward
-8 >>> 1;   // 2147483644    logical: fills with 0

>> preserves the sign by shifting in copies of the leftmost bit. That's correct for division, but it means -1 >> 1 is still -1 — so a loop like while (n != 0) n >>= 1; never terminates on a negative number.

When walking over all 32 bits of a possibly-negative int, use >>>.

XOR — the property that solves half the section

x ^ x = 0        a value cancels itself
x ^ 0 = x        identity
XOR is commutative and associative — order doesn't matter

Put together: XOR everything, and all paired values vanish, leaving only the unpaired one.

Single Number

Every element appears twice except one. Find it.

int res = 0;
for (int n : nums) res ^= n;
return res;

Trace: [4, 1, 2, 1, 2]

0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4      ← the answer

Because XOR is commutative, the order doesn't matter — you can mentally rearrange to (1^1) ^ (2^2) ^ 4 = 0 ^ 0 ^ 4 = 4.

O(n) time, O(1) space — which is what the question is actually testing. A HashSet solution works but uses O(n) space.

Missing Number

Numbers 0..n with one missing.

int res = nums.length;               // seed with n — the index that has no array slot
for (int i = 0; i < nums.length; i++) res ^= i ^ nums[i];
return res;

Why: you XOR together every index 0..n-1, every value present, and n. Each number that is present appears once as a value and once as an index — cancelling. The missing one appears only as an index and survives.

The alternative: Gauss sum, n*(n+1)/2 - actualSum. Equally valid and arguably clearer.

Why XOR is preferable: the sum can overflow for large n, while XOR never can. Mention the overflow-safety — it's the reason to choose it.

The eight tricks

x & 1                  // is x odd?
x >> 1                 // x / 2 (for non-negative x)
x & (1 << i)           // is bit i set?  (non-zero if yes)
x | (1 << i)           // set bit i
x & ~(1 << i)          // clear bit i
x ^ (1 << i)           // toggle bit i

x & (x - 1)            // clear the LOWEST set bit      <- the important one
x & (-x)               // isolate the lowest set bit

Why x & (x - 1) clears the lowest set bit

Subtracting 1 flips the lowest set bit to 0 and turns everything below it into 1s:

  x     = 1011 0100
  x - 1 = 1011 0011      ← lowest 1 became 0, the zeros below became 1s
  ------------------
  AND   = 1011 0000      ← exactly the lowest set bit removed

Number of 1 Bits — loops once per set bit rather than 32 times:

int count = 0;
while (n != 0) { n &= (n - 1); count++; }
return count;

For n = 8 (1000) this runs once, not 32 times.

Also: x & (x - 1) == 0 tests whether x is a power of two — powers of two have exactly one set bit, so removing it leaves 0.

Integer.bitCount(x) does this in one call. Write the loop to show the mechanic, then mention the built-in.

Counting Bits — DP over bits

Count the set bits of every number from 0 to n.

The O(n log n) answer calls bitCount per number. The O(n) answer reuses earlier results:

int[] dp = new int[n + 1];
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);          // bits of i/2, plus the bit i just dropped
}
return dp;

Why: i >> 1 is i with its lowest bit removed. So i has all the bits of i >> 1, plus possibly one more — which is exactly i & 1.

Trace:

✓

Equivalent form using the clear-lowest-bit trick:

dp[i] = dp[i & (i - 1)] + 1;               // one more bit than i with its lowest bit cleared

Both O(n). Being able to give both is better than either alone.

Reverse Bits

Pull the low bit off the input, push it onto the accumulator.

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1);        // shift result left, append n's lowest bit
        n >>>= 1;                          // LOGICAL shift — n may be negative
    }
    return res;
}

Reading it: each iteration takes n's lowest bit and appends it as res's lowest bit, having first shifted everything in res up. After 32 rounds the order is exactly reversed.

n >>>= 1 is mandatory. With >>, a negative n sign-extends forever and you'd read 1-bits that aren't there.

Complexity is O(1) — 32 is a fixed constant, not a function of the input. Say that explicitly; calling it O(log n) is defensible but O(1) for fixed-width ints is the expected answer.

Sum of Two Integers — addition without +

The decomposition:

• XOR gives the sum ignoring carries (1 + 1 = 0 with a carry, which is what XOR does).
• AND then shift left gives exactly the carries (1 & 1 = 1, carried into the next column).

Repeat until there are no carries left.

public int getSum(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;      // bits where BOTH are 1 carry into the next position
        a = a ^ b;                     // sum ignoring carries
        b = carry;                     // now add the carry in
    }
    return a;
}

Trace 3 + 5:

a = 011, b = 101
  carry = (011 & 101) << 1 = 001 << 1 = 010
  a = 011 ^ 101 = 110
  b = 010

a = 110, b = 010
  carry = (110 & 010) << 1 = 010 << 1 = 100
  a = 110 ^ 010 = 100
  b = 100

a = 100, b = 100
  carry = (100 & 100) << 1 = 1000
  a = 100 ^ 100 = 000
  b = 1000

a = 000, b = 1000
  carry = 0
  a = 1000 = 8     ✓
  b = 0  → loop ends

Walk this on the whiteboard — it convinces far faster than explaining.

Termination: each round shifts the carry left, so carries march toward the high end and eventually fall out of the 32-bit word. Two's-complement arithmetic makes this work uniformly for negatives.

Reverse Integer — really an overflow question

Reverse the digits of a 32-bit int; return 0 if the result overflows.

public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int digit = x % 10;                          // Java keeps the sign: -123 % 10 == -3
        x /= 10;

        // check BEFORE multiplying
        if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) return 0;
        if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && digit < -8)) return 0;

        res = res * 10 + digit;
    }
    return res;
}

Three things to state:

1. Java's % keeps the sign of the dividend. -123 % 10 is -3, so negatives need no special casing — unlike Python, where it would be 7.

2. Check before multiplying, not after. Once the overflow happens, the value has already wrapped — there's nothing left to detect. Testing res > MAX/10 asks "would multiplying by 10 push me over?" in advance.

3. Where 7 and 8 come from: they're the last digits of 2147483647 and -2147483648. If res exactly equals MAX/10, then one more digit fits only if that digit doesn't exceed the final 7. Deriving them on the spot reads better than quoting them from memory.

A simpler alternative: accumulate in a long and compare at the end. Acceptable if the interviewer allows it — say you know it and are choosing the stricter version.

Bitmasks as sets

A 32-bit int is a set over up to 32 elements. Bit i being 1 means "element i is in the set."

This is why n ≤ 20 constraints suggest bitmask enumeration: 2^20 is about a million, entirely feasible.

int mask = 0;
mask |= (1 << i);                  // add element i
mask &= ~(1 << i);                 // remove element i
boolean has = (mask & (1 << i)) != 0;
int size = Integer.bitCount(mask);

// enumerate ALL 2^n subsets
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) { /* element i is in this subset */ }
    }
}

Each value of mask from 0 to 2^n - 1 corresponds to exactly one subset. This gives a non-recursive Subsets (15).

Valid Sudoku becomes an O(1) check per cell (06):

int[] rows = new int[9], cols = new int[9], boxes = new int[9];

int bit = 1 << (board[r][c] - '1');          // digit 1..9 -> bit 0..8
int box = (r / 3) * 3 + c / 3;

if ((rows[r] & bit) != 0 || (cols[c] & bit) != 0 || (boxes[box] & bit) != 0) return false;
rows[r] |= bit;  cols[c] |= bit;  boxes[box] |= bit;

Each int stores nine yes/no flags. No string building, no hashing — just arithmetic.

Java gotchas

1. Operator precedence. &, |, ^ bind looser than ==:

if (x & 1 == 1)      // parses as  x & (1 == 1)  -> doesn't compile
if ((x & 1) == 1)    // correct

Always parenthesize bitwise comparisons.

2. >>> for iteration over possibly-negative values.

3. 1 << 31 is negative. It sets the sign bit. Use 1L << 31 when you need the positive value.

4. Shift counts are taken mod 32 for int (mod 64 for long). So x << 32 == x, which is surprising and occasionally a real bug.

5. No unsigned int. Where a problem says "treat as unsigned", either use >>> throughout or widen to long with x & 0xFFFFFFFFL.

Useful built-ins: Integer.bitCount, Integer.toBinaryString, Integer.highestOneBit, Integer.numberOfTrailingZeros, Integer.reverse.

Recognition checklist

Complexity summary