gosper's hack

[LC] binary watch

[LC] kth smallest amount with single digit combination

int c = q & -q;          // isolate lowest set bit. e.g. 0111 -> 0001
int r = q + c;           // add it back in. carries through the low run of 1s,
                         // bumping them into a single higher bit. 0111+0001 = 1000
q = (((r ^ q) >> 2) / c) | r;
                         // r^q = bits that changed = the whole low run + the new bit
                         // shift off the 2 "used up" bits, then /c slides
                         // the leftover 1s all the way down to position 0
                         // | r glues the bumped bit back on top

every step finds the lowest cluster of 1s, pushes it up by one slot, and rakes the rest of the cluster back down to the bottom

trace for q = 0111 (k=3):

c = 0001                (lowest bit)
r = q + c = 1000        (carry ate the whole low run)
r ^ q = 1111            (everything that flipped)
(r ^ q) >> 2 = 0011     (drop 2 bits — one for the carry, one already placed)
0011 / c(0001) = 0011   (leftover 1s, shoved to the bottom)
0011 | r(1000) = 1011   (next combo)