刪除最低位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

回答

相關問題