仅用1位设置检测整数的优化

Question

我有一个功能:

inline uint32_t ShiftOf(uint32_t v)
{
    for (uint32_t s = 0; s < 32; ++s)
    {
        if (v == 1 << s)
            return s;
    }
    return -1;
}

有没有办法优化它？

Answer 1

如果您只需要检测是否设置了一个位,而不是哪一位,则可以显着优化:

int is_power_of_two(uint32_t v) {
    return v && !(v & (v - 1));
}

如果你需要实际计算设置哪个位,不仅仅是设置了一个位,你有多种选择(或者你只是log2在验证它的2的幂并且转换结果后作弊并使用C99的函数).

简短的回答:书签位扭曲黑客.它很方便.

Answer 2

有一些方法可以优化功能.

使用按位运算符进行优化:

inline uint32_t ShiftOf(uint32_t v)
{
    uint32_t s =
        (bool)(v & 0xFFFF0000) * 16 +
        (bool)(v & 0xFF00FF00) * 8 +
        (bool)(v & 0xF0F0F0F0) * 4 +
        (bool)(v & 0xCCCCCCCC) * 2 +
        (bool)(v & 0xAAAAAAAA);
    return v == 1 << s ? s : -1;
}

使用编译器内在函数进行优化:

inline uint32_t ShiftOf(uint32_t v)
{
#if defined(_MSC_VER)
    DWORD s = 0;
    if (!_BitScanForward(&s, v))
        return -1;
#elif defined(__GNUC__)
    uint32_t s = __builtin_ctz(v);
#else
#    error This platform is unsupported!
#endif
    return v == 1 << s ? s : -1;
}

使用哈希表进行优化:

const uint32_t g_divider = 37;
uint32_t g_hash[g_divider] = { 0 };
static void InitHash()
{
    for (uint32_t s = 0; s < 32; ++s)
        g_hash[(1 << s) % g_divider] = s;
}

inline uint32_t ShiftOf(uint32_t v)
{
    uint32_t s = g_hash[v % g_divider];
    return v == 1 << s ? s : -1;
}

Answer 3

我不确定你可以展开循环:

inline uint32_t ShiftOf(uint32_t v)
{
    switch (v)
    {
    case 0x00000001: return 0;
    case 0x00000002: return 1;
    case 0x00000004: return 2;
    case 0x00000008: return 3;
    case 0x00000010: return 4;
    case 0x00000020: return 5;
    case 0x00000040: return 6;
    case 0x00000080: return 7;
    case 0x00000100: return 8;
    case 0x00000200: return 9;
    case 0x00000400: return 10;
    case 0x00000800: return 11;
    case 0x00001000: return 12;
    case 0x00002000: return 13;
    case 0x00004000: return 14;
    case 0x00008000: return 15;
    case 0x00010000: return 16;
    case 0x00020000: return 17;
    case 0x00040000: return 18;
    case 0x00080000: return 19;
    case 0x00100000: return 20;
    case 0x00200000: return 21;
    case 0x00400000: return 22;
    case 0x00800000: return 23;
    case 0x01000000: return 24;
    case 0x02000000: return 25;
    case 0x04000000: return 26;
    case 0x08000000: return 27;
    case 0x10000000: return 28;
    case 0x20000000: return 29;
    case 0x40000000: return 30;
    case 0x80000000: return 31;
    default: return -1;
    }
}