什么是 Lowbit?

一个正整数的 Lowbit 值就是从二进制低位往高位寻找首次出现的1,及其后面低位0组成的新二进制序列。 即寻找数字二进制低位中形如1+若干零的新序列。

例如:

  • 十进制 12 的二进制是1100,最后的1+若干零100, 所以12的 Lowbit 是二进制100即十进制的 4。 即Lowbit(12)=4

同理:

  • Lowbit(6)=2,因为6的二进制是110
  • Lowbit(4)=4,因为4的二进制是100
  • Lowbit(16)=16,因为16的二进制是10000

如何快速求出给定正整数的 Lowbit 值?

假定在 8 比特存储单元下,给定的数 N 的二进制形式是$X_{7}X_{6}X_{5}X_{4}X_{3}100$,显然待求的 Lowbit(N) = 100。

只要想办法构造出$\bar{X_{7}}\bar{X_{6}}\bar{X_{5}}\bar{X_{4}}\bar{X_{3}}100$, 和原序列按位相与就能消掉所有的$X_{i}$,得到Lowbit(N)。

那我们把序列$X_{7}X_{6}X_{5}X_{4}X_{3}100$每一位按位取反, 可是只能得到$\bar{X_{7}}\bar{X_{6}}\bar{X_{5}}\bar{X_{4}}\bar{X_{3}}011$, 和我们期望的$\bar{X_{7}}\bar{X_{6}}\bar{X_{5}}\bar{X_{4}}\bar{X_{3}}100$还有区别, 但是只需要再把末尾011加上一,就变成了100。在代码中只需要执行$\backsim{N}+1$即可。

最后拿$X_{7}X_{6}X_{5}X_{4}X_{3}100$和$\bar{X_{7}}\bar{X_{6}}\bar{X_{5}}\bar{X_{4}}\bar{X_{3}}100$相与, 代码是$N \And (\backsim N+1)$

实现代码

int lowbit(int n)
{
	return n & (~n + 1);
}

改进形式

  • $\backsim N+1$ 是对 N 取反加一。而计算机中整数以补码形式存储,对 N 取反加一就是求 N 的相反数的过程。 所以$\backsim N+1$可简写为$-N$。
  • 有时需要频繁调用 Lowbit 函数,为了加快速度可以使用宏#define lowbit(N) ((N)&-(N)),或者是更安全的内联函数。
inline int lowbit(int n)
{
	return n & -n;
}

文章为 C#.NAME 原创,禁止转载。