删除最低位bit

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

01001001010 - > 01001001000

这将在代码中用于迭代变量的比特。伪代码如下。

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

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

来源

2009-09-24 dharga

什么是最快的？执行时间，实施时间还是理解时间？ – 2009-09-24 15:02:36

呃......在你的例子中，你已经知道该位的索引。然后，它很简单：

bits &= ~(1 << index);

这将屏蔽掉其索引index位，无论其在价值立场（最高，最低，或者在两者之间）的。试想想，你当然可以使用的事实，你知道该位已经被设置，并使用XOR再次明确敲它：

bits ^= (1 << index);

这节省了反转，这可能是一个机器指令。

如果你不是想掩盖掉最低设置位，不知道它的指数，诀窍是：

bits &= (bits - 1);

见here例如。

来源

2009-09-24 14:41:11 unwind

对不起，我的意思是最低...但仍然，我想避免转移 – dharga 2009-09-24 14:42:39

是的，但我认为问题的全部是你不知道位的索引。 – 2009-09-24 14:42:58

我认为OP的意思是如果你不知道要删除的位置是 – Chii 2009-09-24 14:43:44

这就是我到目前为止，我想知道如果有人能击败这一点。

bits &= bits-1

来源

2009-09-24 14:44:29 dharga

不断有用Bit Twiddling Hacks有一些algorithms for counting zero bits - 这将帮助你实现你的getIndexOfLowestOrderBit功能。一旦知道所需位的位置，将其翻转为零就相当简单了，例如，给定一个位置，创建掩码并将其反转，然后将此掩码与原始值进行比较

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

来源

2009-09-24 14:48:27

您不想删除最低位。您想要将最低位SET位置零。

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

来源

2009-09-24 14:55:55

我不知道这是不是媲美快，但我认为它的工作原理：

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; 
}

来源

2009-09-24 15:03:55 skorgon

哇！我无言以对。 – dharga 2009-09-24 16:51:26

在Java中使用Integer.lowestOneBit（）。

来源

2009-09-24 15:08:03 starblue

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

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

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

 
      x: 01101100 
~(x&(~x+1)): 11111011 
      -------- 
      01101000

或者x & (x - 1)作品一样好，更容易阅读。

来源

2009-09-24 21:08:02

删除最低位bit

回答

相关问题