Search code examples
cbit-manipulation

bit manipulation:print the next smallest and largest numbers with same no of 1 bits

Given an integer , print the next smallest and next largest number that have the same number of 1 bits in their binary representation

After Counting the number of 1's in the number.How to determine the next smallest number?

Solution

  • for next high you can use Hakmem 175 :

    ITEM 175 (Gosper):

    To get the next higher 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 next lower I do not know a fast algorithm so I would use the classic approach, if the number is > then 2^0+2^1+...2^n then deduct one from your number and count the number of bits. The first number with n bits is the one.