Bit Manipulation Questions 2026: 18+ Problems [Solved]

Last Updated: June 2026

---

Why Bit Manipulation Matters

Candidates report bit manipulation as appearing in roughly 10% of FAANG coding rounds and frequently as a follow-up question after a brute force solution. Based on public preparation resources and candidate-reported interview threads, bit tricks appear most often when interviewers ask for O(1) space or O(log n) time solutions.

Bit manipulation is the difference between an O(n) solution and an O(1) solution for many number theory problems. It also underpins bitmask DP for subset problems.

---

Binary Representation Cheat Sheet

Bit operations:
  AND  (&):   1&1=1, 1&0=0, 0&0=0
  OR   (|):   1|1=1, 1|0=1, 0|0=0
  XOR  (^):   1^1=0, 1^0=1, 0^0=0
  NOT  (~):   ~n = -(n+1) in two's complement
  LEFT  (<<): n << k = n * 2^k
  RIGHT (>>): n >> k = n // 2^k (arithmetic shift)

Key identities:
  n & (n-1)  -- clears lowest set bit
  n & (-n)   -- isolates lowest set bit (= n & ~(n-1))
  n | (n-1)  -- sets all bits below lowest set bit
  n ^ n = 0
  n ^ 0 = n
  ~n = -(n+1)

---

Core Techniques

Check if kth bit is set

def is_kth_bit_set(n, k):
    return (n >> k) & 1 == 1

Set the kth bit

def set_kth_bit(n, k):
    return n | (1 << k)

Clear the kth bit

def clear_kth_bit(n, k):
    return n & ~(1 << k)

Toggle the kth bit

def toggle_kth_bit(n, k):
    return n ^ (1 << k)

---

Practice Questions with Solutions

Problem 1: Number of 1 Bits (Hamming Weight) (EASY)

Asked at: Amazon, Microsoft, Apple, TCS

def hamming_weight(n):
    """
    Brian Kernighan's algorithm.
    n & (n-1) clears the lowest set bit each iteration.
    Time: O(k) where k = number of set bits  Space: O(1)
    """
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

# Example
print(hamming_weight(11))   # 11 = 1011 -> 3 set bits
print(hamming_weight(128))  # 10000000 -> 1 set bit

Complexity: Time O(k) = O(log n) worst case, Space O(1)

---

Problem 2: Power of Two (EASY)

Asked at: Amazon, Google, TCS, Infosys

def is_power_of_two(n):
    """
    Powers of 2 have exactly one set bit.
    n & (n-1) == 0 for powers of 2.
    Time: O(1)  Space: O(1)
    """
    return n > 0 and (n & (n - 1)) == 0

# Example
print(is_power_of_two(1))   # True  (2^0)
print(is_power_of_two(16))  # True  (2^4)
print(is_power_of_two(6))   # False

Complexity: Time O(1), Space O(1)

---

Problem 3: Single Number (XOR Trick) (EASY)

Asked at: Amazon, Google, Microsoft, Facebook - very frequently asked

def single_number(nums):
    """
    XOR all numbers. Pairs cancel (x^x=0). Single remains (x^0=x).
    Time: O(n)  Space: O(1)
    """
    result = 0
    for num in nums:
        result ^= num
    return result

# Example
print(single_number([2, 2, 1]))          # 1
print(single_number([4, 1, 2, 1, 2]))    # 4

Complexity: Time O(n), Space O(1)

---

Problem 4: Single Number II (Number Appearing Once, Others Thrice) (MEDIUM)

Asked at: Google, Amazon, Facebook

def single_number_ii(nums):
    """
    Track bits seen once vs twice using two bitmasks.
    Time: O(n)  Space: O(1)
    """
    ones = twos = 0
    for num in nums:
        ones = (ones ^ num) & ~twos
        twos = (twos ^ num) & ~ones
    return ones

# Example
print(single_number_ii([2, 2, 3, 2]))       # 3
print(single_number_ii([0, 1, 0, 1, 0, 1, 99]))  # 99

