x & (-x) 是位运算中的一个常见技巧，它的作用是保留 x 二进制表示中最低位的 1，其余位全部置 0。这一操作在算法中有重要应用（如树状数组、计算二进制最低有效位等）。

1. 原理分析

• 补码规则：在计算机中，负数以补码形式存储，-x 等于 ~x + 1（按位取反后加1）。
• 位与操作：x & (-x) 会将 x 的最低位 1 保留，其他位清零。

示例：

• 设 x = 12（二进制 1100）：

  x    = 0000 1100  
  -x   = 1111 0100  （补码形式）  
  x & (-x) = 0000 0100 → 十进制 4
  

• 保留的是 x 二进制中最低位的 1（即 4）。

2. 应用场景

场景1：快速找到最低位的1

int x = 10;  // 二进制 1010
int lowbit = x & (-x); 
cout << lowbit;  // 输出 2（二进制 0010）

场景2：统计二进制中1的个数

int count = 0, x = 12; // 1100
while (x) {
    x -= x & (-x); // 每次减去最低位的1
    count++;
}
cout << count;  // 输出 2（12的二进制有2个1）

场景3：树状数组（Fenwick Tree）

在树状数组中，x & (-x) 用于快速定位父节点或子节点，时间复杂度 O(log n)。

3. 扩展理解

• 如果 x 是0：结果为 0（因为没有 1 可保留）。
• 对负数也适用：补码规则保证运算正确性。

  int x = -12; // 补码表示：1111 0100（8位示例）
  int lowbit = x & (-x); 
  cout << lowbit; // 输出 4（0000 0100）
  

4. 总结

理解这个操作能帮助你更高效地解决位运算相关问题，尤其在算法竞赛或底层开发中非常实用！ 🚀