Power of 2 test

This is a discussion on Power of 2 test within the C Programming forums, part of the General Programming Boards category; Following bit twiddling is new for me, so thought of sharing with you. Let me know, if there are any ...

  1. #1
    Registered User
    Join Date
    Feb 2003
    Posts
    175

    Power of 2 test

    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
    Code:
    if ( (n&(-n) ) == n)
           printf("%d is power of 2\n",n);

    case II
    Code:
    if ( n&(n-1) && !n )
         printf("%d is power of 2\n",n);
    which is very familiar way of testing power of 2.

  2. #2
    moi
    moi is offline
    Registered User moi's Avatar
    Join Date
    Jul 2002
    Posts
    946
    eh?
    hello, internet!

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    175
    But not this

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

  4. #4
    not-a-geek
    Join Date
    Apr 2004
    Posts
    210
    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)).

    Code:
       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:

    Code:
     /* 
      * 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...
    Last edited by Nyda; 10-09-2004 at 08:10 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. sustring test puzzle
    By WDT in forum C# Programming
    Replies: 3
    Last Post: 06-29-2009, 08:19 AM
  2. Help needed to verify a new on-line C test
    By JanHruska in forum Projects and Job Recruitment
    Replies: 15
    Last Post: 06-20-2009, 07:48 AM
  3. Creating C/C++ Unit Test Cases
    By chiefmonkey in forum C++ Programming
    Replies: 1
    Last Post: 04-28-2009, 09:29 PM
  4. x power y?
    By Luigi in forum C++ Programming
    Replies: 6
    Last Post: 04-25-2003, 09:34 PM
  5. power recursion
    By datainjector in forum C Programming
    Replies: 2
    Last Post: 11-06-2002, 04:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21