Power of 2 test

[Roaring_Tiger]

Following bit twiddling is new for me, so thought of sharing with you. Let me know, if there are any caveates and does not work in any of the platforms.

case I

if ( (n&(-n) ) == n)
       printf("%d is power of 2\n",n);

case II

if ( n&(n-1) && !n )
     printf("%d is power of 2\n",n);

which is very familiar way of testing power of 2.

[moi]

eh?

[Roaring_Tiger]

But not this

if ( (n&(-n) ) == n)
printf("%d is power of 2\n",n);

[Nyda]

I came up with this solution during a test. It's longer than yours, but we were not allowed to use branching or the -, == and some other operators. It's also operating properly on signed ints (meaning 1<<31 is !pow(2)).

   int isPow2(int x) {
     int x_neg= ~x +1;  // get -x
     int x_dif= x & x_neg; // lsb on 2's complement
     return !( (x_dif ^ x) | (x >> 31) | !x );
   }

If you get rid of the x_neg and ! stuff to circumvent the lack of -, == and if() you basically end up with your version + negative filter.

As for portability, it won't work on non-2's complement machines. But that's probably a given for most applications today.

edit: If you have fun solving puzzles, you could try this one:

 /* 
  * sum3 - x+y+z using only a single '+'
  *   Example: sum3(3, 4, 5) = 12
  *   Legal ops: ! ~ & ^ | << >>
  *   Max ops: 16
  */
 int sum3(int x, int y, int z) {
   int word1 = 0;
   int word2 = 0;
   /**************************************************************
 	 Fill in code below that computes values for word1 and word2
 	 without using any '+' operations 
   ***************************************************************/
 
   word1= ...;
   word2= ...;
 
   /**************************************************************
 	 Don't change anything below here
   ***************************************************************/
   return word1+word2;
 }

Looks like the prof removed our excerises at the end of the semester, but google has probably tons of other puzzles...