删除最低位

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

01001001010 – > 01001001000

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

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

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

呃…在你的例子中，你已经知道了位的索引。 然后很容易： 

 bits &= ~(1 << index);

这将屏蔽其索引为index的位，而不管其在值中的位置（最高，最低或中间）。 想想看，你当然可以使用你知道该位已经设置的事实，并使用XOR再次清除它： 

 bits ^= (1 << index);

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

如果您想要在不知道其索引的情况下屏蔽最低设置位，那么技巧是： 

 bits &= (bits - 1);

比如这里 。

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

 bits &= bits-1

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

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

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

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

或者x & (x - 1)可以正常工作并且更易于阅读。

有用的Bit Twiddling Hacks有一些计算零位的算法 – 这将帮助你实现你的getIndexOfLowestOrderBit函数。

一旦知道了所需位的位置，将其翻转为零非常简单，例如给定位位置，创建掩码并将其反转，然后将此掩码与原始值相对比 

 result = original & ~(1 << pos);

您不想删除最低位。 您希望将最低阶SET位置为零。

一旦你知道索引，你只需做2 ^索引和一个独占或。

在Java中使用Integer.lowestOneBit（）。

我不知道这是否可以快速比较，但我认为它有效： 

 int data = 0x44A; int temp; int mask; if(data != 0) { // if not there is no bit set temp = data; mask = 1; while((temp&1) == 0) { mask <<= 1; temp >>= 1; } mask = ~mask; data &= mask; }
Interesting Posts