skip to content

A capacity validator accepts n when (n & (n - 1)) == 0 — which inputs wrongly slip through?

level: middleimportance: should knowfreq 55%

answer

  1. The test asserts at most one set bit
  2. Try the smallest possible input
  3. What is zero minus one in binary?
  4. Signed words hide a second offender
  5. The guard is n > 0

basics

~20 s

Zero slips through, and on a signed word so does the most-negative value. The expression only asserts "at most one bit is set", so the real power-of-two test needs the guard n > 0 in front of it.

solid answer

~50 s

The test says *at most one bit is set*, which is weaker than *exactly one bit is set*. For `n = 0`, `n - 1` is all ones, and `0 AND anything` is 0, so an empty word passes and the validator green-lights a zero-length ring allocation. On a signed word the most-negative value also passes, because it has a single set bit — the sign bit — and nothing below it. The correct predicate is `n > 0 && (n & (n - 1)) == 0`; note that `n != 0` is not enough in signed arithmetic, since it still admits the most-negative value. The damage downstream is worse than a rejected config: a ring buffer that wraps with `i & (n - 1)` computes a mask of all ones when `n` is 0, so every index passes the wrap and reads outside the buffer.

code

pseudocode · 10 lines
pseudocode
// n = requested ring-buffer capacity, read from config
if (n & (n - 1)) == 0:
    accept(n)          // caller allocates n slots, wraps with i & (n - 1)
else:
    reject(n)

// config supplies n = 0
//   n - 1      = 11111111...1   (all ones)
//   n & (n-1)  = 00000000...0   -> accepted
//   wrap mask  = n - 1 = all ones -> i & mask == i, no wrap at all

go deeper

for a junior

Know that the bare expression lets zero through and that the working test is n > 0 combined with it. Being able to say why zero passes — all-ones minus one — is enough at this level.

for a middle

Explain the gap between 'at most one set bit' and 'exactly one', walk the zero case through the arithmetic, and name the second offender on a signed word rather than stopping at zero.

for a senior

Trace the blast radius: a zero capacity turns the mask into all ones and removes the wrap entirely, so a validator defect surfaces as memory corruption elsewhere. Say how boundary or property tests pin it.

for a principal

Decide where the invariant is enforced. Validating a capacity at every use site is how the guard goes missing once; making the type itself unable to hold a non-power-of-two capacity moves the check to one place and retires the bug class.

## What the expression actually asserts `n & (n - 1)` removes the lowest set bit of `n`. If the result is zero, then `n` had **at most one** set bit — the removal emptied the word. A power of two is a value with **exactly one** set bit. The gap between "at most one" and "exactly one" is the entire bug. ## Case 1: zero For `n = 0` there is no set bit to remove, and the arithmetic cooperates in the worst way. `0 - 1` in two's complement is the all-ones word, and `0 AND (all ones)` is `0`. The test passes. A validator built on the bare expression therefore certifies an empty capacity as a legitimate power-of-two size. The downstream failure is not a graceful rejection later on. Power-of-two capacities are chosen precisely so that wraparound can be a mask instead of a division: `next = (i + 1) & (n - 1)`. With `n = 0`, the mask `n - 1` is the all-ones word, so `i & mask == i` for every index — the wrap does nothing, and a reader walks straight off the end of a zero-slot allocation. The bug reported by users is memory corruption in the ring buffer; the cause is one missing comparison in a config validator three modules away. ## Case 2: the most-negative signed value On a signed word, the most-negative value is encoded with only the sign bit set and zeros below it. That is one set bit, so it passes the test too. This is why the widespread fix `n != 0 && (n & (n - 1)) == 0` is still not right for a signed input: it plugs the zero hole and leaves the negative one open. Every other negative value fails naturally — negatives have a run of high ones, so removing the lowest set bit leaves something behind — which makes the surviving case easy to miss in ad-hoc testing. The robust predicate is: ``` is_power_of_two(n) = (n > 0) and ((n & (n - 1)) == 0) ``` If the value arrives in an unsigned word, `n != 0` is sufficient, because there is no sign bit to smuggle a single set bit in through. State which one you are assuming; interviewers ask precisely because candidates conflate the two. ## Why capacities want to be powers of two at all Three reasons show up in real systems. Wraparound becomes `i & (n - 1)` instead of a remainder, which is a single cheap operation rather than a division. Growth becomes a doubling, which keeps amortized costs clean. And alignment falls out for free — a power-of-two size aligns naturally to its own boundary. That is why the validator exists in the first place, and why it is worth a moment of care. If your input is an arbitrary requested size, the usual companion routine rounds up rather than rejects: smear the highest set bit downward with a fixed sequence of shift-and-OR steps, then add one. Both routines need the same zero guard — rounding zero up gives you zero (or one, depending on the variant), and neither is what the caller meant. ## How to keep the bug out The interviewer's real question is how you would have caught it. The answer is boundary testing that names the boundaries: 0, 1, 2, 3, the largest representable power of two, the maximum value, and the most-negative value if the type is signed. `1` deserves attention on its own — it is a legitimate power of two (`2^0`) and a common accidental rejection when someone "fixes" the zero hole with `n > 1`. A property test that compares the bit trick against a slow, obviously-correct reference (count the set bits and demand exactly one, on a value known to be positive) over a wide range of inputs finds both holes without anyone having to think of them. The general lesson generalises past this one expression: a bit trick usually encodes a slightly *weaker* predicate than the one you wanted, and the degenerate input — the empty word, the sign bit, the maximum — is where the two predicates come apart.

  • Why exactly does zero pass the test?
    `0 - 1` is the all-ones word in two's complement, and AND-ing zero with anything is zero, so the comparison succeeds. Conceptually the expression checks "removing the lowest set bit empties the word", and a word with no set bits is already empty. Zero satisfies "at most one set bit" while failing "exactly one".
  • Is n != 0 a sufficient guard on a signed word?
    No. The most-negative signed value is encoded as the sign bit alone with zeros below it, so it has exactly one set bit and passes the trick while being nonzero and negative. Every other negative value fails naturally, which makes this one easy to miss. Use `n > 0` for a signed input; `n != 0` is sufficient only for an unsigned one.
  • Why do ring buffers want power-of-two capacities in the first place?
    Because wraparound collapses to a mask: with capacity `n` a power of two, `i & (n - 1)` is equivalent to `i mod n` and costs a single cheap operation instead of a division. Doubling growth also keeps amortized append costs clean, and the size aligns naturally to its own boundary. The masking shortcut is exactly what turns a capacity of zero into an unbounded index.
  • What test cases would have caught this before release?
    Named boundaries rather than round numbers: 0, 1, 2, 3, the largest representable power of two, the maximum value, and the most-negative value when the type is signed. Better still, a property test comparing the trick against a slow reference — positive and exactly one set bit — across a wide input range, which catches both holes without anyone anticipating them.

The expression asks "is the room empty after I switch off the one lamp that is lit?" — a room that was dark to begin with answers yes just as confidently.

saying these in an interview costs you the question

  • Says n & (n - 1) == 0 proves a power of two
  • Guards with n != 0 on a signed word and admits the most-negative value
  • Claims the test already rejects every negative input
  • Fixes the zero hole with n > 1 and rejects 1
  • Cannot say what a zero capacity does to an i & (n - 1) wrap
  • Treats the missing guard as a cosmetic input-validation nit

context

resolving links…