1259. The Next Number With As Many Ones
For each of q numbers, print the smallest value STRICTLY GREATER than it that
has the same number of set bits.
6 = 0110 -> 9 = 1001
5 = 0101 -> 6 = 0110
3 = 0011 -> 5 = 0101
7 = 0111 -> 11 = 1011
## What most people try first
Count the bits of x, then test x + 1, x + 2, x + 3 and so on until one
matches. It is obviously correct and the gap can be enormous: from
2^59 - 1 the answer is 864691128455135231, about 2.9 * 10^17 steps away.
The search is not slow because of a constant factor, it is slow because the
answer can be an astronomical distance from the input.
## Where the change has to happen
To get a LARGER number with the SAME popcount, exactly one 0 bit must become a 1 and exactly one 1 bit must become a 0, and the bit that rises has to be higher than the bit that falls. To get the SMALLEST such number, the rising bit should be as low as possible, and then everything below it should be packed as low as possible.
The lowest 0 that has a 1 immediately below it sits just above the lowest BLOCK
of ones. Call that block's lowest bit low = x & -x. Then
ripple = x + low
adds the block's own weight to it, which carries all the way through the block and sets the single 0 above it, clearing the whole block in the process. That is the smallest possible increase that raises a bit, and nothing above the block moves.
## Putting back what the carry swallowed
The carry destroyed every 1 in the block, so ripple has too few bits set. How
many? Exactly popcount(x) - popcount(ripple), which is a number this
calculation hands you rather than something to track by hand. Those bits have to
go back, and to keep the result smallest they go at the very bottom:
lost = popcount(x) - popcount(ripple)
answer = ripple | ((1 << lost) - 1)
Those low positions are guaranteed free, because the carry cleared everything
from position 0 up to and including the block. So the OR cannot collide with an
existing bit, and the result has the same popcount as x by construction.
x = 0110 low = 2
ripple = 1000 popcount dropped from 2 to 1, so lost = 1
answer = 1001 = 9
## Width
Inputs reach 10^18, below 2^60. ripple = x + (x & -x) is at most about
2 * 10^18 and the final OR only sets low bits, so every intermediate stays
inside a signed 64-bit integer, whose limit is 9223372036854775807. A signed
32-bit integer cannot hold the input at all. lost is at most 59, so
1 << lost must be written 1ULL << lost in C and C++ and 1L << lost in
Java; plain 1 << lost is a 32-bit shift in all three and is wrong from
lost = 31 upward. In JavaScript << and | coerce to signed 32 bits, so the
reference uses BigInt.
Constraints - `1 ≤ q ≤ 100000` - `1 ≤ x ≤ 1000000000000000000` - an answer always exists within 64 bits for every allowed `x`
Input
The first line contains an integer q.
Each of the next q lines contains one positive integer x.
Output
For each number print one integer on its own line: the smallest value greater than x whose binary form has the same number of 1 bits as x.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.