Bit manipulation interview questions with worked solutions
Last updated 2026-11-19
Bit manipulation works directly on the binary representation of integers, using AND, OR, XOR, NOT and shifts. It gives constant-space solutions to problems that otherwise need hash maps, and it is the backbone of bitmask subsets and fast parity checks.
A handful of identities cover most interview questions. x & (x - 1) clears the lowest set bit, x & -x isolates it, x ^ x is 0, x ^ 0 is x, and a left shift multiplies by two. The problems below use these in turn, from counting bits to finding unique numbers among duplicates. Language details matter: Java ints are 32-bit two's complement with a signed shift (>>) and an unsigned one (>>>), while Python integers have unlimited width. See also math and number theory questions and the DSA coding round guide.
| Problems | 10, easy to hard |
|---|---|
| Languages | Python and Java |
| Key identities | x & (x - 1), x & -x, XOR cancels |
Identities worth memorising
x & (x - 1) removes the lowest set bit, so a loop of that operation counts set bits in as many steps as there are ones. x & -x keeps only the lowest set bit. (x >> i) & 1 reads bit i. x | (1 << i) sets bit i, x & ~(1 << i) clears it, x ^ (1 << i) flips it.
XOR is its own inverse and is commutative, so XOR-ing a list in which every value appears twice leaves zero, and with one value appearing once leaves exactly that value.
- Single value among pairs: XOR everything.
- Count or test bits: Kernighan loop, x & (x - 1).
- Enumerate subsets of n items: loop masks from 0 to 2^n - 1.
- Add without plus: XOR gives the sum without carry, AND shifted left gives the carry.
Language pitfalls
In Python, negative numbers behave as if they have infinitely many leading ones, so loops like "while n" never end for a negative n unless you mask with 0xFFFFFFFF. In Java, use >>> when you want a logical shift, and remember that 1 << 31 is negative. Operator precedence bites: == binds tighter than &, so write (x & 1) == 1 with parentheses.
Bit manipulation interview questions with worked solutions: questions with worked answers
1 Count the number of 1 bits in an integer (Hamming weight).
easyBrian Kernighan's trick: n & (n - 1) clears the lowest set bit, so repeat until n is zero and count the repetitions. The loop runs once per set bit rather than once per bit position. In Python mask a negative value to 32 bits first. Time O(number of set bits), space O(1).. Edge cases: zero (0 bits), all bits set, negative numbers in Python.
pythondef hamming_weight(n): n &= 0xFFFFFFFF count = 0 while n: n &= n - 1 count += 1 return countjavaimport java.util.*; class Solution { static int hammingWeight(int n) { int count = 0; while (n != 0) { n &= n - 1; count++; } return count; } }2 Is a number a power of two?
easyA positive power of two has exactly one set bit, so n & (n - 1) is zero. Also require n > 0 because zero and negatives are not powers of two. For 8 (1000) and 7 (0111) the AND is 0. Time O(1), space O(1).. Edge cases: 0 and negative numbers (false), 1 (true, 2^0), Integer.MIN_VALUE.
pythondef is_power_of_two(n): return n > 0 and n & (n - 1) == 0javaimport java.util.*; class Solution { static boolean isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; } }3 Single number: every element appears twice except one. Find it in O(1) space.
easyXOR all the numbers. Pairs cancel because x ^ x = 0, and zero is the identity, so the answer is the one value left. Order does not matter since XOR is commutative and associative. Time O(n), space O(1).. Edge cases: one element, negative numbers, the unique value is 0.
pythondef single_number(a): x = 0 for v in a: x ^= v return xjavaimport java.util.*; class Solution { static int singleNumber(int[] a) { int x = 0; for (int v : a) x ^= v; return x; } }4 Missing number: an array holds n distinct numbers from 0 to n; find the missing one.
easyXOR every index 0..n-1 and every value, starting from n. Each present value cancels with its matching index, leaving the missing one. The sum formula n(n+1)/2 minus the array sum also works but can overflow in fixed-width types, which XOR cannot. Time O(n), space O(1).. Edge cases: missing 0, missing n, a single-element array.
pythondef missing_number(a): x = len(a) for i, v in enumerate(a): x ^= i ^ v return xjavaimport java.util.*; class Solution { static int missingNumber(int[] a) { int x = a.length; for (int i = 0; i < a.length; i++) x ^= i ^ a[i]; return x; } }5 Counting bits: the number of set bits for every number from 0 to n.
mediumUse the recurrence bits[i] = bits[i >> 1] + (i & 1): dropping the last bit gives a smaller number whose answer is already known, then add that last bit back. A single pass fills the array without calling a popcount for each number. Time O(n), space O(n) for the output.. Edge cases: n = 0, powers of two (a single set bit), large n.
pythondef count_bits(n): res = [0] * (n + 1) for i in range(1, n + 1): res[i] = res[i >> 1] + (i & 1) return resjavaimport java.util.*; class Solution { static int[] countBits(int n) { int[] res = new int[n + 1]; for (int i = 1; i <= n; i++) res[i] = res[i >> 1] + (i & 1); return res; } }6 Reverse the bits of a 32-bit unsigned integer.
mediumLoop 32 times. Each time, shift the result left by one, copy in the lowest bit of n, then shift n right. After 32 rounds the bit order is reversed, including leading zeroes. In Java use the unsigned shift >>> so a set top bit does not smear. Time O(32) = O(1), space O(1).. Edge cases: all zeroes, all ones, a value with the top bit set (Java sign).
pythondef reverse_bits(n): res = 0 for _ in range(32): res = (res << 1) | (n & 1) n >>= 1 return resjavaimport java.util.*; class Solution { static int reverseBits(int n) { int res = 0; for (int i = 0; i < 32; i++) { res = (res << 1) | (n & 1); n >>>= 1; } return res; } }7 Single number III: exactly two values appear once and the others twice. Find both.
mediumXOR everything to get x = a ^ b, where a and b are the two unique values. Since a and b differ, x has at least one set bit; isolate the lowest with x & -x. That bit splits all numbers into two groups, one containing a and the other b, with each pair kept together. XOR each group separately to recover a and b. Time O(n), space O(1).. Edge cases: exactly two elements, negative values, the two values differing only in the top bit.
pythondef single_number_iii(a): x = 0 for v in a: x ^= v low = x & -x p = q = 0 for v in a: if v & low: p ^= v else: q ^= v return [p, q]javaimport java.util.*; class Solution { static int[] singleNumberIII(int[] a) { int x = 0; for (int v : a) x ^= v; int low = x & -x, p = 0, q = 0; for (int v : a) { if ((v & low) != 0) p ^= v; else q ^= v; } return new int[]{p, q}; } }8 Generate all subsets of a list using bitmasks.
mediumA list of n items has 2^n subsets. Each integer mask from 0 to 2^n - 1 encodes one of them: bit i set means item i is included. For each mask, collect the items whose bit is set. This is a compact alternative to recursion when n is small (up to about 20). Time O(n * 2^n), space O(n) per subset beyond the output.. Edge cases: empty list (one empty subset), n above 30 (the shift overflows an int).
pythondef subsets(a): n = len(a) return [[a[i] for i in range(n) if mask >> i & 1] for mask in range(1 << n)]javaimport java.util.*; class Solution { static List<List<Integer>> subsets(int[] a) { int n = a.length; List<List<Integer>> res = new ArrayList<>(); for (int mask = 0; mask < (1 << n); mask++) { List<Integer> cur = new ArrayList<>(); for (int i = 0; i < n; i++) if ((mask >> i & 1) == 1) cur.add(a[i]); res.add(cur); } return res; } }9 Add two integers without using the + or - operators.
hardXOR adds the bits without carry, and (a & b) << 1 is the carry. Repeat with the sum-without-carry and the carry until the carry is zero. Java ints wrap naturally. Python needs a 32-bit mask in each step and a conversion back to a signed value at the end, because its integers are unbounded. Time O(32) = O(1), space O(1).. Edge cases: negative numbers (the reason Python needs masking), a zero operand, results that overflow in Java.
pythondef get_sum(a, b): mask = 0xFFFFFFFF while b: a, b = (a ^ b) & mask, ((a & b) << 1) & mask return a if a <= 0x7FFFFFFF else ~(a ^ mask)javaimport java.util.*; class Solution { static int getSum(int a, int b) { while (b != 0) { int carry = (a & b) << 1; a ^= b; b = carry; } return a; } }10 Single number II: every element appears three times except one. Find it in O(1) space.
hardTrack bits seen once and bits seen twice with two variables. For each x: ones = (ones ^ x) & ~twos, then twos = (twos ^ x) & ~ones. A bit that appears a third time is cleared from both, so only bits of the unique value remain in ones. It is XOR generalised to modulo-3 counting. Time O(n), space O(1).. Edge cases: negative numbers, the unique element appearing first or last, a single element.
pythondef single_number_ii(a): ones = twos = 0 for x in a: ones = (ones ^ x) & ~twos twos = (twos ^ x) & ~ones return onesjavaimport java.util.*; class Solution { static int singleNumberII(int[] a) { int ones = 0, twos = 0; for (int x : a) { ones = (ones ^ x) & ~twos; twos = (twos ^ x) & ~ones; } return ones; } }
Frequently asked questions
Why is x & (x - 1) so useful?
Subtracting one flips the lowest set bit and every zero below it, so ANDing with the original clears exactly that lowest set bit. It powers set-bit counting and the power-of-two test.
What is the difference between >> and >>> in Java?
>> is an arithmetic shift that copies the sign bit; >>> is a logical shift that fills with zeroes. Use >>> when treating an int as unsigned.
How do bit tricks behave with negative numbers in Python?
Python integers are arbitrary precision and act as infinite two's complement, so negatives have endless leading ones. Mask with 0xFFFFFFFF when you need 32-bit behaviour.
When should I use a bitmask instead of a set?
When the universe is small (about 20 to 30 items), because a mask is compact and operations are single instructions. It is common in subset enumeration and bitmask dynamic programming.
Which other pages use XOR or bit tricks?
The math and number theory questions page covers parity and gcd-style tricks, and backtracking questions shows recursive subset generation as an alternative.
Related guides
- Math and number theory interview questions with solutions
- Backtracking interview questions with worked solutions
- Array interview questions with worked solutions
- Hashing interview questions with worked solutions
- Cyclic sort pattern interview questions with worked solutions
- Greedy algorithm interview questions with worked solutions
More in DSA Interview Questions
- Bitmask DP Interview Questions
- Cyclic sort pattern interview questions with worked solutions
- DFS (Depth-First Search) Interview Questions
- Dijkstra and Shortest Path Interview Questions
- Divide and Conquer Interview Questions
- Dynamic Programming Interview Questions
- Edit Distance and String DP Interview Questions
- Fast and slow pointers interview questions with solutions
- Fenwick Tree (Binary Indexed Tree) Interview Questions
- Graph Interview Questions and Answers
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions