快速log2取整算法

空间和时间复杂度都是 O(1),好像还鲜有人知的算法:

inline auto log_2(uint64_t x) { // also unsigned long long
    uint64_t rst = 0;
    if (x & 0xffff'ffff'0000'0000ULL) rst += 32, x >>= 32;
    if (x & 0x0000'0000'ffff'0000ULL) rst += 16, x >>= 16;
    if (x & 0x0000'0000'0000'ff00ULL) rst +=  8, x >>=  8;
    if (x & 0x0000'0000'0000'00f0ULL) rst +=  4, x >>=  4;
    if (x & 0x0000'0000'0000'000cULL) rst +=  2, x >>=  2;
    if (x & 0x0000'0000'0000'0002ULL) rst +=  1          ;
    return rst;
}
inline auto log_2(uint32_t x) { // also unsigned int
    uint32_t rst = 0;
    if (x & 0xffff'0000U) rst += 16, x >>= 16;
    if (x & 0x0000'ff00U) rst +=  8, x >>=  8;
    if (x & 0x0000'00f0U) rst +=  4, x >>=  4;
    if (x & 0x0000'000cU) rst +=  2, x >>=  2;
    if (x & 0x0000'0002U) rst +=  1          ;
    return rst;
}
inline auto log_2(uint16_t x) { // also unsigned short
    uint16_t rst = 0;
    if (x & 0x0000'ff00U) rst += 8, x >>= 8;
    if (x & 0x0000'00f0U) rst += 4, x >>= 4;
    if (x & 0x0000'000cU) rst += 2, x >>= 2;
    if (x & 0x0000'0002U) rst += 1         ;
    return rst;
}
inline auto log_2(uint8_t x) { // also unsigned char
    uint8_t rst = 0;
    if (x & 0x00f0U) rst += 4, x >>= 4;
    if (x & 0x000cU) rst += 2, x >>= 2;
    if (x & 0x0002U) rst += 1         ;
    return rst;
}
bit·math·c++
143 views
Comments
登录后评论
Sign In