c中的k-=(k & (-k))是什么意思？

Question

一个计算sum的函数，我在使用此语句时遇到了..plz帮助

 int get_sum(int x) {
     int p = 0, k;
     for (k = x; k > 0; k -= k & -k)
         p += bit[k];
     return p;
 }

Answer 1

此表达式：

k -= (k & (-k))

是一种获取设置为正数的最低有效位并清除该位的巧妙方法。它依赖于两个负数的互补表示。

第一部分，k & (-k)隔离设置的最低有效位。例如：

1 & -1

   00000001
 & 11111111
   --------
   00000001

2 & -2

   00000010
 & 11111110
   --------
   00000010

24 & -24

   00011000
 & 11101000
   --------
   00001000

从原始k中减去此值后，其结果是清除该位。

因此，随着循环的进行，k的值一次减少1位，从最低位开始。例如，如果x是52，那么k将是52，然后是48 (52 - 4)，然后是32 (48 - 16)，并且将在0 (32 - 32)处退出。

至于程序为什么要这样做，这完全取决于bit的定义和它存储的内容。