1250. The Value of the Lowest One
For each of q numbers, print the VALUE of its lowest set bit: the power of
two contributed by the rightmost 1 in its binary form. For zero, print 0.
12 = 1100 -> 4
10 = 1010 -> 2
7 = 0111 -> 1
0 = 0000 -> 0
## What most people try first
A loop: shift right until the lowest bit is 1, counting as you go, then raise
two to that count. It is correct and it is the version worth writing once, by
hand, before reading on. It also takes up to 60 iterations per number, and at
q = 100000 that is six million steps for something a single expression does.
## The expression, and why it is not a coincidence
x & -x
Negation in two's complement is "flip every bit, then add one". Write x as
some prefix, then its lowest 1, then a run of k zeros:
x = P 1 000...0 (k zeros)
~x = ~P 0 111...1
~x+1 = ~P 1 000...0 the carry runs all the way up the k ones and stops
The carry stops at the lowest 1 position because the bit there is 0 in ~x and
absorbs it. So -x agrees with x at that position, has the complement of
x everywhere above, and is zero everywhere below. ANDing the two therefore
keeps exactly one bit: the lowest one. That is a proof, not a pattern, which is
why it holds at every width.
Zero needs no special case. 0 & -0 is 0 & 0, which is 0, and 0 is the
answer the problem asks for. Contrast #1249, where zero DOES need a guard,
because there the expression is x & (x - 1) and a false answer survives it.
## Width
Values reach 10^18, which is below 2^60, so a 64-bit integer holds every
value and every intermediate. A signed 32-bit integer stops at 2147483647 and
cannot hold the inputs at all. Note that 2 * 10^9 would still fit in 32 bits;
it is 10^18 that does not.
In C and C++ write the value as unsigned long long, where ~x + 1ULL is
exactly the negation argued above with no signed-overflow question. In
JavaScript & truncates both sides to signed 32 bits, so a Number here
silently returns the lowest set bit of the bottom 32 bits of the value; the
reference uses BigInt, whose & has no width at all.
Constraints - `1 ≤ q ≤ 100000` - `0 ≤ x ≤ 1000000000000000000`
Input
The first line contains an integer q.
Each of the next q lines contains one non-negative integer x.
Output
For each number print one integer on its own line: the value of its lowest set bit, or 0 when the number is 0. Print nothing else on the line.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.