Loading
Loading
Treat an integer as a set of flags and use the hardware directly.
Integers are fixed-width bit vectors, and the bitwise operators manipulate them in a single instruction. XOR cancels duplicates, AND masks, shifts scale by powers of two, and a small integer can stand in for a subset of up to 64 elements.
XOR is its own inverse: `a ^ a == 0` and `a ^ 0 == a`. That single fact solves a surprising number of problems that otherwise need extra memory.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def single_number(nums): """Pairs cancel under XOR; whatever is left appeared an odd number of times.""" result = 0 for value in nums: result ^= value return result def count_set_bits(n): """Brian Kernighan: n & (n - 1) clears the lowest set bit.""" count = 0 while n: n &= n - 1 count += 1 return count # The vocabulary, in one place:# get bit i (n >> i) & 1# set bit i n | (1 << i)# clear bit i n & ~(1 << i)# toggle bit i n ^ (1 << i)# lowest set bit n & -n# power of two n > 0 and (n & (n - 1)) == 0 def all_subsets(items): """Each integer from 0 to 2^n - 1 is a subset mask.""" results = [] for mask in range(1 << len(items)): results.append([items[i] for i in range(len(items)) if mask >> i & 1]) return results| Status | Problem | Difficulty | Role |
|---|---|---|---|
| The Unpaired Badge#120 | Easy | Primary | |
| Set-Bit Tally#121 | Easy | Primary | |
| Signal Mismatch Count#122 | Easy | Primary | |
| Power-of-Two Batch Check#123 | Easy | Primary | |
| Every Basket Total#124 | Medium | Primary | |
| Strongest XOR Pair#125 | Hard | Primary | |
| The Missing Ticket#127 | Easy | Primary | |
| Fast Modular Power#129 | Medium | Related |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign in