Удаление младшего бита

Question

Учитывая двоичное число, каков самый быстрый способ удаления бит младшего порядка?

01001001010 -> 01001001000

Он будет использоваться в коде для перебора битов переменной. Далее следует псевдокод.

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

Возможные языки, которые я рассматриваю, являются C и Java.

Answer 1

Uh ... В вашем примере вы уже знаете индекс бит. Тогда это легко:

bits &= ~(1 << index); 

Это будет маскировать бит, индекс которой index, независимо от его положения в стоимости (высокий, низкий, или в-между). Давай думать об этом, вы, конечно, можете использовать тот факт, что вы знаете бит уже установлен, и использовать XOR, чтобы столкнуть его снова ясно:

bits ^= (1 << index); 

Это экономит инверсию, которая, вероятно, инструкция одна машина ,

Если вместо этого вы хотите, чтобы замаскировать множество бит низкий, не зная его индекс, уловка:

bits &= (bits - 1); 

См here, например.

Answer 2

Это то, что у меня есть до сих пор, мне интересно, может ли кто-нибудь победить.

bits &= bits-1 

Answer 3

Вечно полезно Bit Twiddling Hacks имеет некоторые algorithms for counting zero bits - это поможет вам реализовать функцию getIndexOfLowestOrderBit.

Как только вы знаете положение требуемого бита, перевертывание его до нуля довольно просто, например. учитывая немного положение, создать маску и инвертировать его, затем И эту маску против исходного значения

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

Answer 4

Вы не хотите, чтобы удалить младший бит порядка. Вы хотите использовать ZERO бит SET младшего порядка.

Как только вы знаете индекс, вы просто делаете 2^индекс и эксклюзивный или.

Answer 5

Я не знаю, если это сравнимо быстро, но я думаю, что это работает:

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

Answer 6

В Java используют Integer.lowestOneBit().

Answer 7

Вы можете найти самый младший бит, используя x & (~x + 1). Пример:

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

расчистке самый низкий набор бит становится x & ~(x & (~x + 1)):

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

Или x & (x - 1) работает так же хорошо и легче читать.