Bitwise interview questions are polarizing. Some engineers love them for their elegance — a single XOR replacing 20 lines of hash table code. Others hate them as trivia that rarely appears in production. The truth is somewhere in between: FAANG companies ask these questions to test whether you understand how data is represented at the machine level, not because they think you will write popcount by hand on the job. Here are the 15 most frequently asked bitwise problems, each with a solution and the key insight behind it. Use our bitwise calculator to verify the bit-level behavior of each trick as you study.
1. Single Number (LeetCode 136)
Problem: Given a non-empty array where every element appears twice except one, find that single element. Do it in O(n) time and O(1) space.
Key insight: x ^ x = 0 and x ^ 0 = x. XOR is commutative and associative, so XOR-ing all elements cancels out the pairs and leaves the singleton.
# Python
def single_number(nums):
result = 0
for n in nums:
result ^= n
return result
// JavaScript
function singleNumber(nums) {
return nums.reduce((a, b) => a ^ b, 0);
}2. Number of 1 Bits / Popcount (LeetCode 191)
Problem: Count the number of 1 bits (set bits) in an unsigned integer.
Key insight: The expression n & (n - 1) clears the lowest set bit. Repeat until n becomes 0 and count the iterations. This runs in O(number of set bits), not O(number of total bits).
# Python
def hamming_weight(n):
count = 0
while n:
n &= n - 1 # clears lowest set bit
count += 1
return count
// C++
int hammingWeight(uint32_t n) {
int count = 0;
while (n) { n &= (n - 1); count++; }
return count;
}3. Counting Bits (LeetCode 338)
Problem: For every number i from 0 to n, return the number of 1 bits in its binary representation. O(n) time.
Key insight: DP with the recurrence dp[i] = dp[i >> 1] + (i & 1). The number of set bits in i equals the set bits in i/2 (right-shift by 1) plus the LSB of i.
# Python
def count_bits(n):
dp = [0] * (n + 1)
for i in range(1, n + 1):
dp[i] = dp[i >> 1] + (i & 1)
return dp4. Reverse Bits (LeetCode 190)
Problem: Reverse the 32 bits of an unsigned integer.
Key insight: Divide and conquer. Swap adjacent 16-bit halves, then 8-bit quarters, then 4-bit nibbles, then 2-bit pairs, then individual bits. This is O(1) — five constant-time operations regardless of bit width.
# Python (divide and conquer)
def reverse_bits(n):
n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16)
n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
return n5. Power of Two (LeetCode 231)
Problem: Determine if an integer n is a power of two.
Key insight: Powers of two have exactly one set bit. n & (n - 1) clears the lowest set bit, so if the result is 0, there was exactly one set bit. Edge case: n must be positive; 0 and negative numbers are not powers of two.
# Python
def is_power_of_two(n):
return n > 0 and (n & (n - 1)) == 0
// JavaScript
const isPowerOfTwo = n => n > 0 && !(n & (n - 1));6. Missing Number (LeetCode 268)
Problem: Given an array containing n distinct numbers from 0 to n, find the one missing number. O(n) time, O(1) space.
Key insight: XOR all indices and all values. Every number that exists gets XOR-ed twice (once as an index, once as a value) and cancels out. The missing number appears only as an index and remains.
# Python
def missing_number(nums):
result = len(nums)
for i, val in enumerate(nums):
result ^= i ^ val
return result7. Find the Duplicate Number (LeetCode 287)
Problem: Given an array of n+1 integers from 1 to n, find the duplicate. O(n) time, O(1) space, do not modify the array.
Key insight: This is Floyd's cycle detection, not a pure bitwise problem — but the bitwise solution treats each bit position independently. Count how many numbers in [1, n] have that bit set, then count in the array. If the array count exceeds the expected count, the duplicate has that bit set.
# Python (bit-by-bit reconstruction)
def find_duplicate(nums):
duplicate = 0
n = len(nums) - 1
for bit in range(32):
expected = sum(1 for i in range(1, n + 1) if i & (1 << bit))
actual = sum(1 for x in nums if x & (1 << bit))
if actual > expected:
duplicate |= (1 << bit)
return duplicate8. Hamming Distance (LeetCode 461)
Problem: The Hamming distance between two integers is the number of positions where their bits differ. Return it for x and y.
Key insight: XOR the two numbers — differing bits become 1. Then count the set bits (popcount).
# Python
def hamming_distance(x, y):
xor = x ^ y
count = 0
while xor:
xor &= xor - 1
count += 1
return count9. UTF-8 Validation (LeetCode 393)
Problem: Given an array of integers representing bytes, determine if it is a valid UTF-8 encoding.
Key insight: Check the leading bits of each byte. 1-byte: starts with 0. 2-byte: starts with 110. 3-byte: starts with 1110. 4-byte: starts with 11110. Continuation bytes: start with 10. Use bitwise masks to check these patterns.
# Python
def valid_utf8(data):
def check_prefix(byte, bits):
mask = ((1 << bits) - 1) << (8 - bits)
return (byte & mask) == mask
i = 0
while i < len(data):
if data[i] >> 7 == 0:
i += 1
elif check_prefix(data[i], 3) and not (data[i] >> 5 & 1):
if i + 1 >= len(data) or not all(d >> 6 == 2 for d in data[i+1:i+2]): return False
i += 2
elif check_prefix(data[i], 4) and not (data[i] >> 4 & 1):
if i + 2 >= len(data) or not all(d >> 6 == 2 for d in data[i+1:i+3]): return False
i += 3
elif check_prefix(data[i], 5) and not (data[i] >> 3 & 1):
if i + 3 >= len(data) or not all(d >> 6 == 2 for d in data[i+1:i+4]): return False
i += 4
else:
return False
return True10. Bitwise AND of Numbers Range (LeetCode 201)
Problem: Given two integers left and right, return the bitwise AND of all numbers in [left, right] inclusive.
Key insight: The result is the common prefix of left and right in binary. All lower bits will flip between 0 and 1 at least once in the range, so they AND to 0. Right-shift both numbers until they are equal, counting the shifts, then left-shift back.
# Python
def range_bitwise_and(left, right):
shift = 0
while left != right:
left >>= 1
right >>= 1
shift += 1
return left << shift11. Maximum XOR of Two Numbers in an Array (LeetCode 421)
Problem: Given an integer array, find the maximum XOR of any two elements.
Key insight: Build a binary Trie of the numbers' bits, MSB first. For each number, greedily traverse the Trie, taking the opposite bit when possible to maximize XOR. This is O(n) in practice (32 bits per number).
# Python (simplified Trie approach)
def find_max_xor(nums):
ans = mask = 0
for i in range(31, -1, -1):
mask |= (1 << i)
prefixes = {n & mask for n in nums}
candidate = ans | (1 << i)
for p in prefixes:
if p ^ candidate in prefixes:
ans = candidate
break
return ans12. Sum of Two Integers (LeetCode 371)
Problem: Calculate a + b without using the + or - operators.
Key insight: XOR gives sum without carry. AND gives the carry bits. Shift carry left by 1 and repeat until carry is 0. This is a half-adder implemented in software.
# Python
def get_sum(a, b):
MASK = 0xFFFFFFFF # simulate 32-bit integer overflow
while b & MASK:
carry = (a & b) << 1
a = a ^ b
b = carry
return a & MASK if b > MASK else a13. Gray Code (LeetCode 89)
Problem: Generate an n-bit Gray code sequence — every adjacent number differs by exactly one bit, and the sequence is cyclic.
Key insight: The nth Gray code is n ^ (n >> 1). That single formula generates the entire sequence in order — one of the most elegant bitwise relationships in computer science.
# Python
def gray_code(n):
return [i ^ (i >> 1) for i in range(1 << n)]
# gray_code(3) → [0, 1, 3, 2, 6, 7, 5, 4]14. Single Number II (LeetCode 137)
Problem: Every element appears three times except one which appears once. Find the single element in O(n) time and O(1) space.
Key insight: For each of the 32 bit positions, count how many numbers have that bit set. If the count modulo 3 is 1, the singleton has that bit set. This generalizes to "every element appears k times except one" for any k.
# Python
def single_number_ii(nums):
result = 0
for bit in range(32):
count = sum((n >> bit) & 1 for n in nums)
if count % 3:
result |= (1 << bit)
# Handle negative numbers (two's complement)
if result & (1 << 31):
result -= (1 << 32)
return result15. Divide Two Integers (LeetCode 29)
Problem: Divide dividend by divisor without using multiplication, division, or mod. Return the quotient truncated toward zero.
Key insight: Repeatedly subtract the largest possible multiple of divisor (divisor << n) from dividend. Doubling via left shift is equivalent to multiplying by 2ⁿ. Each subtraction removes the largest chunk possible, giving O(log n) divisions — the same idea as binary long division.
# Python
def divide(dividend, divisor):
if dividend == -2**31 and divisor == -1:
return 2**31 - 1 # overflow guard
sign = (dividend < 0) ^ (divisor < 0)
a, b = abs(dividend), abs(divisor)
quotient = 0
for i in range(31, -1, -1):
if (a >> i) >= b:
quotient |= (1 << i)
a -= b << i
return -quotient if sign else quotientWhat FAANG Interviewers Look For
When an interviewer asks a bitwise question, they are testing three things. First: do you recognize that a bitwise solution exists at all, or do you instinctively reach for a hash table? Second: can you articulate the bit-level reasoning — why XOR cancels matching pairs, why n & (n-1) clears the lowest set bit, why a right shift is division by 2? Third: can you handle edge cases? Negative numbers in two's complement, 32-bit overflow boundaries, the difference between logical and arithmetic right shift in your language of choice.
The single best preparation strategy: work through each problem on our bitwise calculator with concrete numbers. Type 7 & 6 and watch the binary unfold. Type n ^ (n >> 1) for Gray code values 0 through 7 and observe the one-bit change pattern. The visual feedback from seeing bits shift and flip turns abstract tricks into muscle memory. Also check our bitwise operations guide for the full reference on every operator covered in these solutions.