数字(number)和负数(-number)的含义是什么？

Question

(number) & (-number)

的意义是什么？我已经搜索过了但找不到它的含义。

我想在 for 循环中使用 i & (-i)，例如：

for (i = 0; i <= n; i += i & (-i))

- Aseem Goyal

---

如果你不知道它的意思，为什么还要使用它？ - Rowland Shaw

你想在循环中使用它，但你不知道它是做什么的？ - Mike

我希望i被声明为无符号类型。 - CB Bailey

'i=0' 的初始化器会使得循环无限，因为 'i&(-i)' 也是0。循环的内容是什么？ - Skizz

在给定的代码中，当 i=0 时，i&(-i)也是0，因此只要循环体不改变 i，循环就会无限进行。你说得对，在 i > 0 的情况下，i&(-i) != 0，但在问题中，i 是零。 - Skizz

Answer 1

假设使用2的补码（或者i是无符号整数），-i等于~i+1。

i & (~i + 1)是提取i的最低位的技巧。

它能够运作的原因是+1实际上是将最低清零位设置为1，然后清除它下面的所有位。所以，在i和~i+1中唯一被设置的位就是i中的最低置位（即~i中的最低清零位）。比它低的位在~i+1中都被清除了，而比它高的位在i和~i之间也是不相等的。

除非循环体修改i，否则在循环中使用它似乎有点奇怪，因为i = i & (-i)是幂等操作：执行两次会再次得到相同的结果。

[编辑：在其他地方的一条评论中，您指出代码实际上是i += i & (-i)。因此，对于非零的i，它会清除i的最低组置位，并设置上面的下一个清零位，例如101100 -> 110000。对于没有高于最低置位的清零位的i（包括i = 0），它将i设置为0。因此，如果不是因为i从0开始，每次循环都会增加i至少两倍，有时更多，直到最终超过n并中断或进入0并无限循环。]

如果不加注释就编写这样的代码通常是不可原谅的，但根据问题领域的不同，也许这是一个“显而易见”的值循环序列。

- Steve Jessop

---

看起来他要在循环体内改变i的值..我认为i=i&(-i)是为了保持它为“正数”。 - Anirudha

@Anirudha：如果意图保持正数，则在仅设置最高位的情况下不起作用。但无论如何，提问者在评论中说“i”是无符号的。 - Steve Jessop

Answer 2

假设使用二进制补码表示负数。那么可以将-number计算为(~number)+1，即取反加一。

例如，如果number = 92，则其在二进制下的表示如下：

number               0000 0000 0000 0000 0000 0000 0101 1100
~number              1111 1111 1111 1111 1111 1111 1010 0011
(~number) + 1        1111 1111 1111 1111 1111 1111 1010 0100
-number              1111 1111 1111 1111 1111 1111 1010 0100
(number) & (-number) 0000 0000 0000 0000 0000 0000 0000 0100

你可以看到上面的例子，(number) & (-number) 让你得到了最小位数。

你可以在 IDE One 上在线运行代码：http://ideone.com/WzpxSD 这是一些 C 代码：

#include <iostream>
#include <bitset>
#include <stdio.h>
using namespace std;

void printIntBits(int num);
void printExpression(char *text, int value);

int main() {
  int number = 92;

  printExpression("number", number);
  printExpression("~number", ~number);
  printExpression("(~number) + 1", (~number) + 1);
  printExpression("-number", -number);
  printExpression("(number) & (-number)", (number) & (-number));

  return 0;
}

void printExpression(char *text, int value) {
  printf("%-20s", text);
  printIntBits(value);
  printf("\n");
}

void printIntBits(int num) {
    for(int i = 0; i < 8; i++) {
        int mask = (0xF0000000 >> (i * 4));
        int portion = (num & mask) >> ((7 - i) * 4);
      cout << " " << std::bitset<4>(portion);
    }
}

这里还有一个C# .NET版本的代码：https://dotnetfiddle.net/ai7Eq6

- Luis Perez

Answer 3

我想花一点时间来展示这个代码是如何工作的。以下代码可以得到二进制数中最低位为1的值：

int i = 0xFFFFFFFF; //Last byte is 1111(base 2), -1(base 10)
int j = -i;         //-(-1) == 1
int k = i&j;        //   1111(2) = -1(10) 
                    // & 0001(2) =  1(10)
                    // ------------------
                    //   0001(2) = 1(10). So the lowest set bit here is the 1's bit


int i = 0x80;       //Last 2 bytes are 1000 0000(base 2), 128(base 10)
int j = -i;         //-(128) == -128
int k = i&j;        //   ...0000 0000 1000 0000(2) =  128(10) 
                    // & ...1111 1111 1000 0000(2) = -128(10)
                    // ---------------------------
                    //   1000 0000(2) = 128(10). So the lowest set bit here is the 128's bit

int i = 0xFFFFFFC0; //Last 2 bytes are 1100 0000(base 2), -64(base 10)
int j = -i;         //-(-64) == 64
int k = i&j;        //   1100 0000(2) = -64(10) 
                    // & 0100 0000(2) =  64(10)
                    // ------------------
                    //   0100 0000(2) = 64(10). So the lowest set bit here is the 64's bit

对于无符号值，结果始终是最低位设置的值。

考虑到您的循环：

for(i=0;i<=n;i=i&(-i))  

没有任何位被设置（i=0），所以在这一操作的增量步骤中，您将得到一个0。因此，除非 n=0 或者 i 被修改，否则这个循环会一直进行下去。

- Mike

---

它是 i += i & (-i); 有人编辑了我的帖子并将其改为 i = i & (-i); - Aseem Goyal

@aseem - 好的，但这并不重要，除非在循环内部更改了i（这可能就是为什么它被编辑的原因）。 i=0，因此i&(-i)=0，因此i+=i&(-i)只会添加0，所以i=0+0&(-0)，它仍然是0。 - Mike

Answer 4

操作 i & -i 用于隔离相应整数的最低非零位。

• 在二进制表示法中，num可以表示为a1b，其中a表示最后一位之前的二进制数字，b表示最后一位之后的零。

• -num等于(a1b)¯ + 1 = a¯0b¯ + 1。b由所有零组成，因此b¯由所有一组成。

  • -num = (a1b)¯ + 1 => a¯0b¯ + 1 => a¯0(0…0)¯ + 1 => ¯0(1…1) + 1 => a¯1(0…0) => a¯1b

• 现在，num & -num => a1b & a¯1b => (0..0)1(0..0)

例如，如果 i = 5。

| iteration | i | last bit position | i & -i|
|-------- |--------|-------- |-----|
| 1    | 5 = 101     | 0 | 1 (2^0)|
| 2    | 6 = 110     | 1 | 2 (2^1)|
| 3    | 8 = 1000    | 3 | 8 (2^3)|
| 4    | 16 = 10000  | 4 | 16 (2^4)|
| 5    | 32 = 100000 | 5 | 32 (2^5)| 

这个操作主要用于二叉索引树中，在树上向上和向下移动。

PS：由于某些原因，stackoverflow将表格视为代码 :(

- rohit kamal