1292. The Value of the Highest One
For each of q values x, print the VALUE of its highest set bit: the largest
power of two that is at most x.
1 -> 1
3 -> 2
5 -> 4
16 -> 16
1023 -> 512
## What most people try first
The mirror of #1250 does not work. x & -x finds the LOWEST set bit in one
expression because the carry from the negation stops there, and there is no
corresponding single expression for the highest: nothing about the top of a
number is local, since finding it requires knowing that no bit above it is set.
So this problem is genuinely harder than #1250, and that asymmetry is worth noticing rather than being surprised by.
## Smear, then halve, then add one
v = x
v |= v >> 1
v |= v >> 2
v |= v >> 4
v |= v >> 8
v |= v >> 16
v |= v >> 32
answer = (v >> 1) + 1
The smearing is #1291's, applied to x itself rather than to x - 1. It turns
x into a solid run of ones from x's highest set bit down to bit 0, which is
2^(m+1) - 1 where 2^m is the answer.
Then v >> 1 is 2^m - 1, a run of ones one shorter, and adding one gives
2^m. Checking it on x = 3: v = 3 = 11, v >> 1 = 1, answer 2. And on
x = 1: v = 1, v >> 1 = 0, answer 1.
## The deliberate pair with #1291
#1291 rounds UP to a power of two and starts the smear at n - 1. This one
rounds DOWN and starts at x. The two differ by exactly those two details, and
putting them side by side is the lesson: the smear produces a run of ones, and
where you enter and leave it decides which power you get.
A useful check: for x a power of two both problems answer x. For anything
else #1291's answer is exactly twice this one's. On x = 1023 that is 1024 and
512, both declared tests.
## Width
Values reach 10^18, below 2^60, so the answer is at most
2^59 = 576460752303423488 and everything fits in a signed 64-bit integer,
limit 9223372036854775807. A signed 32-bit integer cannot hold the input, and
the v >> 32 line is a no-op in a 32-bit type, which is how a 32-bit version
of this appears to work on small inputs.
In JavaScript all six shifts would coerce to signed 32 bits, so the reference
uses BigInt. #1293 asks for the EXPONENT of this same bit and discusses why
log2 is not the way to get it.
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 largest power of two that is less than or equal to x.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.