GIDForums  

Go Back   GIDForums > Computer Programming Forums > C Programming Language
User Name
Password
Register FAQ Members List Calendar Search Today's Posts Mark Forums Read
 
 
Thread Tools Search this Thread Rate Thread
  #1  
Old 12-Feb-2008, 10:14
mikhail mikhail is offline
Awaiting Email Confirmation
 
Join Date: Mar 2004
Location: Dublin, Ireland
Posts: 73
mikhail is on a distinguished road

Quick test whether a number is a power of two


I was wondering, is there an efficient (speed, memory?) test for whether or not a number is a power of 2 (or anything else).

I'm writing a programme where it would be handy to be able to make that kind of check.

An implementation I've used before was something like:
CPP / C++ / C Code:
int test(int x)
{
float y;

y = (float) x;

while(y>2) y /= 2; 

if(y != 1) y=0;

return (int) y
}

That doesn't look very efficient to me though. Is there a faster way?
  #2  
Old 12-Feb-2008, 15:13
seprich seprich is offline
Member
 
Join Date: Jun 2007
Posts: 110
seprich has a spectacular aura aboutseprich has a spectacular aura about

Re: Quick test whether a number is a power of two


Quote:
Originally Posted by mikhail
I was wondering, is there an efficient (speed, memory?) test for whether or not a number is a power of 2 (or anything else).

I'm writing a programme where it would be handy to be able to make that kind of check.

An implementation I've used before was something like:
CPP / C++ / C Code:
int test(int x)
{
float y;

y = (float) x;

while(y>2) y /= 2; 

if(y != 1) y=0;

return (int) y
}

That doesn't look very efficient to me though. Is there a faster way?

If you use float (or double ) it is always suspectible to rounding errors. Therefore in the end when you compare ( y != 1) you may unexpectedly get "wrong" answer because floating point numbers are not mathematically exact but instead each calculation increases the cumulative rounding error.

the simplest I could imagine was:
CPP / C++ / C Code:
int is_power_of( int x, int y ) {
    while( x>1 &&  x % y == 0 ) x /= y;
    if( x == 1 ) return 1;
    else return 0;
}

If someone can do without even the while-loop that would be interesting to see.
  #3  
Old 12-Feb-2008, 16:20
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,153
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Quick test whether a number is a power of two


Quote:
Originally Posted by mikhail
I was wondering,...
There is a highly efficient scheme for counting the number of '1' bits in a 2's complement number that goes like the following:

CPP / C++ / C Code:

/* 
 * The statement inside the loop clears the
 * least significant bit of the number.
 *
 * The loop terminates when all bits are zero.
 *
 * Therefore, the number of ones in the number
 * is simply equal to the number of times the
 * program goes through the loop.
 */
   
unsigned number_of_ones(unsigned x)
{
    unsigned count;
    for (count = 0; x != 0; count++) {
        x &= x - 1;
    }
    return count;
}

From The C Programming Language by Brian W. Kerhighan and Dennis M. Ritchie. First edition in 1978, second edition in 1988.

Bottom line: If your system has 2's complement representation of integers (as is highly likely), this function returns a value of 1 if (and only if) the number is a power of 2. It only has logic operations on the number itself. (The only arithmetic operation is the part that increments the loop counter.)

CPP / C++ / C Code:
/* Use Kerhighan's ones-counting routine
 * to determine whether an integer is
 * a power of 2
 */
#include <stdio.h>

unsigned number_of_ones(unsigned x);

int main()
{
    unsigned i;
    printf("Enter an integer: ");
    while ((scanf("%u", &i) == 1)) {
        printf("%u is ", i);
        if (number_of_ones(i) != 1) {
            printf("not ");
        }
        printf("a power of 2.\n\n");
        printf("Enter an integer: ");
    }
    return 0;
}

Code:
Enter an integer: 0 0 is not a power of 2. Enter an integer: 1 1 is a power of 2. Enter an integer: 2 2 is a power of 2. Enter an integer: 4 4 is a power of 2. Enter an integer: 8 8 is a power of 2. Enter an integer: 12 12 is not a power of 2. Enter an integer: 2147483648 2147483648 is a power of 2. Enter an integer: 2146483648 2146483648 is not a power of 2.

Regards,

Dave
  #4  
Old 12-Feb-2008, 22:16
sandeepchiks sandeepchiks is offline
Awaiting Email Confirmation
 
Join Date: Feb 2008
Location: Bangalore
Posts: 7
sandeepchiks is on a distinguished road

Re: Quick test whether a number is a power of two


One line test to determine if the number is power of 2 or not.

/************************************************** ***/
int main()
{
unsigned long int var = 2147483648;

if ( var & (var-1) )
printf ("%u is not power of 2\n", var);
else
printf ("%u is power of 2\n", var);


return 0;
}

/************************************************** ***/

cheers,
Sandeep
  #5  
Old 12-Feb-2008, 23:20
davekw7x davekw7x is offline
Outstanding Member
 
Join Date: Feb 2004
Location: Left Coast, USA
Posts: 6,153
davekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to beholddavekw7x is a splendid one to behold

Re: Quick test whether a number is a power of two


Quote:
Originally Posted by sandeepchiks
One line test to determine if the number is power of 2 or not.
That's a good specialization of the Kernighan codelet that I mentioned, and is valid except...

It works for everything but zero. It reports zero is a power of 2.

Maybe
CPP / C++ / C Code:
        if (!var || (var & (var - 1))) {
            printf("%u is not power of 2\n", var);
        }
        else {
            printf("%u is power of 2\n", var);
        }

Still a one-liner; still pretty elegant. Makes you look at what happens when you apply bit-twiddling to binary integers. Maybe a little insight, maybe a little fun. Thanks for that.

Regards,

Dave
  #6  
Old 14-Feb-2008, 07:38
mikhail mikhail is offline
Awaiting Email Confirmation
 
Join Date: Mar 2004
Location: Dublin, Ireland
Posts: 73
mikhail is on a distinguished road

Re: Quick test whether a number is a power of two


Thanks very much guys. Those looks ideal.

A slight pity though, they only work for x = 2^k. It would be nice to have something that does x = 3^k, etc. Is the best way to do that just the way seprich and I used?
 


Thread Tools Search this Thread
Search this Thread:

Advanced Search
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Check a number whether it is a sqrt of another number. dendelion C Programming Language 10 07-Aug-2006 01:48
Converting a number amount to text Godzilla C++ Forum 5 31-Mar-2006 11:38
Need Help with my Cards Program (C++) krisopotamus C++ Forum 2 06-Oct-2005 16:48
fltk-2.0 cvs Plumb FLTK Forum 20 13-Nov-2004 07:10
Anyone can write a program code for this??? chriskan76 C Programming Language 1 19-Oct-2004 20:25

Network Sites: GIDNetwork · GIDApp · GIDBlog · Learning Journal by J de Silva, The

All times are GMT -6. The time now is 15:45.


vBulletin, Copyright © 2000 - 2014, Jelsoft Enterprises Ltd.