How to find the next higher value with same 1′s

Question

Suppose we have 127 i.e. 1111111 and next number which has same number of one's is 191 i.e. 10111111

Please provide the C code to achieve this?

Comments

Left shift the highest 1 bit by one

---

This will not work with all the numbers.
For example:
Input : 5 (0000 0101)
If we do a left shift on the highest 1 bit by one then it becomes
         0000 1010 = Ten.
But after 5 the next higher value is 6 which has two 1's. i.e (0000 0110).

Thanks.

---

my bad,
it should be shifting the first one which has 0 on the left

Answer 1

#include <stdio.h>

/*
   This function will return the total number of 1's the input num has.
*/

int num_ones_present(int num)
{
     int i = 0;

     while (num) {
           i += (num & 1);
           num >>= 1;
     }

     return i;
}

int main()
{
     int num, next_num, i = 0;
     int num_ones = 0;

     printf("Enter the number : ");
     scanf("%d", &num);

     num_ones = num_ones_present(num);
     printf("Then given number is : %d which has %d num of 1's\n", num, num_ones);

     next_num = num + 1;
     while(1) {
           /*
               The below code's concept is that, we are passing the (given_number + 1), and comparing the
               number of 1's it has. If the number of 1's is equal to giver_number. Then its done we found our
               next higher value. Else increment the given_number by 1 again. Do this until we found one.
           */
           i = num_ones_present(next_num);
           if (i == num_ones)
                break;
           next_num++;
     }

     printf("The next higer number is : %d which has %d num of 1's\n", next_num, i);

     return 0;
}