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
In the next higher number, the leftmost 1
of the rightmost run of 1
s exchanges place with the 0
to its left, while the remaining 1
s move to the far right.
1
,a
(making carries ripple through to the next higher 0
, inverting all those bits)0
from the high position), 1
makes room for as many 0
-bits more as there were on the right end of a
.