Question Bank
Bit Manipulation Tricks
Difficulty: Medium
Mid-tier drills on XOR cancellation, mask construction, low-bit isolation, and bit counting. The patterns show up across hash-table tricks, DP states, and graph encodings.
Bit Manipulation Tricks
Mid-tier drills on XOR cancellation, mask construction, low-bit isolation, and bit counting. The patterns show up across hash-table tricks, DP states, and graph encodings.
747 views
15
Given an array where every value appears twice except one, return the lone value in O(n) time and O(1) space. Justify why XOR works.
Examples
Example 1:
Input: nums = [4, 1, 2, 1, 2]
Output: 4
Explanation: XOR is commutative, associative, and x ^ x = 0 with x ^ 0 = x. Paired values cancel pair-by-pair regardless of order. The remaining accumulator equals the single unpaired value.Write lowBit(x) that returns the value of the lowest set bit of x (e.g. lowBit(12) = 4). Explain how x & -x yields it via two's complement.
Count the set bits of an unsigned 32-bit integer in O(popcount) time (proportional to the number of set bits), not O(bit width). Show the loop.
Examples
Example 1:
Input: n = 0b10110100 (180)
Output: 4
Explanation: Brian Kernighan's trick: n &= n - 1 clears the lowest set bit on each iteration. Loop iterations = number of 1-bits. Scales with popcount, not the 32-bit width.Example 2:
Input: n = 0xFFFFFFFF
Output: 32
Explanation: Every bit is set, so the trick takes 32 iterations, matching the popcount.Given a mask m representing a chosen subset of n items, enumerate every proper non-empty submask of m in O(2^popcount(m)) total. State the canonical loop.
Swap two integers using XOR without a temporary variable. Trace a = 5, b = 9 through the three XOR statements and report the final values.
Examples
Example 1:
Input: a = 5, b = 9; apply a ^= b; b ^= a; a ^= b
Output: a = 9, b = 5
Explanation: After a ^= b: a = 5 ^ 9 = 12. After b ^= a: b = 9 ^ 12 = 5 (original a). After a ^= b: a = 12 ^ 5 = 9 (original b). Fun trivia but not a real-world recommendation; it fails when a and b alias the same memory.