Fastest way of computing the power that a "power of 2" number used?
c++, math
Solution
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);
}
Problem
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 } ```