Bit: print the next smallest and largest numbers with the same number of 1 bit

Question

Set an integer, type the next smallest and the next largest number that have the same amount of 1 bit in their binary representation

After counting the number 1 in the number. How to determine the next smallest number?

Answer 1

for the following maximum you can use Hakmem 175:

ITEM 175 (GUSPER):

To get the following larger number with the same number of 1 bits:

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); } 

For the following, I don’t know a fast algorithm, so I would use the classical approach if the number → then 2 ^ 0 + 2 ^ 1 + ... 2 ^ n, then subtract one from your number and count the number of bits. The first number with n bits is one.

Answer 2

Here is a very good explanation. :)

Answer 3

For less

 int getNextSmaller(int num) { return ~getNextLarger(~num); } 

Sometimes it's just that simple. :)

http://www.sureinterview.com/shwqst/40004

Answer 4

See example No. 156 below. I also published a source for a detailed explanation.

{

 x = 156 10011100 becomes 10100011 To get the next higher number we need to set the 6th bit from LSB and shift the string of 1 (3rd,4th,5th) to LSB positions 1,2 and drop 5th bit 

therefore, we get 163 - 10100011, which is the next largest number with the same number 1 as 156.

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

}

{

 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; } 

}

source: http://www.geeksforgeeks.org/next-higher-number-with-same-number-of-set-bits/