1255. Splitting a Number Into Its Powers of Two
For each of q numbers, print the powers of two that add up to it, in
increasing order, separated by single spaces. For zero, print the word NONE.
12 -> 4 8
10 -> 2 8
7 -> 1 2 4
0 -> NONE
## What most people try first
Walk positions 0 to 59, test each bit, print 2^p when the bit is set. That is
correct and it does 60 iterations for every number regardless of how few bits
are set. On q = 100000 numbers that is six million tests, of which at most
24 * 100000 find anything when the values are bounded by 10^18.
## Peel the lowest bit, repeatedly
while x:
low = x & -x the lowest set bit, as a value
print low
x -= low equivalently x &= x - 1
Two things make this correct rather than merely plausible. First, x & -x is
always a single power of two, by the two's-complement argument in #1250, so
every printed value IS a power of two. Second, subtracting it clears exactly
that bit and touches nothing else, so the loop visits each set bit exactly once
and the printed values sum back to the original x. The order is increasing
because the lowest remaining bit is always taken next.
The cost is O(popcount(x)), which is the point: a number with one set bit
costs one iteration whatever its magnitude.
## Why zero needs a word rather than an empty line
Zero is the sum of no powers of two, so the honest answer is an empty list. An
empty line is a terrible output format: the judge compares bytes, a blank line
is invisible in a diff, and a solution that crashed before printing produces the
same thing as a correct one. Printing NONE makes the case distinguishable,
which is why the output contract names the word exactly.
## Width
Values reach 10^18, below 2^60, so the largest power printed is at most
2^59 = 576460752303423488 and everything fits in a 64-bit integer. A signed
32-bit integer cannot hold values past 2147483647, and in particular cannot
hold 2^31 itself, so a 32-bit implementation starts printing wrong powers at
position 31. 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 line: the powers of two summing to it, in increasing order, separated by single spaces. When the number is 0 print the single word NONE on that line instead.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.