Next higher number with same number of set bits | GeeksforGeeks

Next higher number with same number of set bits | GeeksforGeeks
Given a number x, find next number with same number of 1 bits in it’s binary representation.
For example, consider x = 12, whose binary representation is 1100 (excluding leading zeros on 32 bit machine). It contains two logic 1 bits. The next higher number with two logic 1 bits is 17 (10001₂)

When we observe the binary sequence from 0 to 2ⁿ – 1 (n is # of bits), right most bits (least significant) vary rapidly than left most bits. The idea is to find right most string of 1′s in x, and shift the pattern to right extreme, except the left most bit in the pattern. Shift the left most bit in the pattern (omitted bit) to left part of x by one position. An example makes it more clear,

10011100
00011100 - right most string of 1's in x
00000011 - right shifted pattern except left most bit ------> [A]
00010000 - isolated left most bit of right most 1's pattern
00100000 - shiftleft-ed the isolated bit by one position ------> [B]
10000000 - left part of x, excluding right most 1's pattern ------> [C]
10100000 - add B and C (OR operation) ------> [D]
10100011 - add A and D which is required number 163

Explanation

 The expression x & -x will isolate right most set bit in x (ensuring x will use 2′s complement form for negative numbers). If we add the result to x, right most string of 1′s in x will be reset, and the immediate ’0′ left to this pattern of 1′s will be set, which is part [B] of above explanation. For example if x = 156, x & -x will result in 00000100, adding this result to x yields 10100000 (see part D).

A Correction Factor:

Note that we are adding right most set bit to the bit pattern. The addition operation causes a shift in the bit positions. The weight of binary system is 2, one shift causes an increase by a factor of 2. Since the increased number (rightOnesPattern in the code) being used twice, the error propagates twice. The error needs to be corrected. A right shift by 2 positions will correct the result.

uint_t snoob(uint_t x)

{

  uint_t rightOne;

  uint_t nextHigherOneBit;

  uint_t rightOnesPattern;

  uint_t next = 0;

  if(x)

  {

    // right most set bit

    rightOne = x & -(signed)x;

    // reset the pattern and set next higher bit

    // left part of x will be here

    nextHigherOneBit = x + rightOne;

    // nextHigherOneBit is now part [D] of the above explanation.

    // isolate the pattern

    rightOnesPattern = x ^ nextHigherOneBit;

    // right adjust pattern

    rightOnesPattern = (rightOnesPattern)/rightOne;

    // correction factor

    rightOnesPattern >>= 2;

    // rightOnesPattern is now part [A] of the above explanation.

    // integrate new pattern (Add [D] and [A])

    next = nextHigherOneBit | rightOnesPattern;

  }

  return next;

}

http://algorithmsforever.blogspot.com/2011/11/next-integer-with-same-number-of-set.html

N = 10 (1010)
Next = 12 (1100)

Solution :

1. Suppose N has last x bits 0 and then y bits 1, then in general the next number having same number of set bits is given by N + 2^(y-1) + 2^x - 1
2. Now 2^x is given by N&-N
3. Suppose M = N + 2^x
4. Similarly 2^(x+y) is given by M&-M
5. So we get 2^(y-1) by (2^(x+y)/2^x >> 1)

int next_equal_setbits(int N){

int K1 = N & -N; int M = N + K1;
int K2 = M & -M;
return K2 + ((K2/K1)>>1) - 1;

}
Read full article from Next higher number with same number of set bits | GeeksforGeeks