Complexity: Time O(n), Space O(1)

---

Problem 5: Missing Number (EASY)

Asked at: Amazon, Google, Microsoft

def missing_number(nums):
    """
    XOR all indices and all values. Pairs cancel. Missing number remains.
    Time: O(n)  Space: O(1)
    """
    xor = 0
    for i, num in enumerate(nums):
        xor ^= i ^ num
    return xor ^ len(nums)

# Example
print(missing_number([3, 0, 1]))      # 2
print(missing_number([9,6,4,2,3,5,7,0,1]))  # 8

Complexity: Time O(n), Space O(1)

---

Problem 6: Counting Bits (EASY-MEDIUM)

Asked at: Amazon, Apple, Microsoft

def count_bits(n):
    """
    dp[i] = number of 1s in binary representation of i.
    dp[i] = dp[i >> 1] + (i & 1)
    Time: O(n)  Space: O(n)
    """
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

# Example
print(count_bits(5))  # [0, 1, 1, 2, 1, 2]

Complexity: Time O(n), Space O(n)

---

Problem 7: Reverse Bits (EASY)

Asked at: Apple, Amazon, Google

def reverse_bits(n):
    """
    Extract bits from right, build reversed integer from left.
    Time: O(32) = O(1)  Space: O(1)
    """
    result = 0
    for _ in range(32):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

# Example
print(reverse_bits(0b00000010100101000001111010011100))
# 0b00111001011110000010100101000000 = 964176192

Complexity: Time O(1), Space O(1)

---

Problem 8: Bitwise AND of Numbers Range (MEDIUM)

Asked at: Amazon, Google

def range_bitwise_and(left, right):
    """
    Common prefix of left and right in binary is the answer.
    Right-shift both until equal; then shift back.
    Time: O(log n)  Space: O(1)
    """
    shift = 0
    while left != right:
        left >>= 1
        right >>= 1
        shift += 1
    return left << shift

# Example
print(range_bitwise_and(5, 7))   # 4 (5=101, 6=110, 7=111 -> common prefix=100=4)
print(range_bitwise_and(1, 2147483647))  # 0

Complexity: Time O(log n), Space O(1)

---

Problem 9: Sum of Two Integers Without + or - (MEDIUM)

Asked at: Amazon, Google, Microsoft, Facebook

def get_sum(a, b):
    """
    XOR gives sum without carries. AND gives carry positions.
    Shift carry left by 1, repeat until no carry.
    Time: O(1) for 32-bit ints  Space: O(1)
    """
    MASK = 0xFFFFFFFF  # 32-bit mask

    while b & MASK:
        carry = (a & b) << 1
        a = a ^ b
        b = carry

    # Handle overflow for Python (arbitrary precision)
    return a if a <= 0x7FFFFFFF else ~(a ^ MASK)

# Example
print(get_sum(1, 2))    # 3
print(get_sum(-1, 1))   # 0

Complexity: Time O(1), Space O(1)

---

Problem 10: Maximum XOR of Two Numbers in Array (MEDIUM)

Asked at: Google, Amazon

def find_maximum_xor(nums):
    """
    Build trie of bits, greedily pick opposite bit for each number.
    Time: O(n)  Space: O(n)
    """
    max_num = max(nums)
    L = max_num.bit_length()

    prefix_set = {0}
    max_xor = 0
    curr_xor = 0

    for i in range(L - 1, -1, -1):
        prefix_set = {num >> i for num in nums}
        curr_xor = max_xor | (1 << i)  # try to set this bit

        for prefix in prefix_set:
            if curr_xor ^ prefix in prefix_set:
                max_xor = curr_xor
                break

    return max_xor

# Example
print(find_maximum_xor([3, 10, 5, 25, 2, 8]))  # 28 (5 XOR 25)

Complexity: Time O(n), Space O(n)

---

