找到最低的设置位 [英] Find the lowest set bit

问题描述

我有5位数字，例如

10000
01000
00100

如果我的计算中只有一位，我没问题.

If only one bit is on in my calculation i have no problem.

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

but if 2 bits are on then I want to select only the first on bit for example

10010

我想将其视为2而不是数字18

i want to treat it as 2 instead of the number 18

在这种情况下我可以使用按位运算吗?

is there any bitwise operation which may i use in such sitution?

推荐答案

由于您只想隔离它，而不要获取它的索引，因此很容易:

Since you only want to isolate it, not get its index, it's easy:

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

之所以起作用，是因为如果您对一个数字进行二进制补码求反，则首先对其进行补码，将最低置位右边的所有零设置为1，将最低置位右边的所有零设置为零，然后将其加一，将右边的位变为零，最低的置位再次变为1，从而结束了进位链.因此，数字的取反具有相同的右侧部分"，直到并包括最低设置位，但最低设置位左侧的所有内容都是输入的补码.因此，如果将数字的按位与取反，则最低设置位左侧的所有位都将被抵消.

It works because if you take the two's complement negation of a number, first you complement it, setting all zeroes to the right of the lowest set bit to one and the lowest set bit to zero, then you add one, setting the bits on the right to zero and the lowest set bit becomes one again, ending the carry chain. So the negation of the number has the same "right part", up to and including the lowest set bit, but everything to the left of the lowest set bit is the complement of the input. Thus if you take the bitwise AND of a number with its negation, all the bits to the left of the lowest set bit are cancelled out.

这篇关于找到最低的设置位的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！