Bit Manipulation & Math

Bit manipulation is where confident candidates suddenly go quiet. The operators are trivial, but two's complement, sign extension, and silent 32-bit overflow turn "easy" problems into wrong answers that compile and run. This session builds the vocabulary from the metal up — how an int is actually stored, what each operator really does — and then spends it on the interview regulars: counting set bits, the XOR single-number trick, powers of two, reversing bits, base conversion, and the "math" problems (LC 7 / 29 / 69 / 166 / 172) that are really overflow problems wearing arithmetic costumes.

How an Integer Actually Lives in Memory

A Java int is 32 bits — four bytes — and it is signed by default. The top bit is the sign (the most significant bit); the bottom bit is the least significant. That single sign bit is why the range is asymmetric: -2^31 to 2^31 - 1. Conversion is mechanical in both directions — binary → decimal is a weighted sum of powers of two (each bit times 2^i), and decimal → binary is repeated division by 2, reading off the remainders.

The idea that unlocks negatives is two's complement: to negate a number, flip every bit and add 1. The same recipe runs both ways — it turns 2 into -2 and -2 back into 2. Integer.MIN_VALUE is a lone sign bit, 1000…0, and it has no positive counterpart — which is exactly why Math.abs(Integer.MIN_VALUE) overflows and comes back negative. Memorize that landmine; half the "math" problems below are really about tiptoeing around it.

sign bit                                    least significant bit
   |                                                  |
   v                                                  v
   1 0 0 0 0 0 0 0 . . . . . 0 0 0 0 0 0 0   =  Integer.MIN_VALUE = -2^31
   0 1 1 1 1 1 1 1 . . . . . 1 1 1 1 1 1 1   =  Integer.MAX_VALUE =  2^31 - 1

negate a number:  flip every bit, then + 1     (two's complement)
    2  = 0000 . . . 0010
   ~2  = 1111 . . . 1101
   +1  = 1111 . . . 1110  = -2      // same recipe turns -2 back into 2

The Operator Cheat Sheet

Two families of operators look alike and behave nothing alike. The bitwise operators work on all 32 bits at once; the logical ones (&&, ||, !) work on a single boolean and short-circuit. Swapping them is a classic bug.

One naming trap worth fixing up front: ^ is exclusive-or (XOR), not inclusive-or — it returns 1 only when the two bits differ, and that "difference detector" is the entire reason XOR becomes a superpower two sections down. And the shift subtlety interviewers listen for: >> sign-extends (a negative stays negative), while >>> always feeds in 0. There is no <<< because a left shift already fills 0 on the right, so it would be identical to <<. Every one of these compiles down to a single hardware instruction — O(1).

The Bit Toolkit: Set, Clear, Check a Bit

Almost every bit problem decomposes into three primitives — set a bit, clear a bit, read a bit. Learn them as one-liners so you stop re-deriving them under interview pressure.

// x is the int, k is the bit index (0 = least significant)
int     setBit   = x | (1 << k);          // force bit k to 1
int     clearBit = x & ~(1 << k);         // force bit k to 0
boolean isOne    = (x >> k & 1) != 0;      // read bit k  (or: (x & (1 << k)) != 0)
boolean isZero   = (x >> k & 1) == 0;      // read bit k, the other way round

To set bit k, OR in a mask with a single 1 at position k. To clear it, AND with the inverted mask. To read it, shift the bit down to position 0 and mask off the rest. One operator-precedence warning the notes flag hard: in Java & binds looser than !=, so x & (1 << k) != 0 is parsed as x & ((1 << k) != 0) — an int & boolean type error. Always parenthesize: (x & (1 << k)) != 0. That single missing pair of parentheses is a genuine interview-whiteboard bug.

Counting Set Bits: LC 191 Number of 1 Bits

LC 191 Number of 1 Bits asks for the Hamming weight — how many bits are set. There is a ladder of solutions, each cleaner than the last:

• Moving mask, 32 iterations — slide a mask left and test (n & (mask << i)) != 0. Correct, but always 32 rounds.
• Shift n itself, 32 iterations — test the low bit and shift n right. Critical detail: use >>>, not >> — a negative number sign-extends under >> and you loop forever counting phantom 1s.
• Stop early — while (n != 0) n >>>= 1 quits the moment the remaining bits are all zero.
• The best: n &= (n - 1) — each step erases the lowest set bit, so the loop runs exactly once per 1-bit — O(number of set bits), not O(32).

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // wipe the lowest set bit — one iteration per 1-bit
        count++;
    }
    return count;
}

