Where it runs
1. The problem
The rest of the course needs two low-level tools: working with the single bits of a number, and a little number theory. A bit is one binary digit, 0 or 1.
A user has permissions: read, write, delete, admin and a dozen more. The obvious way to store them is one true/false value per permission, in a small object or an array. It works. But now every user carries a whole set of true/false values, and the check "can they write?" has to reach into that set every time.
You can store them more compactly. A whole number sits in memory as a row of 32 bits, and each bit is already a yes/no switch. Pack all the permissions into one number. Then the database holds one field, you pass one value around, and any switch changes with one operation.
For that you need to read and change one bit without touching the others.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedfindUnique([5, 3, 5, 6, 3])| 8 | 4 | 2 | 1 | |
|---|---|---|---|---|
| acc | 0 | 0 | 0 | 0 |
Every number appears twice except one. acc starts at 0, and a XOR b flips the bits of a wherever b has a 1.
Bars: the 32 bits of the number, highest on the left, a tall bar for 1. Checking every bit only reads them; Kernighan's trick clears each 1 it counts, so its bars end at zero.
One operation is one step of the loop: one bit tested or one bit cleared. Every frame, each lane does the same number of operations, so the slow one falls behind.
O(n)O(k)
Operations for n numbers, and roughly how long they take at 100 million simple operations a second. An estimate from the same count, not a measurement.
Recognise it
Say these words and it is this pattern
- find the single or unique number using XOR
- set, clear, toggle, or test a bit
- pack many yes/no flags into one integer
- count set bits or check a power of two
Looks similar, isn't
- Hash set / map
A set answers membership for any key at all. A bitmask does it for 32 known items, with no memory.
- Math and number theory (GCD, sieve, modular)
Both work on the number itself. That page is about divisors and primes, this one about bits.
- Backtracking
Subsets can be listed by counting from zero upward. Backtracking builds the same list recursively.
- Non-comparison sort (counting / radix)
Radix sort reads digits, sometimes as bits. Its goal is grouping, never flipping.
One operation is O(1) on a 32-bit value. Looping the bits is O(32), which counts as constant.
On LeetCode
Problems that read, set or count single bits of a number, such as counting 1 bits, comparing two numbers bit by bit or reversing the bits. A mask 1 << i with AND, OR and NOT handles one bit at a time.
The lesson's countBits. Add x & 1 and shift right until x is 0.
XOR the two numbers so the differing bits become 1, then count them with countBits.
Read bit i with getBit and set bit 31 minus i in the answer. Finish with >>> 0, because JavaScript bit operators give signed 32-bit results.
Check each bit position with getBit. Where c has a 0, flip every 1 in a and b, and where c has a 1, flip one bit only if both are 0.
bits[i] equals bits[i >> 1] + (i & 1), so each count reuses one you already have.