javascript - 找到最低的设置位

Question

我有 5 位数字，例如

10000
01000
00100

如果在我的计算中只有一位开启，我没有问题。

但如果 2 位打开，那么我只想选择第一个打开的位，例如

10010

我想把它当作 2 而不是数字 18

在这种情况下，我可以使用任何按位运算吗？

Answer 1

因为你只想隔离它，而不是获取它的索引，所以很简单:

function firstSetBit(number)
{
    return number & -number;
}

它的工作原理是因为 -number 的二进制表示，称为“二进制补码”。

为了得到一个更好的例子，假设数字是 888，它是二进制的 0000001101111000。前导零构成 16 位数字，但这适用于任何整数大小。

要获得一个数的二进制补码，我们首先对其进行补码，将所有 1 设置为 0，将所有 0 设置为 1。

          number: 0000001101111000
      complement: 1111110010000111

然后我们给它加 1。

          number: 0000001101111000
      complement: 1111110010000111
           add 1: 1111110010001000

请注意，如果最右边的位是 1，这将创建一个进位，将所有 1 翻转为 0，直到达到 0。

这个数字现在实际上也是 -number 的二进制表示。

          number: 0000001101111000
      complement: 1111110010000111
           add 1: 1111110010001000
         -number: 1111110010001000

我们现在取 number 和 -number 的按位 &。

          number: 0000001101111000
         -number: 1111110010001000
number & -number: 0000000000001000

在目标位的右侧，number 前提是全 0。 -number 也全为 0，因为它们在 +1 期间被翻转了。 0 和 0 的按位与产生 0。

在目标位，number 也有一个 1，前提也是如此。 -number 也有一个 1，因为取反将它变成 0 并进位将它放回 1。1 和 1 的按位与产生 1。

在目标位的左侧，number 和 -number 总是形成 0 和 1 对，因为它不受二进制补码过程的 +1 步骤的干扰。 1 和 0 的按位与产生 0。

因此，我们已经证明 number & -number 产生了数字的最低 1 位。