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

我们现在取 and 的按位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 位。

Answer 2

返回 log2(n & -n) + 1;

这可能会对您有所帮助。

Answer 3

二元运算符通常影响数字的所有位。因此，没有特殊功能可以仅获取数字中的第一个“1”。但是你可以试试这样的功能：

function filterFirstFoundBit(number)
{
    for (var i = 0; i < 32; i++) {
        if ((1 << i) & number)
        {
            return 1 << i;
        }
    }
    return number;
}
document.write(filterFirstFoundBit(9)); //10010​​​​​​​​

在这里试试

Answer 4

function isolateLowestBit(input)
{
  mask = 1;
  while (mask <= input)
  {
    if (mask & input)
    {
      // found match - mask is set to the value of the lowest bit
      return mask;
    }

    mask *= 2;  // shift up mask by one bit
  }

  // no match
  return 0;
}

请注意，Javascript 中的按位运算不是一个好主意，因为 Javascript 数字不是自然整数。