Clever Geek Handbook

Find the next larger number with the same number of bits set

I am working on a problem, when I am assigned a number n, I have to find the next larger item with the same number of set bits. While searching the web, I found an interesting piece of code that does this in a 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);
}

But I want to understand the basic logic of the algorithm that it will always work. All edge cases will be handled properly.

Can someone explain the logic in simple steps.

thank

+3


source to share


2 answers


In the next higher number, the leftmost 1

rightmost run 1

swaps with the 0

left, and the rest 1

move to the far right.



  • The code isolates the lowest 1

    ,
  • adds it to a

    (doing it brings the ripple to the next higher one 0

    , inverting all those bits)
  • The ex-or gets the least significant mileage of these, pushed one space to the left.
  • Offset to the right of two positions takes the left border one position to the right of the original (leaving room for this 0

    from the top position),
  • Dividing by the smallest 1

    gives room for more 0

    -bits more than the right end a

    .
+1


source


Let's say we have a bit pattern like

111100111 - decimal representation of 487

to generate the next highest integer while keeping the number 0 and 1 as in the input, we need to find the first 0 bit to the right of the input, followed by 1, and we need to switch that bit to 1. Then we need to decrease the 1 to the right from this flip point by 1 to compensate for the bit we switched from 0 to 1.



our new bit pattern will become 111101011 - 491 in decimal (we kept the bit set and not set on the input)

int getNextNumber(int input)
{
    int flipPosition=0;
    int trailingZeros=0;
    int trailingOnes=0;
    int copy = input;

    //count trailing zeros
    while(copy != 0 && (copy&1) == 0 )
    {
        ++trailingZeros;

        //test next bit
        copy = copy >> 1;
    }

    //count trailing ones
    while(copy != 0 && (copy&1) == 1 )
    {
        ++trailingOnes;

        //test next bit
        copy = copy >> 1;
    }

    //if we have no 1 we cannot form another patter with the same number of 1's
    //which will increment the input, or if we have leading consecutive
    //zero followed by consecutive 1 up to the maximum bit size of a int
    //we cannot increase the input whilst preserving the no of 0 and
    //1 in the original bit pattern
    if(trailingZeros + trailingOnes  == 0 || trailingZeros + trailingOnes == 31)
        return -1;

    //flip first 0 followed by a 1 found from the right of the bit pattern
    flipPosition = trailingZeros + trailingOnes+1;
    input |= 1<<(trailingZeros+trailingOnes);

    //clear fields to the right of the flip position
    int mask = ~0 << (trailingZeros+trailingOnes);
    input &= mask;

    //insert a bit pattern to the right of the flop position that will contain
    //one less 1 to compensate for the bit we switched from 0 to 1
    int insert = flipPosition-1;
    input |= insert;

    return input;
}
0


source






More articles:


All Articles