Finding next bigger number with same number of set bits

Question

I'm working on a problem where I'm given a number n, I have to find the next larger element with same number of set bits. While searching on Internet, I found an interesting piece of code which does this in few lines of code (BIT MAGIC) here:

unsigned nexthi_same_count_ones(unsigned a) {
  /* works for any word length */
  unsigned c = (a & -a);
  unsigned r = a+c;
  return (((r ^ a) >> 2) / c) | r;  // original typo corrected
}

But I want to understand the underlying logic about the algorithm that it will work always. All the boundary cases will be handled properly.

Can someone please explain the logic in simple steps.

Thanks

Answer 1

In the next higher number, the leftmost 1 of the rightmost run of 1s exchanges place with the 0 to its left, while the remaining 1s move to the far right.

• The code isolates lowest 1,
• adds it to a (making carries ripple through to the next higher 0, inverting all those bits)
• The ex-or gets the least significant run of ones, extended one position to the left.
• Shifting it right two positions takes its left boundary one position right of the original one (leaving place for that one 0 from the high position),
• dividing by the lowest 1 makes room for as many 0-bits more as there were on the right end of a.