Recent searches
Search options
Imagine you have an integer x, and you want to find the closest integer (unequal to x) that has the same hamming weight.
There is a relevant Q&A on SO, link at the bottom.
Here's an alternative with fewer operations than anything mentioned there: let y = -x & (x + 1) in x ^ y ^ (y >> 1)
How does that work? I don't really know, I pulled this out of the void with a SAT solver. Basically magic.
SO: (careful, the decent answers are buried deep) https://stackoverflow.com/q/38523733/555045
@harold I believe -x & (x + 1) isolates the first bit that changes after a run of identical bits. For example, 0b1011 -> 0b100, 0b1100 -> 0b100. I feel like I've seen that described before.
After that, we flip the first two adjacent and unequal bits in x?
@pkhuong I don't remember this from TAOCP 7.1.3 or Hacker's Delight, could it have been somewhere else? Or I just forgot
@harold I thought it was in that one graphics people bithack files, but I can't find it either. Either way, I *think* we can re-explain it as a hybrid of (-x & x) and (x ^ (x + 1))?
@harold Since this is equivalent to lexicographic enumeration of k-combinations it feels like the sort of thing that should be in Knuth volume 4A.
@pervognsen There is a classic bithack to generate the lexicographic next bit-permutation, but that's different. This thing here can go up or down (whichever is closer) and cannot be used for enumeration
@harold Ah, I'd failed to notice it was "nearest" rather than "next". Neat.