13

谁能帮忙是什么n&-n意思？？以及它的意义是什么。

4

8 回答 8

30

这是一个古老的技巧，它给出了一个包含单个位的数字，即设置在n. 至少在二进制补码算术中，这在当今几乎是普遍的。

它起作用的原因：数字的负数是通过将数字反转，然后加 1 产生的（这是二进制补码的定义）。当你加 1 时，从底部开始设置的每一位都会溢出到下一个更高的位；一旦达到零位，这就会停止。那些溢出的位都将为零，而受影响的最后一位之上的位将相互取反，因此唯一剩下的位是停止级联的位 - 开始为 1 并反转为 0 的位。

PS如果您担心遇到补码算法，这里有一个适用于两者的版本：

n & (~n + 1)
于 2013-03-13T20:13:39.677 回答
8

在大多数人真正关心的几乎每个系统上，它都会为您提供 2 的最大幂，而 n 可以被 n 整除。

于 2013-03-13T20:07:46.867 回答
3

我相信判断 n 是否是 2 的幂是一个技巧。 (n == (n & -n)) IFF n 是 2 (1,2,4,8) 的幂。

于 2013-03-13T20:10:27.993 回答
3

N&(-N)将以二进制形式为您提供第一位的位置。例如：'1'N

N = 144 (0b10010000) => N&(-N) = 0b10000
N = 7 (0b00000111) => N&(-N) = 0b1

此技巧的一个应用是将整数转换为 2 的幂的总和。例如：

To convert 22 = 16 + 4 + 2 = 2^4 + 2^2 + 2^1
22&(-22) = 2, 22 - 2 = 20
20&(-20) = 4, 20 - 4 = 16
16&(-16) = 16, 16 - 16 = 0
于 2018-07-16T11:28:50.920 回答
2

这只是数字的按位和。负数表示为二进制补码。

例如，按位和 7&(-7) 是 x00000111 & x11111001 = x00000001 = 1

于 2013-03-13T20:11:03.400 回答
0

我会在Mark Randsom的精彩论述中添加一个不言自明的例子。

010010000 | +144 ~
----------|-------
101101111 | -145 +
        1 |
----------|-------
101110000 | -144 

101110000 | -144 & 
010010000 | +144
----------|-------
000010000 |   16`
于 2016-01-13T13:37:03.000 回答
-1

因为x & -x = {0, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32}forx从 0 到 32。它用于在某些应用程序的 for 序列中跳跃。应用程序可以存储累积的记录。

for(;x < N;x += x&-x) {
    // do something here
    ++tr[x];
}

循环遍历非常快，因为它寻找下一个二的幂来跳转。

于 2018-01-31T06:20:39.303 回答
-3

正如@aestrivex 所提到的，这是一种写作方式 1.即使我遇到了这个

for (int y = x; y > 0; y -= y & -y)

它只是意味着 y=y-1 因为
7&(-7) 是 x00000111 & x11111001 = x00000001 = 1

于 2015-12-27T09:01:59.257 回答