【进阶指南学习笔记】lowbit

lowbit(n)是n最低一位的1和后面的所有0构成的数。

实现:lowbit(n) = (~n+1) & n = (-n) & n,原理是补码原理。(int中n + (-n) = (2^{32})

拓展问题:我有lowbit(n)了,可我怎么知道它是2的多少次幂?

大常数方法有很多,这里介绍一个牛逼的O(1)方法。

性质:any k ∈ [0, 35], (2^k) mod 37互不相等。

int H[37];
for (int i = 0; i < 36; ++i) {
    H[(1ll << i) % 37] = i;
}
// lowbit(i)的位就是H[lowbit(i) % 37]啦!
原文地址:https://www.cnblogs.com/maomao9173/p/13781525.html