Problem 11: Subsets via Bitmask (MEDIUM)

Asked at: Amazon, Google - iterative approach

def subsets_bitmask(nums):
    """
    For n elements, there are 2^n subsets.
    Each bitmask from 0 to 2^n - 1 represents a subset.
    Time: O(n * 2^n)  Space: O(1) excluding output
    """
    n = len(nums)
    result = []

    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask >> i & 1:
                subset.append(nums[i])
        result.append(subset)

    return result

# Example
print(subsets_bitmask([1, 2, 3]))  # all 8 subsets

Complexity: Time O(n * 2^n), Space O(1) excluding output

---

Problem 12: Minimum Flips to Make OR Equal to Goal (MEDIUM)

Asked at: Amazon, Google

def min_flips(a, b, c):
    """
    For each bit: if c-bit is 0, both a and b bits must be 0.
    Count flips needed bit by bit.
    Time: O(30) = O(1)  Space: O(1)
    """
    flips = 0
    while a or b or c:
        bit_a = a & 1
        bit_b = b & 1
        bit_c = c & 1

        if bit_c == 0:
            flips += bit_a + bit_b  # both must be 0
        else:
            if bit_a == 0 and bit_b == 0:
                flips += 1  # at least one must be 1

        a >>= 1
        b >>= 1
        c >>= 1

    return flips

# Example
print(min_flips(2, 6, 5))   # 3
print(min_flips(4, 2, 7))   # 1

Complexity: Time O(1), Space O(1)

---

Problem 13: Single Number III (Two Numbers Appear Once) (MEDIUM)

Asked at: Google, Amazon, Facebook - the partition-by-bit XOR trick

Problem: Every element appears twice except two elements that appear once. Find both.

def single_number_iii(nums):
    """
    XOR everything to get a XOR b (the two singles).
    Any set bit in that result differs between a and b.
    Partition all numbers by that bit, XOR each group separately.
    Time: O(n)  Space: O(1)
    """
    xor_all = 0
    for num in nums:
        xor_all ^= num                 # = a XOR b

    # Isolate the lowest set bit: a bit where a and b differ
    diff = xor_all & (-xor_all)

    a = 0
    for num in nums:
        if num & diff:                 # group 1: this bit set
            a ^= num
    b = xor_all ^ a                     # the other single
    return [a, b]

# Example
print(single_number_iii([1, 2, 1, 3, 2, 5]))   # [3, 5]

Dry run: XOR of all gives 3 XOR 5 = 6 (binary 110). The lowest set bit is 2 (binary 010). Partition numbers by whether bit 2 is set: one group XORs to 3, the other to 5. The duplicates cancel within each group because both copies land in the same group.

Complexity: Time O(n), Space O(1)

---

Problem 14: Gray Code (MEDIUM)

Asked at: Amazon, Google

Problem: Return a sequence of 2^n integers where consecutive values differ by exactly one bit, starting at 0.

def gray_code(n):
    """
    The i-th Gray code is i XOR (i >> 1). This direct formula
    guarantees consecutive codes differ by exactly one bit.
    Time: O(2^n)  Space: O(1) excluding output
    """
    return [i ^ (i >> 1) for i in range(1 << n)]

# Example
print(gray_code(2))   # [0, 1, 3, 2]  (00, 01, 11, 10)

The formula i XOR (i >> 1) is worth memorizing. Each step flips exactly the bit that changes when you increment i and propagate the carry, which is precisely the single-bit-change property Gray codes require.

Complexity: Time O(2^n), Space O(1) excluding output

---

Problem 15: Total Hamming Distance (MEDIUM)

Asked at: Amazon, Facebook

Problem: Sum the Hamming distance between every pair of numbers in the array.

def total_hamming_distance(nums):
    """
    For each bit position, count how many numbers have it set (c).
    That bit contributes c * (n - c) to the total (set-vs-unset pairs).
    Time: O(32 * n)  Space: O(1)
    """
    total = 0
    n = len(nums)
    for bit in range(32):
        count = sum((num >> bit) & 1 for num in nums)
        total += count * (n - count)
    return total

