Bit manipulation interview questions, with answers

The questions, with answers

1. 1.What do AND, OR, XOR, NOT and the shift operators do, bit by bit?

   AND (&) gives 1 only where both bits are 1; OR (|) gives 1 where either is 1; XOR (^) gives 1 where the bits differ; NOT (~) flips every bit. Left shift (<<) moves bits toward the high end and fills with zeros, so n << k is n × 2^k; right shift (>>) moves them down, so n >> k is n ÷ 2^k rounded toward negative infinity for signed values. Work an example in binary: 13 is 1101 and 6 is 0110, so 13 & 6 = 0100 = 4, 13 | 6 = 1111 = 15, and 13 ^ 6 = 1011 = 11. Being able to write the numbers out in four bits and combine them column by column is the whole skill; every trick below is that plus one observation.

2. 2.How do you check whether a number is odd, or a power of two, without division?

   Odd or even: the lowest bit is 1 exactly when the number is odd, so n & 1 is 1 for odd and 0 for even — one instruction, no modulo. Power of two: a power of two has exactly one set bit, and subtracting 1 turns that bit off and every lower bit on (1000 - 1 = 0111), so the two share no bits: n & (n - 1) == 0. Add the guard n > 0, because 0 & (0 - 1) is also 0 and 0 is not a power of two. The same test tells you whether a number is a power of two minus one — all ones — via n & (n + 1) == 0.

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

3. 3.What does n & (n - 1) do, and how does Brian Kernighan's algorithm use it?

   Subtracting 1 from n flips its lowest set bit to 0 and every bit below it to 1; ANDing with n keeps the higher bits and zeroes that whole tail, so n & (n - 1) clears the lowest set bit and nothing else. 12 is 1100, 11 is 1011, and 12 & 11 = 1000. Kernighan's algorithm counts set bits by repeating that until n is 0 and counting the repetitions — it runs once per set bit rather than once per bit, so 8 (1000) takes one step. Most languages expose a hardware instruction for the same count: Integer.bitCount in Java, __builtin_popcount in GCC, int.bit_count() in Python 3.10+; mention both the loop and the builtin.

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

4. 4.How does XOR find the number that appears once when every other number appears twice?

   XOR has three properties that make it a pair-cancelling machine: a ^ a = 0, a ^ 0 = a, and it is commutative and associative, so the order of operations does not matter. XOR every element of the array together: each value that appears twice cancels itself to 0, and what remains is the single unpaired value. O(n) time, O(1) space, no sorting and no hash set. The follow-up is the missing number from 1 to n with one absent: XOR all the array elements with all the numbers 1 to n, and the pairs cancel, leaving the missing one. The version with two singles is harder — split the array by a bit where the two singles differ, then apply the trick to each half.

   int single(int[] a) {
       int x = 0;
       for (int v : a) x ^= v;   // pairs cancel, the single survives
       return x;
   }

5. 5.How do you get, set, clear and toggle the k-th bit?

   Build a mask with a single 1 in position k — 1 << k — and combine. Get: (n >> k) & 1, or (n & (1 << k)) != 0. Set: n | (1 << k). Clear: n & ~(1 << k). Toggle: n ^ (1 << k). Bits are numbered from 0 at the least significant end, so the k-th bit has value 2^k, and interviewers check whether you count from 0 or 1. The same masks handle ranges: to clear the lowest k bits, AND with ~((1 << k) - 1); to keep only the lowest k bits, AND with (1 << k) - 1. A related favourite is isolating the lowest set bit with n & (-n), which works because two's complement negation flips everything above the lowest set bit and leaves it in place.

6. 6.How are negative numbers stored, and what does that do to right shifts?

   Almost every machine uses two's complement: to negate a number, invert every bit and add 1, so -1 is all ones, the top bit marks the sign, and an n-bit integer runs from -2^(n-1) to 2^(n-1) - 1 — which is why Integer.MAX_VALUE + 1 wraps to the most negative value. Right shifts come in two flavours because of the sign bit. An arithmetic shift copies the sign bit into the vacated positions, so -8 >> 1 is -4 and the sign survives; a logical shift fills with zeros, so the same bits become a large positive number. Java has both: >> is arithmetic and >>> is logical. C leaves the behaviour of right-shifting a negative signed value implementation-defined, which is the answer if asked why unsigned types are safer for bit tricks.

7. 7.How do you swap two numbers without a temporary variable, and should you?

   The XOR swap: a ^= b; b ^= a; a ^= b. After the first line a holds a ^ b; the second line sets b to (a ^ b) ^ b, which is the original a; the third sets a to (a ^ b) ^ a, the original b. It works, it is a classic interview question, and it is the wrong thing to write in real code: it fails if a and b are the same variable or alias the same memory (the first XOR zeroes both), it is harder to read, and modern compilers turn a temporary-variable swap into a register move that is at least as fast. The arithmetic version, a = a + b; b = a - b; a = a - b, has the same aliasing problem and can overflow. Say how it works, then say why you would not use it.

8. 8.Where does bit manipulation show up in real problems?

   Bitmasks as sets: a 32-bit integer stores membership of up to 32 items, so "which of these subsets have I visited" becomes an int, union is |, intersection is &, and checking membership is a shift — the standard trick in subset dynamic programming and permission flags (read = 1, write = 2, execute = 4, combined with |). Fast arithmetic: x << 1 doubles, x >> 1 halves, x & (size - 1) replaces x % size when size is a power of two, which is how hash tables index buckets. Enumerating subsets: counting from 0 to 2^n - 1 and reading each bit generates every subset of n items without recursion. Parity, Gray codes, checksums and compression formats all live here, and the two questions above — power of two and XOR cancellation — cover most of what gets asked.

How the diagnostic asks it

One question from the DSA bank, exactly as a sitting would show it. The bank has 4 on bit manipulation and 60 across DSA.