Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fastest way of computing the power that a "power of 2" number used?

Tags:

c++

math

What would be the quickest way to find the power of 2, that a certain number (that is a power of two) used?

I'm not very skilled at mathematics, so I'm not sure how best to describe it. But the function would look similar to x = 2^y where y is the output, and x is the input. Here's a truth table of what it'd look like if that helps explain it.

0 = f(1)
1 = f(2)
2 = f(4)
3 = f(8)
...
8 = f(256)
9 = f(512)

I've made a function that does this, but I fear it's not very efficient (or elegant for that matter). Would there be a simpler and more efficient way of doing this? I'm using this to compute what area of a texture is used to buffer how drawing is done, so it's called at least once for every drawn object. Here's the function I've made so far:

uint32 getThePowerOfTwo(uint32 value){
    for(uint32 n = 0; n < 32; ++n){
        if(value <= (1 << n)){
            return n;
        }
    }
    return 32; // should never be called
}
like image 840
Anne Quinn Avatar asked Jan 29 '14 17:01

Anne Quinn


People also ask

How do you quickly check if a number is a power of 2?

Keep dividing the number by two, i.e, do n = n/2 iteratively until n becomes 1. In any iteration, if n%2 becomes non-zero and n is not 1 then n is not a power of 2. If n becomes 1 then it is a power of 2.

How do you calculate the power of 2?

What is an exponent of 2? In summary, the power of a number refers to how many times we will have to multiply the base. Let's put an example: 2 to the power of 5, which we can write as 2 5 2^5 25 means 2 × × 2 × 2 × 2 × 2 2 \times \times 2 \times 2 \times 2 \times 2 2××2×2×2×2.

How do you express a number as a power of 2?

How do you express a number as a power of 2? Therefore, 9 is the 2nd power of 3. Hence, it can be concluded that any number as a power of 2 can be represented as the square of that number.

Which algorithm is best for computing power function?

exponentiation - Algorithm for computing powers - Mathematics Stack Exchange.


2 Answers

Building on woolstar's answer - I wonder if a binary search of a lookup table would be slightly faster? (and much nicer looking)...

int getThePowerOfTwo(int value) {
    static constexpr int twos[] = {
        1<<0,  1<<1,  1<<2,  1<<3,  1<<4,  1<<5,  1<<6,  1<<7,
        1<<8,  1<<9,  1<<10, 1<<11, 1<<12, 1<<13, 1<<14, 1<<15,
        1<<16, 1<<17, 1<<18, 1<<19, 1<<20, 1<<21, 1<<22, 1<<23,
        1<<24, 1<<25, 1<<26, 1<<27, 1<<28, 1<<29, 1<<30, 1<<31
    };

    return std::lower_bound(std::begin(twos), std::end(twos), value) - std::begin(twos);
}
like image 184
David Avatar answered Sep 29 '22 19:09

David


This operation is sufficiently popular for processor vendors to come up with hardware support for it. Check out find first set. Compiler vendors offer specific functions for this, unfortunately there appears to be no standard how to name it. So if you need maximum performance you have to create compiler-dependent code:

# ifdef __GNUC__  
    return __builtin_ffs( x ) - 1; // GCC
#endif
#ifdef _MSC_VER
    return CHAR_BIT * sizeof(x)-__lzcnt( x ); // Visual studio
#endif
like image 37
pentadecagon Avatar answered Sep 29 '22 20:09

pentadecagon