减1

由于我们对十进制比二进制更熟悉，所以有时看看十进制中发生了什么会有所帮助。
在十进制中减去1会发生什么？例如1786000 - 1 = 1785999。
如果你从十进制的正数x中减去1：

• x右边的所有零都变成了9;
• x的最右边的非零数字变成1少;
• 其他数字不受影响。

现在，在二进制中，它的工作原理完全相同，除了我们只有0 1而不是0 123456789。
如果你从二进制数x中减去1：

• x右边的所有零都变成1;
• x的最右边的非零比特变成0;
• 其他比特不受影响。

负数呢？令人高兴的是，使用2的补数的表示是负数的行为完全像正数。实际上，当查看x的位时，您可以从x中减去1，而无需知道x是有符号整数还是无符号整数。

x & (x-1)

让我们从一个例子开始：x = 01011000 .我们可以用我刚才解释的方法减去1：

x   = 01011000
x-1 = 01010111

现在，按位与运算x & (x-1)的结果是什么？我们在每一列中取两个位;如果它们都是1，我们写1;如果其中至少有一个是0，我们写0。

x       = 01011000
x-1     = 01010111
x&(x-1) = 01010000

发生什么事了？

• x右边的所有零保持为零;
• x的最右边的1由于x-1而变为0;
• 所有其他位不受影响，因为它们在x和x-1中是相同的。

结论：我们已经将x的最右边的1置零，其他位不受影响。

让我们来看看x-1是做什么的。假设x是值'???? 1000（？为0或1）
=> x-1 = ???? 0111
=> x & (x-1) = ???? 0000
无论最右边的1放在x中的哪个位置，它都非常相似。
请求的示例：
x=00001111
=> x-1=00001110
=> x & (x-1) = 00001110
P.s. x-1 = 00001110 - 00000001 (<=> 00001110 + 11111111)

根据Brian Kernighan's Algorithm，它用于计算给定数量中的设置位，从数字x中减去1将从其最右边的设置位开始反转所有位。
让
x = 14，在二进制中是1110。这里，从右数第二位是最右边的设置位。
x - 1 = 13，在二进制中是1101。可以清楚地观察到，从右起第2位开始的位被反转。
现在，如果我们对这两个数字进行按位的AND运算，即x &（x-1），我们将从数字x的最右边的设置位取消设置。看看下面的例子，
如果，数字x最初是2的幂，那么与**（x-1）进行逐位AND将导致0**。比如说，
这是因为，数字x，即2的幂，在其二进制表示中只有单个设置位。
类似地，如果我们尝试对数字x进行按位AND，对数字**（x-1）进行按位NOT*，那么它只会设置结果数字中的最右边的位。即x & [~（x-1）]。检查下面的例子，
x = 14
x - 1 = 13
因此，~(x-1)将是，

注：~(x-1)项的计算结果为-x。here提供了相同的解释

因此，我们认为，
从右边起的第2位是数字x（14）的二进制表示中最右边的设置位，是结果数字中唯一的设置位。也是2的幂，因为结果中只有一个设置位。