Autocoder

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.

Problems10, easy to hard
LanguagesPython and Java
Key identitiesx & (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.

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. 1

    Count the number of 1 bits in an integer (Hamming weight).

    easy

    Brian 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.

    python
    def hamming_weight(n):
        n &= 0xFFFFFFFF
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count
    java
    import java.util.*;
    
    class Solution {
        static int hammingWeight(int n) {
            int count = 0;
            while (n != 0) {
                n &= n - 1;
                count++;
            }
            return count;
        }
    }
  2. 2

    Is a number a power of two?

    easy

    A 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.

    python
    def is_power_of_two(n):
        return n > 0 and n & (n - 1) == 0
    java
    import java.util.*;
    
    class Solution {
        static boolean isPowerOfTwo(int n) {
            return n > 0 && (n & (n - 1)) == 0;
        }
    }
  3. 3

    Single number: every element appears twice except one. Find it in O(1) space.

    easy

    XOR 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.

    python
    def single_number(a):
        x = 0
        for v in a:
            x ^= v
        return x
    java
    import java.util.*;
    
    class Solution {
        static int singleNumber(int[] a) {
            int x = 0;
            for (int v : a) x ^= v;
            return x;
        }
    }
  4. 4

    Missing number: an array holds n distinct numbers from 0 to n; find the missing one.

    easy

    XOR 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.

    python
    def missing_number(a):
        x = len(a)
        for i, v in enumerate(a):
            x ^= i ^ v
        return x
    java
    import 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. 5

    Counting bits: the number of set bits for every number from 0 to n.

    medium

    Use 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.

    python
    def count_bits(n):
        res = [0] * (n + 1)
        for i in range(1, n + 1):
            res[i] = res[i >> 1] + (i & 1)
        return res
    java
    import 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. 6

    Reverse the bits of a 32-bit unsigned integer.

    medium

    Loop 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).

    python
    def reverse_bits(n):
        res = 0
        for _ in range(32):
            res = (res << 1) | (n & 1)
            n >>= 1
        return res
    java
    import 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. 7

    Single number III: exactly two values appear once and the others twice. Find both.

    medium

    XOR 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.

    python
    def 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]
    java
    import 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. 8

    Generate all subsets of a list using bitmasks.

    medium

    A 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).

    python
    def subsets(a):
        n = len(a)
        return [[a[i] for i in range(n) if mask >> i & 1]
                for mask in range(1 << n)]
    java
    import 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. 9

    Add two integers without using the + or - operators.

    hard

    XOR 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.

    python
    def 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)
    java
    import 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. 10

    Single number II: every element appears three times except one. Find it in O(1) space.

    hard

    Track 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.

    python
    def single_number_ii(a):
        ones = twos = 0
        for x in a:
            ones = (ones ^ x) & ~twos
            twos = (twos ^ x) & ~ones
        return ones
    java
    import 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

More in DSA Interview Questions

See all in this section