lowbit(x) 详解（CSP‑J/NOIP高频）

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

作用：取出x二进制中，最低位的1以及后面所有的0，返回这个数值。

示例：

• \((x=6)\) 二进制：0110
• lowbit(6) = 0010 = 2
• \((x=8)\) 二进制：1000
• lowbit(8) = 1000 = 8
• \((x=5)\)：0101 → lowbit = 0001 = 1

原理（补码）

C++中负数 -x = ~x + 1（按位取反再加1）

例子 (x=6)：

 x = 0110
~x = 1001
-x=~x+1 = 1010

x & (-x)
0110
1010
----
0010   →结果2

最低位的1，在取反之后变成0；加1之后，这一位变回1，右边全部置0；高位全部取反。 按位与 & 之后，只保留最低位那一个1。

常用场景

1. 树状数组(BIT)核心操作

//下标更新
while(i <= n){
    tree[i] += val;
    i += lowbit(i);
}
//查询前缀和
while(i>0){
    ans += tree[i];
    i -= lowbit(i);
}

1. 判断是不是2的整数次幂

如果 x > 0 并且 lowbit(x) == x，说明x是2的幂。 例：8 lowbit=8，是2的幂；6 lowbit=2≠6，不是。

1. 统计数字二进制里面1的个数

int cnt =0;
while(x>0){
    x -= lowbit(x);
    cnt++;
}
//cnt就是二进制中1的总个数

测试样例表

⚠️注意：x=0，lowbit(0)=0。0没有最低位的1。

思考题：lowbit(12)等于多少？

答案 12二进制 1100，lowbit = 4

补充坑：如果用无符号unsigned int，-x行为和有符号int不一样，lowbit一般只用于正整数。

树状数组极简小题（只用lowbit）

已知数组 a[5]={1,2,3,4,5}，下标从1开始。 树状数组tree[]，初始全部为0。 执行单点更新：add(3, 10)，含义：下标3位置加上数值10。

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

// 单点加：pos位置 += val
void add(int pos, int val){
    while(pos <= 5){
        tree[pos] += val;
        pos = pos + lowbit(pos);
    }
}

问题1：模拟 add(3,10)，写出每一轮循环pos的值分别是多少？

解析答案 初始 pos = 3

1. pos=3，lowbit(3)=1 → pos +=1 → pos=4
2. pos=4，lowbit(4)=4 → pos +=4 → pos=8，8>5，循环结束。

pos遍历顺序：3 → 4 所以tree[3] +=10，tree[4] +=10。

问题2：查询前缀和，query(x)求a[1]+a[2]+…+a[x]

int query(int pos){
    int res = 0;
    while(pos > 0){
        res += tree[pos];
        pos = pos - lowbit(pos);
    }
    return res;
}

调用 query(5)，写出每一轮pos变化。

答案 pos=5，lowbit(5)=1 → pos=4 pos=4，lowbit(4)=4 → pos=0，循环结束。 pos序列：5 →4

关键记忆

1. add更新：pos += lowbit(pos)，往大树父亲走
2. query查询：pos -= lowbit(pos)，往小区间退
3. lowbit只抓最靠右的1

思考题

lowbit(14)=?

答案 14二进制：1110，lowbit = 2

拓展小坑

如果pos=0传入lowbit，0 & (-0)=0。

• add(0, x) 会死循环！因为 pos +=0，pos永远不变。 👉树状数组下标必须从1开始，不能用0下标。