How to arrange a set of number?

How to find the next higher number with only one bit set (in C/C++)?

• Hey guys, I need a simple logic to get the next greater number with only one bit set ex: For Decimal Number : 20 (i.e. 0001 0100) The next higher number with only one bit set is 0010 0000, i.e. 32 The idea which i can think of is to *somehow* get the left most '1' bit set for the given number, and simply do a right shift of 1. i.e. For Decimal number : 20 Step 1 : (in binary form) 0001 0100 Step 2 : (find the left most '1' bit set) 000*1* 0000 Step 3 : (now do Right shift by 1) (0001 0000) <<1 = 0010 0000 (this is the answer) I need a logic to implement Step 2, Please suggest.

• Answer:

  you are making this way too complex hint: if j is your integer then only one bit is set if ( j& (j-1)) is 0 #include <stdio.h> int main() { int j; for(j=20;j& (j-1);j++); printf("%d ",j); return 0; } here is another way divide by two 'til you get to zero count the times you divided multiply 1 by two that many times (divide by 2 is the same as right shift one ) #include <stdio.h> int main() { int j=20; int n=0; for(;j;j/=2,n++); for(j=1;n;n--) j*=2; printf("%d\n",j); return 0; } or even: #include <stdio.h> int main() { int j=20; int n=0; for(;j;j>>=1,n++); j=1<<n; printf("%d\n",j); return 0; }