1293. The Floor of Log Base Two, Without Floating Point
For each of q values x, print floor(log2(x)): the position of the highest
set bit, counting from 0. Equivalently, the number of times x can be halved
before reaching 1.
1 -> 0
2 -> 1
3 -> 1
1023 -> 9
1024 -> 10
## What most people try first
The library call, in one of its forms: log2(x), log(x) / log(2), or
floor(log2(x)). All three are approximations being used to answer an exact
question, and all three fail at the top of this range. Three separate things go
wrong:
1. x itself is not exact as a double once it passes 2^53 = 9007199254740992,
so the function is not even given the right input.
2. log2 of a large power of two can return a value a hair BELOW the integer,
and the floor then gives one less. For 2^59 that is 58 instead of 59.
3. log(x) / log(2) involves two roundings and a division, so it is worse
than log2 wherever log2 exists.
The symptom is an answer that is correct for every small input and off by one at a few large ones, which is the hardest kind of bug to find by testing.
## Count the halvings
e = 0
while x > 1:
x >>= 1
e += 1
Exact at every magnitude, because it never leaves the integers, and at most 59
iterations for x up to 10^18.
The loop condition is x > 1 and not x > 0. With x > 0 the loop runs one
extra time, from 1 down to 0, and every answer comes out one too large. Writing
it as "halve until you reach 1" rather than "until you reach 0" is what makes
the count the EXPONENT rather than the bit length; those two differ by exactly
one and #1253 uses the other one.
## The same number under other names
This is the bit length minus one, the count of leading zeros subtracted from the
width, __builtin_clzll turned around, Long.numberOfLeadingZeros turned
around, and x.bit_length() - 1 in Python. Recognising that they are all this
one quantity saves rediscovering it.
## The deliberate pair with #1292
#1292 asks for the VALUE of the highest set bit and #1293 for its POSITION. They
are the same bit seen two ways, and the relation is
value = 2^position. Having both makes the conversion explicit instead of
assumed: on x = 1023 the value is 512 and the position is 9, and
2^9 = 512.
## Width
Values reach 10^18, below 2^60, so the answer runs from 0 to 59 and the
input needs a 64-bit integer. A signed 32-bit integer cannot hold 10^18 at
all, which is past its 2147483647 limit by nine orders of magnitude. The
ANSWER is at most 59 and fits anywhere, which is the distinction worth keeping:
the input is wide and the output is tiny.
In JavaScript the input passes 2^53 = 9007199254740992, so a Number cannot
hold it exactly and >> would additionally coerce to 32 bits. The reference
uses BigInt for the value and a plain Number for the counter.
Constraints - `1 ≤ q ≤ 100000` - `1 ≤ x ≤ 1000000000000000000`
Input
The first line contains an integer q.
Each of the next q lines contains one integer x.
Output
For each value print one integer on its own line: the position of its highest set bit, counting from 0, which is floor(log2(x)).
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.