That identity — n & (n - 1) clears the lowest set bit — is the single most reused trick in the whole session. Subtracting 1 flips the lowest 1 to 0 and turns every 0 beneath it into 1; ANDing with the original erases exactly that one bit. The next two problems are just more applications of it.

XOR's Superpower: LC 136 Single Number

LC 136 Single Number: every element appears twice except one — find the loner. You could sort and scan, or dump everything into a HashSet — both work, both cost extra time or space. The elegant answer rests on one property: XOR is commutative and associative, with n ^ n = 0 and n ^ 0 = n. XOR the entire array together and every duplicated pair annihilates itself, leaving exactly the unique value. O(n) time, O(1) space, no data structure at all.

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) res ^= num;   // pairs cancel (a^a=0), the loner survives
    return res;
}

// bonus follow-up: how many bits differ between a and b?
int diff = a ^ b, bits = 0;
while (diff != 0) { diff &= (diff - 1); bits++; }   // XOR marks the differences, then popcount

The same "difference detector" answers a frequent follow-up: how many bits differ between two integers a and b? Compute a ^ b — every differing position becomes a 1 — then count those 1s with the n & (n-1) loop from LC 191. Two tricks from this session, composed into one clean answer.

Power of Two, Four, and K (LC 231)

LC 231 Power of Two has an entire menu of solutions, and naming several signals depth:

• Divide it down — reject n <= 0, then while (n % 2 == 0) n /= 2 and check n == 1. The recursive form is the same idea: return n > 0 && (n == 1 || (n % 2 == 0 && isPowerOfTwo(n / 2))).
• Count the bits — a power of two has exactly one set bit, so its Hamming weight is 1.
• The clean one — return n > 0 && (n & (n - 1)) == 0; clearing the only set bit yields 0. That is n & (n-1) yet again.
• The math flex — since the largest power of two an int can hold is 2^30 = 1073741824, any power of two must divide it evenly: return n > 0 && 1073741824 % n == 0. O(1), and not a single bit operation.

Power of Four and Power of K generalize the same ideas — for four, additionally require the single set bit to sit in an even position (or check Math.log(n) / Math.log(4) is an integer); for a general k, fall back to the divide-down loop.

Reversing Bits and Reversing Numbers (LC 190, LC 7)

LC 190 Reverse Bits flips a 32-bit integer end for end. The direct approach builds a fresh result: read bit i of the input, and if it's 1, set bit 31 - i of the output. But there's a slicker in-place idea — treat it like reversing an array with two pointers. Walk i from 0 to 15 and look at the symmetric pair (i, 31 - i): if the two bits already match, do nothing; if they differ, flip both with XOR 1. Sixteen iterations, zero allocation.

public int reverseBits(int n) {
    for (int i = 0; i < 16; i++) {          // meet in the middle
        int l = (n >> i) & 1;
        int r = (n >> (31 - i)) & 1;
        if (l != r) {                        // bits differ → flip both via XOR 1
            n ^= (1 << i);
            n ^= (1 << (31 - i));
        }
    }
    return n;
}

The decimal cousin is LC 7 Reverse Integer: peel digits with res = res * 10 + n % 10 and n /= 10. The trap is overflow — a reversed int can exceed 2^31 - 1. Guard it before the multiply: if res > (Integer.MAX_VALUE - digit) / 10, you're about to overflow, so clamp to Integer.MAX_VALUE or return 0. Reversing a String, or a fractional number (12.34 → 43.21, reversing the integer and fractional parts separately), reuses the exact same peel-and-rebuild loop.

Duplicate Detection and Bitmaps (LC 217 / 219 / 220)

