C Question: Most Economical Test For Integer Is a Power of 2

Discussion in 'C Programming' started by David T. Ashley, Jan 4, 2007.

  1. What is the most economical test in 'C' for "integer is a power of 2"?

    For example, something better than:

    void is_2_pow(int arg)
    {
    return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    so on */ );
    }
    David T. Ashley, Jan 4, 2007
    #1
    1. Advertising

  2. "David T. Ashley" <> wrote in message
    news:...
    > What is the most economical test in 'C' for "integer is a power of 2"?
    >
    > For example, something better than:
    >
    > void is_2_pow(int arg)
    > {
    > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > so on */ );
    > }


    Let's try that again:

    void is_2_pow(int x)
    {
    return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    so on */ );
    }

    but I think everyone would have known what I meant.
    David T. Ashley, Jan 4, 2007
    #2
    1. Advertising

  3. David T. Ashley

    Guest

    David T. Ashley wrote:
    > "David T. Ashley" <> wrote in message
    > news:...
    > > What is the most economical test in 'C' for "integer is a power of 2"?
    > >
    > > For example, something better than:
    > >
    > > void is_2_pow(int arg)
    > > {
    > > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > > so on */ );
    > > }

    >
    > Let's try that again:
    >
    > void is_2_pow(int x)
    > {
    > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > so on */ );
    > }


    You're returning a value in a void function. Should be: int
    is_2_pow(int x)

    Probably not the most economical method, but I'd do:


    int isPowerof2(int x) {
    unsigned int i;
    int count = 0;
    int n = 1;

    for (i = INT_MAX; i; i >>= 1) {
    if (x & n)
    count ++;
    n <<= 1;
    }
    if (count > 1)
    count = 0;

    return count;
    }
    , Jan 4, 2007
    #3
  4. David T. Ashley

    pete Guest

    David T. Ashley wrote:
    >
    > What is the most economical test in 'C' for "integer is a power of 2"?
    >
    > For example, something better than:
    >
    > void is_2_pow(int arg)
    > {
    > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > so on */ );
    > }



    int n_is_Power_of_two(long unsigned n)
    {
    return (n & n - 1) == 0 && n != 0;
    }

    --
    pete
    pete, Jan 4, 2007
    #4
  5. In article <>,
    David T. Ashley <> wrote:

    >What is the most economical test in 'C' for "integer is a power of 2"?


    Assuming the number is known to be > 0, you can just test

    x & (x-1) == 0

    which tests whether there is only one bit set in x. If there's more
    than one 1 bit, all but the lowest order 1 bit will be unchanged by
    the subtraction and (x-1) will have 1 bits in common with x.

    -- Richard
    --
    "Consideration shall be given to the need for as many as 32 characters
    in some alphabets" - X3.4, 1963.
    Richard Tobin, Jan 4, 2007
    #5
  6. David T. Ashley

    Eric Sosman Guest

    David T. Ashley wrote:
    > What is the most economical test in 'C' for "integer is a power of 2"?
    >
    > For example, something better than:
    >
    > void is_2_pow(int arg)
    > {
    > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > so on */ );
    > }


    "Better than" a void function that tries to return a
    value isn't much of a challenge ...

    For "most economical" I nominate

    int is_2_pow(int arg) { return 0; }

    If you're willing to sacrifice some economy in pursuit of
    correctness, you might consider

    int is_2_pow(int arg) { return arg > 0; }

    If you're interested in a slightly more restricted problem
    than the one stated, I fear you'll have to abandon all hope of
    economy and suffer with this frightful piece of bloatware:

    int is_2_pow(int arg) {
    return arg > 0 && (arg & (arg - 1)) == 0;
    }

    --
    Eric Sosman
    lid
    Eric Sosman, Jan 4, 2007
    #6
  7. David T. Ashley

    Henryk Guest

    If the nummer is a power of 2 then only one bit is set in the int
    value.

    So just count the bits that are set and check if the number is 1. For
    negative numbers it's a little more complicated...

    Henryk
    Henryk, Jan 4, 2007
    #7
  8. David T. Ashley

    Coos Haak Guest

    Op 4 Jan 2007 03:52:16 -0800 schreef Henryk:

    > If the nummer is a power of 2 then only one bit is set in the int
    > value.
    >
    > So just count the bits that are set and check if the number is 1. For
    > negative numbers it's a little more complicated...
    >
    > Henryk


    There exist many negative powers of 2, but no power of 2 is negative ;-(
    So if the number is negative, it surely is no power of 2. It could be a
    power of -2 though.
    --
    Coos
    Coos Haak, Jan 4, 2007
    #8
  9. David T. Ashley

    Daniel Pitts Guest

    David T. Ashley wrote:
    > "David T. Ashley" <> wrote in message
    > news:...
    > > What is the most economical test in 'C' for "integer is a power of 2"?
    > >
    > > For example, something better than:
    > >
    > > void is_2_pow(int arg)
    > > {
    > > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > > so on */ );
    > > }

    >
    > Let's try that again:
    >
    > void is_2_pow(int x)
    > {
    > return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    > so on */ );
    > }
    >
    > but I think everyone would have known what I meant.


    int is_power_of_two(unsigned int value) {
    return x && (x & (x-1))
    }
    Daniel Pitts, Jan 5, 2007
    #9
  10. Daniel Pitts wrote:
    > David T. Ashley wrote:
    >> "David T. Ashley" <> wrote in message
    >> news:...
    >>> What is the most economical test in 'C' for "integer is a power of 2"?
    >>>
    >>> For example, something better than:
    >>>
    >>> void is_2_pow(int arg)
    >>> {
    >>> return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    >>> so on */ );
    >>> }

    >> Let's try that again:
    >>
    >> void is_2_pow(int x)
    >> {
    >> return((x == 1) || (x == 2) || (x == 4) || (x == 8) || (x == 16) /* and
    >> so on */ );
    >> }
    >>
    >> but I think everyone would have known what I meant.

    >
    > int is_power_of_two(unsigned int value) {
    > return x && (x & (x-1))
    > }
    >


    Hmm,

    5 && (5 & (4))
    == 5 && 4
    == 1

    15 && (15 & (14))
    == 15 && 14
    == 1

    So, your function tells me that 5 and 15 are both powers of 2.

    --
    Clark S. Cox III
    Clark S. Cox III, Jan 5, 2007
    #10
  11. David T. Ashley

    Old Wolf Guest

    Clark S. Cox III wrote:
    > Daniel Pitts wrote:
    > > David T. Ashley wrote:
    > >> "David T. Ashley" <> wrote:
    > >>> What is the most economical test in 'C' for "integer is a power of 2"?

    > >
    > > int is_power_of_two(unsigned int value) {
    > > return x && (x & (x-1))
    > > }

    >
    > So, your function tells me that 5 and 15 are both powers of 2.


    Should be:
    x && ! (x & (x-1))
    Old Wolf, Jan 5, 2007
    #11
    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. H.MuthuKumaraRajan
    Replies:
    3
    Views:
    417
    H.MuthuKumaraRajan
    Feb 4, 2004
  2. xkenneth
    Replies:
    8
    Views:
    328
    Bruno Desthuilliers
    Feb 6, 2008
  3. Replies:
    8
    Views:
    349
    Mark Dickinson
    Apr 17, 2008
  4. Matthew Thornton

    Economical Auction Site

    Matthew Thornton, Dec 25, 2009, in forum: ASP .Net
    Replies:
    0
    Views:
    350
    Matthew Thornton
    Dec 25, 2009
  5. Matthew Thornton

    Economical Auction Site

    Matthew Thornton, Dec 25, 2009, in forum: ASP General
    Replies:
    0
    Views:
    683
    Matthew Thornton
    Dec 25, 2009
Loading...

Share This Page