lowbit

一句话理解

lowbit(x) 是 x 的最低位 1 以及它右边的 0。

为什么要学

树状数组的引擎，也用来枚举子集。

讲解

lowbit(x)=x&-x。12 是 1100₂，lowbit 是 4。

每次 x-=lowbit(x) 可以枚举所有 1 位。

例子

int lowbit(int x) { return x & -x; }

利用补码：-x 是取反加一，与完只留下最低 1。

常见错误

• x=0 时 lowbit 是 0，循环不会推进。
• 对负数随便用。