test whether a number is a power of 2

Discussion in 'C Programming' started by Matt, Sep 28, 2003.

  1. Matt

    Matt Guest

    Give a one-line C expression to test whether a number is a power of 2.
    No loops allowed.
     
    Matt, Sep 28, 2003
    #1
    1. Advertising

  2. Matt <> scribbled the following:
    > Give a one-line C expression to test whether a number is a power of 2.
    > No loops allowed.


    ((((x&&!(x&(x-!!x)))+x)-x)^x)^x

    What do I win?

    --
    /-- Joona Palaste () ---------------------------\
    | Kingpriest of "The Flying Lemon Tree" G++ FR FW+ M- #108 D+ ADA N+++|
    | http://www.helsinki.fi/~palaste W++ B OP+ |
    \----------------------------------------- Finland rules! ------------/
    "Remember: There are only three kinds of people - those who can count and those
    who can't."
    - Vampyra
     
    Joona I Palaste, Sep 28, 2003
    #2
    1. Advertising

  3. Ivan Vecerina, Sep 28, 2003
    #3
  4. (Matt) writes:
    > Give a one-line C expression to test whether a number is a power of 2.
    > No loops allowed.


    We're not here to do your homework for you.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
     
    Keith Thompson, Sep 28, 2003
    #4
  5. Matt

    jacob navia Guest


    > isPow2 = x && !( (x-1) & x );


    Algorithm:
    If x is a power of two, it doesn't have any bits in common with x-1, since it
    consists of a single bit on. Any positive power of two is a single bit, using
    binary integer representation.

    This means that we test if x-1 and x doesn't share bits with the and operator.

    Of course, if x is zero (not a power of two) this doesn't hold, so we add an
    explicit test for zero with xx && expression.

    Negative powers of two (0.5, 0.25, 0.125, etc) could share this same property
    in a suitable fraction representation. 0.5 would be 0.1, 0.250 would be 0.01,
    0.125 would be 0.001 etc.

    jacob
     
    jacob navia, Sep 28, 2003
    #5
  6. Matt

    Aishwarya Guest

    Joona I Palaste <> wrote in message news:<bl79og$2tv$>...
    > Matt <> scribbled the following:
    > > Give a one-line C expression to test whether a number is a power of 2.
    > > No loops allowed.

    >
    > ((((x&&!(x&(x-!!x)))+x)-x)^x)^x
    >
    > What do I win?



    hi Joona,

    i know this works because i just tested it .. but help me understand
    the algoritm please ..

    Thanks and Regards
    A.
     
    Aishwarya, Sep 29, 2003
    #6
  7. Matt

    Eric Sosman Guest

    Matt wrote:
    >
    > Give a one-line C expression to test whether a number is a power of 2.
    > No loops allowed.


    true_or_false = a_number > 0;

    (For example, 3.14159 ~= 2 ** 1.65149.)

    --
     
    Eric Sosman, Sep 29, 2003
    #7
  8. Matt

    Dan Pop Guest

    In <> Keith Thompson <> writes:

    > (Matt) writes:
    >> Give a one-line C expression to test whether a number is a power of 2.
    >> No loops allowed.

    >
    >We're not here to do your homework for you.


    OTOH, the solution is far too tricky for a homework assignment. It
    requires a bit of knowledge that has precious little to do with C
    programming.

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
     
    Dan Pop, Sep 29, 2003
    #8
  9. Matt

    Dan Pop Guest

    In <> (Aishwarya) writes:

    >Joona I Palaste <> wrote in message news:<bl79og$2tv$>...
    >> Matt <> scribbled the following:
    >> > Give a one-line C expression to test whether a number is a power of 2.
    >> > No loops allowed.

    >>
    >> ((((x&&!(x&(x-!!x)))+x)-x)^x)^x

    >
    >i know this works because i just tested it .. but help me understand
    >the algoritm please ..


    Had you engaged your brain, you'd have easily noticed that one ^x cancels
    the other and that -x cancels the +x, so you're left with

    x&&!(x&(x-!!x))

    Now, !!x is an obfuscated way of writing 1, when you know that x cannot
    be zero (it was already tested), so, we're left with:

    x&&!(x&(x-1))

    The tricky bit is x&(x-1) which actually clears the least significant
    bit that happens to be set. If the original number was a power of two,
    it had only one bit set, so the result of x&(x-1) must be zero in such
    cases.

    The rest should be obvious.

    Dan
    --
    Dan Pop
    DESY Zeuthen, RZ group
    Email:
     
    Dan Pop, Sep 29, 2003
    #9
  10. Matt

    Jirka Klaue Guest

    Aishwarya wrote:
    > Joona I Palaste <> wrote in message news:<bl79og$2tv$>...

    ....
    >>((((x&&!(x&(x-!!x)))+x)-x)^x)^x

    >
    > i know this works because i just tested it .. but help me understand
    > the algoritm please ..


    +x -x does nothing, ^x ^x does nothing.

    remains:
    x && !(x & (x - !!x))

    !!x ist alway 1, because x can't be 0 at this point.

    remains:
    x && !(x & (x - 1))

    Jirka
     
    Jirka Klaue, Sep 29, 2003
    #10
  11. Matt

    Ed Morton Guest

    On 9/28/2003 1:21 PM, Matt wrote:
    > Give a one-line C expression to test whether a number is a power of 2.
    > No loops allowed.


    if (!(x%2)) {
    puts("x is a power of 2");
    }

    Regards,

    Ed.
     
    Ed Morton, Sep 29, 2003
    #11
  12. Matt

    Jirka Klaue Guest

    Ed Morton wrote:
    > On 9/28/2003 1:21 PM, Matt wrote:
    >
    >>Give a one-line C expression to test whether a number is a power of 2.
    >>No loops allowed.

    >
    > if (!(x%2)) {
    > puts("x is a power of 2");
    > }


    Are you implying that 42 is a power of 2 and 43 is not?
    BTW: It's a three-liner and no C expression at all. ;-)

    Jirka
     
    Jirka Klaue, Sep 29, 2003
    #12
  13. Matt

    Ed Morton Guest

    On 9/29/2003 10:44 AM, Jirka Klaue wrote:
    > Ed Morton wrote:
    >
    >>On 9/28/2003 1:21 PM, Matt wrote:
    >>
    >>
    >>>Give a one-line C expression to test whether a number is a power of 2.
    >>>No loops allowed.

    >>
    >>if (!(x%2)) {
    >> puts("x is a power of 2");
    >>}

    >
    >
    > Are you implying that 42 is a power of 2 and 43 is not?
    > BTW: It's a three-liner and no C expression at all. ;-)
    >
    > Jirka
    >


    I had intended !(x%2) to be the expression, the rest was demonstrating using it.
    I'll go back to sleep now.... wake me next time you want to know if a number is
    a multiple of 2 rather than a power of 2. Sorry 'bout that.

    Ed.
     
    Ed Morton, Sep 29, 2003
    #13
  14. Matt

    Guest

    Joona I Palaste <> wrote:
    >
    > ((((x&&!(x&(x-!!x)))+x)-x)^x)^x
    >
    > What do I win?


    Nothing. What if x is negative? What if it's not an integer? What if
    the original poster provided a complete specification of the problem? :)

    -Larry Jones

    I kind of resent the manufacturer's implicit assumption
    that this would amuse me. -- Calvin
     
    , Sep 29, 2003
    #14
  15. Eric Sosman <> wrote in message news:<>...
    > Matt wrote:
    > >
    > > Give a one-line C expression to test whether a number is a power of 2.
    > > No loops allowed.

    >
    > true_or_false = a_number > 0;
    > (For example, 3.14159 ~= 2 ** 1.65149.)


    Why stop there? C99 has complex types. ;)

    --
    Peter
     
    Peter Nilsson, Sep 29, 2003
    #15
  16. Matt

    CBFalconer Guest

    Ed Morton wrote:
    > On 9/28/2003 1:21 PM, Matt wrote:
    >
    > > Give a one-line C expression to test whether a number is a
    > > power of 2. No loops allowed.

    >
    > if (!(x%2)) {
    > puts("x is a power of 2");
    > }

    ^^^^^^^^^^^^
    even

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Sep 30, 2003
    #16
  17. Matt

    Aishwarya Guest

    (Dan Pop) wrote in message news:<bl9hsv$368$>...
    ...

    > Now, !!x is an obfuscated way of writing 1, when you know that x cannot
    > be zero (it was already tested)


    this is exactly what i got stuck in :) i should have guessed it ...
    thanks for the explanation though :)
     
    Aishwarya, Sep 30, 2003
    #17
  18. "jacob navia" <> wrote in message news:<bl7kgo$d5e$>...
    > > isPow2 = x && !( (x-1) & x );

    >
    > Algorithm:
    > If x is a power of two, it doesn't have any bits in common with x-1, since it
    > consists of a single bit on. Any positive power of two is a single bit, using
    > binary integer representation.
    >
    > This means that we test if x-1 and x doesn't share bits with the and operator.
    >
    > Of course, if x is zero (not a power of two) this doesn't hold, so we add an
    > explicit test for zero with xx && expression.


    Few Mathematicians say any positive integer raised to the power minus
    infinity is 0. That is,
    n (pow) (-infinity) = 0

    IOW, 2 (pow) 3 = 8, 2 (pow) 2 = 4, 2 (pow) 1 = 2, 2 (pow) 0 = 1,
    and, 2 (pow) (-infinity) = 0.

    Because of this religious reason, I would just write my macro as
    (without 0 check)
    #define ISPOWOF2( n ) ( ! ( n & (n-1) ) )

    But, someone here in CLC told me that the above macro won't work all
    the time. I know, it won't work for float; I know the necessity of
    additional paranthesis for n. But, I couldn't see any other reasons.
    Anybody have any good comments? TIA

    ---
    "Silence is the only right answer for many wrong questions" --
    G.K.Moopanaar, Indian Politician
    http://guideme.itgo.com/atozofc/ - "A to Z of C" Project
    Email: rrjanbiah-at-Y!com
     
    R. Rajesh Jeba Anbiah, Oct 1, 2003
    #18
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. MJ
    Replies:
    11
    Views:
    1,106
  2. David T. Ashley
    Replies:
    10
    Views:
    655
    Old Wolf
    Jan 5, 2007
  3. ravi

    to test whether a number is a power of 2

    ravi, Jul 8, 2007, in forum: C Programming
    Replies:
    31
    Views:
    2,046
    Flash Gordon
    Jul 13, 2007
  4. Replies:
    8
    Views:
    395
    Mark Dickinson
    Apr 17, 2008
  5. Erik the Red
    Replies:
    4
    Views:
    194
    Chris Pine
    Jul 29, 2005
Loading...

Share This Page