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
}
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.
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? 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.
exponentiation - Algorithm for computing powers - Mathematics Stack Exchange.
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);
}
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With