1258. The Lowest Bit That Is Still Zero

For each of q numbers, print the value of the lowest bit position that is NOT set: the smallest power of two the number does not contain.

12 = 1100 -> 1 position 0 is zero 10 = 1010 -> 1 position 0 is zero 7 = 0111 -> 8 positions 0, 1, 2 are all set 0 = 0000 -> 1 position 0 is zero

## What most people try first

Walk positions upward testing (x >> p) & 1 until one comes back 0. That is correct and costs up to 60 iterations, and it is worth writing once because it makes the next step easy to believe.

The reflex improvement is ~x & -(~x): take the complement, then its lowest set bit. That is nearly right and it is a trap in every fixed-width language, because ~x depends on the WIDTH. In 64 bits ~0 is 2^64 - 1; in 32 bits it is 2^32 - 1; in Python it is the negative number -1 with no width at all. So the expression's meaning changes between languages, which is exactly what this topic's problems are supposed to avoid.

## Adding one does the whole job

y = x + 1 answer = y & -y

Write x as some prefix, then its lowest 0, then a run of j ones:

x = P 0 111...1 (j ones) x + 1 = P 1 000...0 the carry runs up the ones and stops at the first 0

Adding one propagates a carry through exactly the trailing run of ones and settles on the lowest 0 position, turning it into a 1 and clearing everything below it. So the lowest SET bit of x + 1 sits precisely at the lowest ZERO bit of x, and no bit below it survives to confuse the issue. That means the answer is lowbit(x + 1), computed by #1250's expression, with no complement and therefore no width dependence anywhere.

Zero is handled by the same line: 0 + 1 = 1, whose lowest set bit is 1, and position 0 is indeed zero's lowest unset bit.

## Why this is worth a problem of its own

The pair lowbit(x) and lowbit(x + 1) answers "lowest one" and "lowest zero" with one operation each, and together they are how an allocator finds a free slot in a bitmap word: a word of allocated flags, and the next free index is the lowest zero bit. That is the real use, and it is why interviews ask it.

## Width

Values reach 10^18, so x + 1 reaches 10^18 + 1, still below 2^60, and a 64-bit integer holds it. The answer is at most 2^59 in range, since 10^18 has a zero bit well below position 59. A signed 32-bit integer cannot hold the input. In JavaScript & coerces to signed 32 bits, so the reference uses BigInt.

Constraints - `1 ≤ q ≤ 100000` - `0 ≤ x ≤ 1000000000000000000`