Bit Manipulation & Math — Interview Questions

How to use this lesson

Know the core bit tricks:

• x & (x - 1) clears the lowest set bit;
• x & -x isolates the lowest set bit;
• a ^ a = 0 and a ^ 0 = a;
• >>> is the unsigned shift (>> keeps the sign).

Java ints are 32-bit two's complement; watch for overflow (use long, or the Math.*Exact methods). The Integer class has built-ins: bitCount, reverse, highestOneBit, numberOfTrailingZeros.

Q1. Single number II (every other element appears three times).

Short answer:

• Count each bit position modulo 3: the bits that remain belong to the single number. O(32n), O(1).
• Or use the ones/twos state machine (O(n)): ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones.

(For "every other element appears twice", XOR everything: Single Number.)

int singleNumber(int[] a) {
    int ones = 0, twos = 0;
    for (int x : a) { ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones; }
    return ones;
}

Q2. Count the set bits.

Short answer:

• Brian Kernighan's trick: x &= x - 1 removes one set bit per iteration, so it's O(number of set bits). Use >>> and != 0 (not > 0) for negative numbers.
• The built-in is Integer.bitCount(x) (an intrinsic, usually a single POPCNT instruction).
• For all numbers from 0 to n: bits[i] = bits[i >> 1] + (i & 1), which is O(n). (Counting Bits, Number of 1 Bits)

int countBits(int x) { int c = 0; while (x != 0) { x &= x - 1; c++; } return c; }
int[] countBitsUpTo(int n) { int[] b = new int[n + 1]; for (int i = 1; i <= n; i++) b[i] = b[i >> 1] + (i & 1); return b; }

Q3. Power of two.

Short answer: A power of two has exactly one set bit, so n > 0 && (n & (n - 1)) == 0. O(1). Don't forget the n > 0 check: 0 and negative numbers aren't powers of two.

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

Q4. Reverse the bits of a 32-bit integer.

Short answer:

• Loop 32 times: shift the result left, OR in the lowest bit of n, then unsigned-shift n right. O(32).
• The built-in is Integer.reverse(n) (it uses divide-and-conquer swapping of halves, then quarters, and so on).
• If you call it very often, use a byte lookup table.

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

Q5. Find the missing number with XOR.

Short answer: XOR all the indices 0..n with all the values; the pairs cancel out, leaving the missing number. O(n), O(1), and no overflow risk (unlike the sum formula, n(n+1)/2 - sum, which needs a long for large n).

int missingNumber(int[] a) {
    int x = a.length;
    for (int i = 0; i < a.length; i++) x ^= i ^ a[i];
    return x;
}

Q6. Divide two integers without *, / or %.

Short answer: Use exponential subtraction: subtract the largest shifted multiple of the divisor (divisor << k) that fits, and add 1 << k to the quotient. That's O(log² n), or O(log n) going from high to low bits. Handle the signs with XOR, and work in long (or in negative space) to avoid overflow. Special case: MIN_VALUE / -1 overflows, so clamp it to MAX_VALUE.

int divide(int dividend, int divisor) {
    if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;
    long a = Math.abs((long) dividend), b = Math.abs((long) divisor), q = 0;
    for (int shift = 31; shift >= 0; shift--)
        if ((a >> shift) >= b) { a -= b << shift; q += 1L << shift; }
    return (int) ((dividend < 0) ^ (divisor < 0) ? -q : q);
}

Q7. Fast exponentiation.

Short answer: Exponentiation by squaring: x^n = (x²)^(n/2) when n is even, and x·x^(n-1) when it's odd, which gives O(log n). For modular exponentiation, reduce modulo m at each step, using long (or Math.multiplyHigh / BigInteger.modPow for large moduli). For a negative n with doubles: 1 / x^(-n); cast to long first, because -Integer.MIN_VALUE overflows.

double myPow(double x, int n) {
    long e = n; if (e < 0) { x = 1 / x; e = -e; }
    double res = 1;
    while (e > 0) { if ((e & 1) == 1) res *= x; x *= x; e >>= 1; }
    return res;
}
long modPow(long base, long exp, long mod) {
    long res = 1; base %= mod;
    while (exp > 0) { if ((exp & 1) == 1) res = res * base % mod; base = base * base % mod; exp >>= 1; }
    return res;
}

Q8. The Sieve of Eratosthenes.

Short answer: Mark the multiples of each prime p, starting from p² (the smaller multiples were already marked), for p ≤ √n. It's O(n log log n) time, and O(n) space (a BitSet or boolean[]). A segmented sieve handles very large ranges with O(√n) memory.

List<Integer> primesUpTo(int n) {
    boolean[] composite = new boolean[n + 1];
    for (int p = 2; (long) p * p <= n; p++)
        if (!composite[p]) for (int m = p * p; m <= n; m += p) composite[m] = true;
    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) if (!composite[i]) primes.add(i);
    return primes;
}

Q9. GCD and LCM.

Short answer:

• The Euclidean algorithm: gcd(a, b) = gcd(b, a % b), which is O(log min(a, b)).
• LCM: a / gcd(a, b) * b. Divide first, to reduce the overflow risk, and use long.
• BigInteger.gcd exists for big numbers.

long gcd(long a, long b) { while (b != 0) { long t = a % b; a = b; b = t; } return Math.abs(a); }
long lcm(long a, long b) { return a == 0 || b == 0 ? 0 : Math.abs(a / gcd(a, b) * b); }

Q10. Trailing zeroes in n!.

Short answer: Each trailing zero comes from a factor of 10 = 2 × 5, and there are always more 2s than 5s. So count the factors of 5: n/5 + n/25 + n/125 + …. O(log₅ n). Never compute the factorial (it overflows immediately, and it's too slow).

int trailingZeroes(int n) { int count = 0; while (n > 0) { n /= 5; count += n; } return count; }

Follow-up questions this topic invites — and their answers

Q: What's the difference between >> and >>> in Java? A: >> is an arithmetic shift that preserves the sign bit (negative numbers stay negative); >>> is a logical shift that fills with zeros. Use >>> when treating an int as unsigned bits.

Q: How do you check whether the i-th bit is set, and set, clear or toggle it? A: Check: (x >> i) & 1. Set: x | (1 << i). Clear: x & ~(1 << i). Toggle: x ^ (1 << i). Use 1L << i for long values and for i ≥ 31.

Q: Why is Math.abs(Integer.MIN_VALUE) negative? A: In two's complement, the range is asymmetric: +2³¹ doesn't fit in an int, so the result overflows back to MIN_VALUE. Convert to long first, or use Math.absExact, which throws.

Q: Where does bit manipulation show up in real Java code? A: HashMap uses hash ^ (hash >>> 16) and power-of-two table sizes (index = hash & (n - 1)), EnumSet uses bit vectors, and flags and permission masks, Bloom filters, and compact encodings all rely on it.