1252. Which Position Holds the Lowest One
For each of q numbers, print the POSITION of the lowest set bit, counting
positions from 0 at the least significant end. For zero, print -1, since there
is no set bit to point at.
12 = 1100 -> 2
10 = 1010 -> 1
7 = 0111 -> 0
0 = 0000 -> -1
## What most people try first
log2(x & -x) as a floating-point call. It reads well and it is wrong at the
top of the range: a double holds integers exactly only up to
2^53 = 9007199254740992, and the library rounding on values above that can
land the result on either side of an integer. Taking the floor of a number that
was supposed to BE an integer and is now 41.99999999999999 gives 41 instead
of 42. The failure is silent and it only appears on large inputs, which is the
worst kind.
## Count the shifts instead
The position is just how many times the isolated low bit must be halved to reach 1:
low = x & -x
p = 0
while low > 1: low >>= 1; p += 1
That is at most 60 iterations and it is exact at every width, because it never leaves the integers. Shifting a power of two right by one is division by two with no remainder, so no rounding exists to go wrong.
The loop also makes the zero case obvious rather than accidental: x & -x is
0 for x = 0, the guard low > 1 is false, and the answer would come out 0.
That is why zero must be tested BEFORE the loop and answered -1. A solution that
prints 0 for zero is indistinguishable from a correct one on every input that
has a set bit at position 0, which is half of all random inputs.
## The same quantity under three names
This number is the count of trailing zeros, which C and C++ expose as
__builtin_ctzll, Java as Long.numberOfTrailingZeros, and Python as
(x & -x).bit_length() - 1. Knowing that it IS the trailing-zero count is
worth more than the loop, because it is how the quantity is named everywhere
else. #1250 asks for the same bit as a value rather than as a position.
## Width
Values reach 10^18, below 2^60, so positions run from 0 to 59 and every
value fits in a 64-bit integer. 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`
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 zero-based position of its lowest set bit, or -1 when the number is 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.