Thread: power of 2? without loops or recursion

  1. #1
    Registered User
    Join Date
    Mar 2003
    Posts
    6

    power of 2? without loops or recursion

    Hi,
    I read this question somewhere and also found its answer on the web but couldnt figure it out. can anyone pls enlighten me:

    Ques:
    Test if an unsigned integer is a power of two without loops or recursion?

    Soln: #define power_of_two(x) \ ((x)&&(~(x&(x-1))))

    Can anyone figure out what is this macro doing?
    Pls try to simplify ur explanation as much as possible.

    Thanks.

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    3
    Here's a little different code for the same thing:

    Code:
    #define power_of_two(x) ((x & (x - 1)) == 0);
    Returns 1 is it is a power of two, zero otherwise. The code changes the least significant bit of x to zero, and if x is a power of two then after the statement (x & (x - 1)) there is only one bit with a value of one and if you set it to zero it leaves you with zero for the answer.

  3. #3
    Registered User
    Join Date
    Mar 2003
    Posts
    6

    Thanks

    Hey Entropic,
    Thanks a lot for the code and the explanation.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    #define PTWO(x) (x%2==0)

    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Originally posted by quzah
    #define PTWO(x) (x%2==0)

    Quzah.
    Nono, that checks whether the number is odd or even, you little brat
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Magos
    Nono, that checks whether the number is odd or even, you little brat
    Yeah. I was thinking if it was a multiple of two, not a power of...

    Quzah.
    Hope is the first step on the road to disappointment.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Since the quick way has been done for you, I'll give you a different way:
    Code:
    #define pot_test(x) \
            ( \
                x==(1<<1) || \
                x==(1<<2) || \
                x==(1<<3) || \
                x==(1<<4) || \
                x==(1<<5) || \
                x==(1<<6) || \
                x==(1<<7) || \
                x==(1<<8) || \
                x==(1<<9) || \
                x==(1<<10) || \
                x==(1<<11) || \
                x==(1<<12) || \
                x==(1<<13) || \
                x==(1<<14) || \
                x==(1<<15) || \
                x==(1<<16) || \
                x==(1<<17) || \
                x==(1<<18) || \
                x==(1<<19) || \
                x==(1<<20) || \
                x==(1<<21) || \
                x==(1<<22) || \
                x==(1<<23) || \
                x==(1<<24) || \
                x==(1<<25) || \
                x==(1<<26) || \
                x==(1<<27) || \
                x==(1<<28) || \
                x==(1<<29) || \
                x==(1<<30) || \
                x==(1<<31)    \
            )
    Unlike the first example, mine will work on floating point numbers. Neither example will work on negative numbers.

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    You forgot 1. 2^0 = 1.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  9. #9
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Originally posted by Magos
    You forgot 1. 2^0 = 1.
    I actually intentionally left it out.

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to simulate loops for/while using a recursion
    By transgalactic2 in forum C Programming
    Replies: 4
    Last Post: 01-06-2009, 04:47 PM
  2. Problem With My Box
    By HaVoX in forum Tech Board
    Replies: 9
    Last Post: 10-15-2005, 07:38 AM
  3. Determining what power of 2 a number is without loops
    By Sfpiano in forum C++ Programming
    Replies: 4
    Last Post: 07-16-2005, 10:39 AM
  4. power recursion
    By datainjector in forum C Programming
    Replies: 2
    Last Post: 11-06-2002, 04:56 PM
  5. Power Loops
    By ginoitalo in forum C++ Programming
    Replies: 5
    Last Post: 02-23-2002, 09:56 AM