什么是最快的算法，以返回数是2的幂的力量？ [英] What is the fastest algorithm to return the power of a number which is a power of 2?

问题描述

由于N = 2 ^ K，我怎么能得到k假设n为32位整数，使用C / C ++按位？

Given n = 2^k, how can I find k assuming n is 32-bit integer using C/C++ bitwise?

推荐答案

那么，你可以使用二进制指数显式存储浮点数的事实：

Well, you could use the fact that the binary exponent is explicitly stored in floating point numbers:

unsigned log2(unsigned x)
{
    float f = x;
    memcpy(&x, &f, sizeof x);
    return (x >> 23) - 127;
}

我不知道有多快，这是和它肯定不是最便携的解决方案，但我觉得挺有意思的。

I don't know how fast this is, and it surely is not the most portable solution, but I find it quite interesting.

和只是为了好玩，这里是一个完全不同的，相对简单的解决方案：

And just for fun, here is a completely different, relatively straightforward solution:

unsigned log2(unsigned x)
{
    unsigned exp = 0;
    for (; ;)
    {
        switch (x)
        {
            case 128: ++exp;
            case 64: ++exp;
            case 32: ++exp;
            case 16: ++exp;
            case 8: ++exp;
            case 4: ++exp;
            case 2: ++exp;
            case 1: return exp;
            case 0: throw "illegal input detected";
        }
        x >>= 8;
        exp += 8;
    }
}

这里是一个完全展开的解决方案：

And here is a completely unrolled solution:

#define CASE(exp) case (1 << (exp)) : return (exp);

unsigned log2(unsigned x)
{
    switch (x)
    {
        CASE(31) CASE(30) CASE(29) CASE(28)
        CASE(27) CASE(26) CASE(25) CASE(24)
        CASE(23) CASE(22) CASE(21) CASE(20)
        CASE(19) CASE(18) CASE(17) CASE(16)
        CASE(15) CASE(14) CASE(13) CASE(12)
        CASE(11) CASE(10) CASE( 9) CASE( 8)
        CASE( 7) CASE( 6) CASE( 5) CASE( 4)
        CASE( 3) CASE( 2) CASE( 1) CASE( 0)
        default: throw "illegal input";
    }
}

这篇关于什么是最快的算法，以返回数是2的幂的力量？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！