删除最低位

Question

给定二进制数,删除最低位的最快方法是什么？

01001001010 - > 01001001000

它将在代码中用于迭代变量的位.伪代码如下.

while(bits != 0){
  index = getIndexOfLowestOrderBit(bits);
  doSomething(index);
  removeLowestOrderBit(bits);
}

我正在考虑使用的可能语言是C和Java.

Answer 1

这是我到目前为止所得到的,我想知道是否有人可以击败这个.

bits &= bits-1

Answer 2

呃...在你的例子中,你已经知道了位的索引.然后很容易:

bits &= ~(1 << index);

这将屏蔽其索引所在的位index,而不管其在值中的位置(最高,最低或中间).想想看,你当然可以使用你知道该位已经设置的事实,并使用XOR再次清除它:

bits ^= (1 << index);

这样可以节省反转,这可能是一台机器指令.

如果你想要掩盖最低设置位,而不知道它的索引,那么诀窍是:

bits &= (bits - 1);

见这里的实例.

Answer 3

您可以使用找到最低的设置位x & (~x + 1)。例：

    x：01101100
 〜x + 1：10010100
       --------
       00000100

清除最低设置位将变为x & ~(x & (~x + 1))：

          x：01101100
〜（x＆（〜x + 1））：11111011
             --------
             01101000

或x & (x - 1)效果也一样，而且更易于阅读。