LC 217 Contains Duplicate and its neighbors are HashSet warm-ups with a twist. Base version: add each element to a set; if add returns false, you've seen it — duplicate. LC 219 Contains Nearby Duplicate bounds the gap — the two indices must be within k. Keep a sliding-window set of the last k elements: before inserting nums[i], evict nums[i - k - 1] so the set never holds anything farther than k away; a failed add is your answer. (A HashMap of value → last index works too: on a repeat, check i - map.get(v) <= k.) LC 220 tightens it further, bounding the value difference as well, which pushes you toward a TreeSet or bucketing.

When the alphabet is small and fixed, you can drop hashing entirely. For letters, a boolean[52] (or boolean[256] for ASCII) flags "seen". Push it one step further into a bitmap: pack 256 flags into int[8], because each int holds 32 bits. For a character c, row = c / 32 picks the int and col = c % 32 picks the bit; check with (bitMap[row] & (1 << col)) != 0 and record with bitMap[row] |= (1 << col). Same O(1) membership test as a boolean array at one-thirty-second of the memory — a tidy way to show you understand what a hash set is really doing underneath.

Base Conversion and Roman Numerals (LC 12 / 13)

Any base-to-base conversion routes through decimal as a bridge. Decimal → base b: repeatedly take % b (the next digit) and /= b. Base b → decimal: weighted sum of digit × b^i. You can even fuse the two — res = res * 2 + (n % 2) is the same as res = (res << 1) | (n & 1), building the new representation one digit at a time.

LC 12 Integer to Roman leans on a lookup table: precompute the Roman strings for the ones, tens, hundreds, and thousands places, then peel decimal digits with % 10 and /= 10, prepending each place's numeral. 2438 → MM + CD + XXX + VIII. LC 13 Roman to Integer runs the other way with a char → value map: scan right to left and add each symbol's value, but subtract it when it is smaller than the symbol to its right — that single rule handles all the IV / IX / XL subtractive cases.

Arithmetic From Scratch (LC 29, 69, 166, 172)

The session closes on four problems that reimplement arithmetic the language usually hands you for free:

LC 29 Divide Two Integers — divide without * or /. The engine is repeated doubling: to divide a by b, double b (via << 1) as far as it still fits under a, subtract that chunk, and recurse on the remainder — each chunk contributes its accumulated multiple to the quotient. That turns an O(quotient) subtraction loop into O(log quotient). Two landmines: work in long and take Math.abs after casting (so Integer.MIN_VALUE survives), and special-case the one overflowing result, MIN_VALUE / -1, which must clamp to Integer.MAX_VALUE.

public int divide(int dividend, int divisor) {
    int sign = ((dividend > 0) ^ (divisor > 0)) ? -1 : 1;
    long a = Math.abs((long) dividend);
    long b = Math.abs((long) divisor);
    long ans = recurDiv(a, b);
    if (ans > Integer.MAX_VALUE)               // the only overflow: MIN_VALUE / -1
        return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
    return (int) (sign * ans);
}

private long recurDiv(long a, long b) {
    if (a < b) return 0;
    long sum = b, multiple = 1;
    while ((sum << 1) <= a) { sum <<= 1; multiple <<= 1; }  // double b as far as it fits
    return multiple + recurDiv(a - sum, b);
}

LC 69 Sqrt(x) — integer square root by binary search on 1 … x/2+1, comparing x / mid against mid (division, never mid * mid, to dodge overflow). It's the answer-space binary search from Session 1, in miniature.

LC 166 Fraction to Recurring Decimal — long division by hand. Emit the integer part, then keep multiplying the remainder by 10 and dividing. The clever bit is detecting the repeat: store each remainder in a HashMap keyed to its position in the output; the first time a remainder recurs, you've found the cycle, so wrap that slice in parentheses. The sign comes from a single XOR of the two operands' signs, and everything runs in long to survive Integer.MIN_VALUE.

LC 172 Factorial Trailing Zeroes — no big-number math required. A trailing zero comes from a factor of 10 = 2 × 5, and fives are scarcer than twos, so the answer is just how many factors of 5 live in n!: n/5 + n/25 + n/125 + …. Counting the right prime is the whole problem.

Problem Checklist