1253. The Cost of Two Different Bit Loops
Two loops both count the set bits of a number. Over q given numbers, print
how many iterations EACH performs in total.
shift loop: while x: c += x & 1; x >>= 1
Kernighan's loop: while x: x &= x - 1; c += 1
Print two integers on one line: Kernighan's total first, then the shift loop's.
12 10 7 -> 7 11
because 12, 10 and 7` have 2, 2 and 3 set bits (7 in total) and occupy
4, 4 and 3 bit positions (11 in total).
## What most people try first
Asserting that Kernighan's version "is faster" and leaving it there. It is the right instinct and the wrong shape of claim, because the two loops have different costs on different inputs rather than one being uniformly better. This problem makes you compute both numbers, which forces the comparison to be specific.
## What each loop actually costs
The shift loop runs once per bit POSITION up to and including the highest set
one, so its count is the bit length of x: floor(log2(x)) + 1 for positive
x, and 0 for zero. It does not care how many of those bits are 1.
Kernighan's loop clears exactly one set bit per iteration and never sets one,
so its count is popcount(x) exactly. It does not care how wide the number is.
So the comparison is O(popcount) against O(width), and neither dominates:
x = 2^59 popcount 1, bit length 60 Kernighan wins 60 to 1
x = 2^59 - 1 popcount 59, bit length 59 they tie exactly
x = 7 popcount 3, bit length 3 they tie
They tie precisely when every bit up to the top one is set, which is when x is
one less than a power of two. Kernighan's loop is never WORSE, because the
number of set bits can never exceed the number of positions, and it is strictly
better as soon as one interior bit is 0. That is the honest version of "it is
faster", and it is why #1246 uses it and #1251 shows the intermediate values.
## Width
The VALUES reach 10^18 and need a 64-bit type. The two COUNTS do not: with
q at 100000 and a bit length of at most 60, each total is at most
6 * 10^6, which fits in a signed 32-bit integer with room to spare. Widening
the counters by reflex would hide that distinction, so the statement makes it:
the inputs overflow 32 bits, the answers do not. In JavaScript the counts are
plain Numbers and only the value needs 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
Print two integers on one line separated by a single space: the total iterations of Kernighan's loop over all q numbers, then the total iterations of the shift loop.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.