# Example
print(total_hamming_distance([4, 14, 2]))   # 6

The insight that turns an O(n^2) pairwise comparison into O(32n): a given bit position contributes to the distance of a pair only when one number has it set and the other does not. With c numbers having the bit set, there are exactly c times (n minus c) such pairs.

Complexity: Time O(32 * n), Space O(1)

---

Problem 16: Divide Two Integers Without Multiplication (MEDIUM)

Asked at: Amazon, Microsoft, Facebook

Problem: Divide two integers without using multiplication, division, or mod.

def divide(dividend, divisor):
    """
    Repeated doubling (bit-shift) subtraction. Subtract the largest
    shifted multiple of the divisor that still fits, then continue.
    Time: O(log^2 n)  Space: O(1)
    """
    INT_MAX, INT_MIN = 2**31 - 1, -2**31
    if dividend == INT_MIN and divisor == -1:
        return INT_MAX                       # overflow guard

    negative = (dividend < 0) ^ (divisor < 0)
    a, b = abs(dividend), abs(divisor)
    quotient = 0

    while a >= b:
        temp, multiple = b, 1
        while a >= (temp << 1):
            temp <<= 1
            multiple <<= 1
        a -= temp
        quotient += multiple

    return -quotient if negative else quotient

# Example
print(divide(10, 3))    # 3
print(divide(-7, 2))    # -3

The doubling trick means each outer iteration removes the highest possible chunk of the dividend, so the algorithm runs in logarithmic rather than linear iterations of subtraction.

Complexity: Time O(log^2 n), Space O(1)

---

How to Recognize a Bit Manipulation Problem

Bit problems hide behind a few recurring tells. The strongest signal is a constraint that an answer must use O(1) extra space while the obvious solution would need a hash set or array. The XOR self-cancellation trick (Single Number, Missing Number) exists precisely to hit O(1) space.

A second tell is any mention of pairs, duplicates, or "every element appears twice except." XOR cancels pairs to zero, so problems framed around finding the odd-one-out almost always reduce to an XOR sweep.

A third tell is the appearance of powers of two, subsets, or "choose any combination." There are exactly 2^n subsets of n elements, and a bitmask from 0 to 2^n minus 1 enumerates them, so subset-enumeration problems map directly onto integer bitmasks.

A fourth tell is arithmetic restricted away from the usual operators (add without plus, divide without division). These force you to rebuild arithmetic from XOR (sum without carry), AND plus shift (carry), and repeated doubling.

When you see optimization over bit positions independently, think column by column: process each of the 32 bit positions separately and combine, as in Counting Bits and Total Hamming Distance. The unifying mindset is that an integer is just a fixed-width array of bits you can read, set, and clear in constant time.

---

XOR Tricks Reference

XOR property	Formula	Use case
Self-cancellation	x XOR x = 0	Find single number in pairs
Identity	x XOR 0 = x	Reset accumulator
Commutativity	a XOR b = b XOR a	Order-independent XOR
Find missing	XOR all [1..n] XOR array	Missing number in [1..n]
Swap without temp	a^=b; b^=a; a^=b	Swap (rarely used in practice)

---

Bit Tricks Reference

Operation	Code	Use
Check kth bit	(n >> k) & 1	Is bit k set?
Set kth bit	n or (1 << k)	Set bit k
Clear kth bit	n & ~(1 << k)	Clear bit k
Clear lowest set bit	n & (n-1)	Popcount, power-of-two check
Isolate lowest set bit	n & (-n)	Fenwick tree operations
Check power of two	n > 0 and (n & n-1) == 0	Is n = 2^k?

---

Related Articles

• Arrays Questions Placement
• Dynamic Programming Patterns 2026
• Binary Search Patterns 2026
• Must-Do Coding Questions
• Union Find Questions 2026