c++ - （数字）和（-数字）的含义

Question

是什么意思 (number) & (-number)？我已经搜索了它，但无法找到含义

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

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

Answer 1

假设 2 的补码（或i无符号）-i等于~i+1。

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

它之所以有效，是因为 +1 实际上所做的是设置最低清除位，并清除所有低于该位的位。i因此，两者中唯一设置的~i+1位是最低设置位i（即 中的最低清除位~i）。低于 的位在 中清零~i+1，高于 的位在i和之间不相等~i。

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

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

在没有注释的情况下编写这样的代码通常是不可原谅的，但根据问题的领域，这可能是一个“明显”的值序列循环。]

Answer 2

我想我只需花一点时间来展示它是如何工作的。此代码为您提供最低设置位的值：

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修改。

Answer 3

假设负值使用二进制补码。然后-number可以计算为(~number)+1，翻转位并加 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

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 将表格视为代码:(