A grid engine counts set bits in a 64-bit occupancy word a billion times a frame — is the clear-lowest-bit loop good enough?
answer
- What varies with the data here?
- Count the branches, not the operations
- Fixed cost beats density-proportional cost
- Hardware has an instruction for this
- Better still: never count at scan time
basics
~20 sNo. The loop costs one unpredictable branch per set bit, so its price rises with board density. At that call volume use a fixed-cost population-count instruction, with a branch-free shift-and-mask fallback where the hardware lacks one.
solid answer
~50 sThe clear-lowest-set-bit loop is the right teaching answer and the wrong hot-path answer. Its iteration count tracks how many cells are occupied, and each pass carries a branch the predictor cannot learn on varied boards, so a dense grid costs far more than a sparse one. Modern 64-bit processors provide a population-count instruction that is one fixed-cost operation regardless of density; that is what a billion calls a frame wants. Where the target lacks it, a branch-free shift-and-mask sequence counts in a fixed handful of steps, and it usually beats a byte lookup table, which trades arithmetic for loads and cache pressure. The stronger move is often architectural: if the word is read far more often than it changes, maintain the count incrementally on set and clear and never count at scan time. Then measure — at a fixed 64-bit width, constants decide, not asymptotics.
go deeper
Know that counting set bits has more than one implementation and that the clear-lowest-set-bit loop does one pass per set bit. You are not expected to pick between hardware and software variants yet.
Explain why the loop's cost tracks bit density while a branch-free sequence and a hardware count do not, and describe the shift-and-mask approach as a fixed number of steps with no branching.
Show the production reasoning: target-feature availability and where the dispatch lives, branch prediction and cache effects, benchmarking at realistic densities, and attacking the call volume rather than the per-call cost.
Own the tradeoff between a portable, obvious implementation and a dispatched fast path your team must maintain. Justify the complexity against a measured frame budget, and prefer a representation change that removes the hot count over a clever routine that shrinks it.
## The four implementations, and what each actually costs **Naive per-position loop.** Shift and test each of the `w` positions. Always `w` iterations — 64 here — regardless of the data. Simple, slow, and predictable. **Clear-lowest-set-bit loop.** `n = n & (n - 1)` per pass, one pass per set bit. Cost proportional to the population count, so it is excellent on sparse words and no better than naive on dense ones. Two properties matter at scale: the loop-exit branch is *data-dependent*, so on boards of varying density the predictor mispredicts regularly, and elapsed time reveals the density of the input. **Branch-free shift-and-mask (the SWAR trick).** A fixed sequence of masked additions folds pairs into 2-bit counts, then 4-bit, then 8-bit, and sums the bytes — a logarithmic number of steps in the width, so about a dozen operations for 64 bits, and crucially with **no branches at all**. Same cost for an empty word as for a full one. **Table lookup.** Split the word into bytes and sum eight precomputed counts. Historically a big win over the naive loop, but it converts arithmetic into memory traffic; in a routine called a billion times a frame the table competes for cache lines with the data you actually care about. It is also worth checking the arithmetic on any "just precompute it" instinct — a table indexed by the whole 64-bit word is not a table, it is more entries than there are atoms you can afford. **Hardware population count.** Mainstream 64-bit processor families expose a single instruction that counts the set bits of a register in fixed time, on the order of a few cycles of latency with high throughput. It is not data-dependent, not branchy, and not beatable in software. ## Choosing under the stated constraint A billion calls a frame means the routine is the frame budget. The instruction wins, and the engineering question becomes availability: it is a target feature, not a universal one, so a real implementation selects it at build time for a known target, or dispatches once at startup for a portable binary, and keeps the branch-free sequence as the fallback. Do not put the availability check inside the hot loop — the branch you added to avoid a branch is the whole regression. Ecosystems differ in how they hand this to you rather than in what the hardware does: C++, Rust, and Java all expose a population-count in their standard libraries that lowers to the instruction on supporting targets and to a software routine elsewhere, so "write it by hand" is usually the worse call even before portability enters the picture. ## The better question: why are you counting? Senior answers usually attack the call volume rather than the per-call cost. - **Maintain the count incrementally.** If the occupancy word is read far more often than it is mutated, update a companion counter in the set and clear paths — each mutation already knows whether it changed a bit — and the scan-time cost drops to a field read. - **Cache with a dirty flag.** Recompute only when the word has changed since the last query. - **Hoist the work.** A billion calls a frame usually means the count is being recomputed inside a loop over something that did not change; count once outside it. - **Change the representation.** If what you need is "how many" far more than "which ones", a plain counter alongside the bitboard is not a hack, it is the right data structure. ## Measure, and measure the right thing At a fixed 64-bit width, asymptotic reasoning has nothing to say — every candidate is constant time in any collection sense, and the constants are the answer. Benchmark on representative densities, not on random uniform words: a puzzle grid early in a level and one late in it have very different bit densities, and the loop's ranking flips between them while the instruction's does not. Measure in the surrounding loop rather than in isolation, because the branch-prediction and cache effects that decide this comparison do not exist in a microbenchmark that counts the same word a million times. One last property worth naming: the branch-free variants and the hardware instruction are also the ones with data-independent timing. If the word being counted is ever derived from something secret, the pretty loop is the one you cannot use, quite apart from speed.
- When is the clear-lowest-set-bit loop still the right choice?When words are reliably sparse and the call volume is modest, when the target has no population-count instruction and the extra code is not worth it, and — most often — when you need to *visit* each set bit rather than merely count them: `n & -n` grabs one, `n & (n - 1)` advances, and the enumeration costs one pass per occupied cell instead of one per cell on the board.
- How would you avoid the count entirely for a bitboard read far more often than it is written?Maintain a companion counter updated in the set and clear paths, which already know whether the bit changed value; queries then read a field. If mutations are bursty, a cached count with a dirty flag gets most of the benefit with less discipline. Both replace a hot-path computation with an invariant the mutation sites must uphold, so keep the mutation behind one accessor.
- Why can a byte lookup table lose to a branch-free arithmetic sequence?The table converts arithmetic into memory traffic: eight dependent loads per word, cache lines spent on the table rather than on your data, and a stall whenever it is evicted in a busy loop. The shift-and-mask sequence is a dozen register operations with no loads and no branches. The table was a clear win against naive loops on older machines; against modern arithmetic throughput it usually is not.
- What would you actually measure before switching implementations?Throughput at representative bit densities, inside the real surrounding loop rather than in isolation, plus the branch-mispredict rate for the loop variant. A microbenchmark that counts one fixed word repeatedly trains the predictor perfectly and flatters the loop, which is exactly the comparison the production workload will not reproduce.
Counting coins by picking them out one at a time is fine for a handful and hopeless for a jar; a machine that weighs the whole jar takes the same moment either way.
saying these in an interview costs you the question
- Calls the clear-lowest-bit loop constant time and stops there
- Ignores branch misprediction on data-dependent loops
- Assumes a lookup table is automatically fastest
- Puts the instruction-availability check inside the hot loop
- Never questions why the count is recomputed a billion times
- Reasons asymptotically about a fixed 64-bit width