Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
244 views
in Technique[技术] by (71.8m points)

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

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
}
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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);
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...