Thread: Determining what power of 2 a number is without loops

  1. #1
    Registered User
    Join Date
    Jul 2005
    Posts
    22

    Determining what power of 2 a number is without loops

    For example 2^5 is 32, so given the input 32, the result would be 5. I know I could do this like:

    while( num > 0 ) num >>= 1;

    but I was wondering if there was some bit operation or something because I'd rather not use a loop for this particular situation.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    2^a = b <=> log_2(b) = a
    log_2(x) = log(x)/log(2)
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > because I'd rather not use a loop for this particular situation.
    Why ever not?
    I mean, it's only one line of code and with a max of 32 iterations, it's bound to be a lot quicker than any contrived "loop-free" answers (which will actually contain vastly more complex loops, just hidden from view that's all).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Here's a bona fide loop-free answer. It might be quicker for some inputs, but obviously slower for 1, 2, 4, 8, 16. May be faster for something like 128 or 256 and higher.

    Code:
    int pow = 0;
    unsigned long tmp;
    /* Let's assume num is an unsigned long; assume
       unsigned longs are 32 bits :-) */
    
    if (tmp = num >> 16) {
        pow |= 16;
        num = tmp;
    }
    if (tmp = num >> 8) {
        pow |= 8;
        num = tmp;
    }
    if (tmp = num >> 4) {
        pow |= 4;
        num = tmp;
    }
    if (tmp = num >> 2) {
        pow |= 2;
        num = tmp;
    }
    if (tmp = num >> 1) {
        pow |= 1;
        num = tmp;
    }
    /* pow now contains the logarithm. */
    Of course, you could just roll that into a loop:
    Code:
    int pow = 0;
    unsigned long tmp; /* Should really be same type as num. */
    int i = 32; /* Set to power of two, >= length of num in bits. */
    while (i >>= 1) {
        if (tmp = num >> i) {
            pow |= i;
            num = tmp;
        }
    }
    Last edited by Rashakil Fol; 07-16-2005 at 01:48 AM.

  5. #5
    People Love Me
    Join Date
    Jan 2003
    Posts
    412
    Quote Originally Posted by Sfpiano
    For example 2^5 is 32, so given the input 32, the result would be 5. I know I could do this like:

    while( num > 0 ) num >>= 1;

    but I was wondering if there was some bit operation or something because I'd rather not use a loop for this particular situation.
    You're looking to find an exponent dear. You should probably use logarithms. You want to know the exponent in 2^x = y. Let's use your 32 for our y. So 2^x = 32. Since log functions do not allow you to specify bases other than 10 or e, you have to use the change of base method:

    log(total) / log(new base) = log _new base(32)

    log(32) / log (2) solves for the exponent. Try it yourself. It'll always work for any base, total, etc. It works great for determining exponential growth in RPG-game characters too.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. checking if a number if a power of 2
    By -EquinoX- in forum C Programming
    Replies: 10
    Last Post: 03-27-2009, 02:55 AM
  2. memory issue
    By t014y in forum C Programming
    Replies: 2
    Last Post: 02-21-2009, 12:37 AM
  3. Nim Trainer
    By guesst in forum Game Programming
    Replies: 3
    Last Post: 05-04-2008, 04:11 PM
  4. Determining the Largest number??
    By gqchynaboy in forum C++ Programming
    Replies: 4
    Last Post: 08-28-2003, 11:27 PM
  5. Determining if a number has a remainder?
    By Captain Penguin in forum C Programming
    Replies: 3
    Last Post: 09-01-2001, 07:07 AM