【アルゴリズム】いろいろビット演算

最下位ビット以外を0にする

code:cs

var value = x & -x;

最下位ビットを0にする

code:cs

var value = x & x - 1;

最上位ビット以外を0にする

code:cs

x = x | (x >> 1);

x = x | (x >> 2);

x = x | (x >> 4);

x = x | (x >> 8);

x = x | (x >> 16);

var value = x ^ (x >> 1);

ビット数を数える

code:cs

int CountBit(int source)

{

source = (source & 0x55555555) + (source >> 1 & 0x55555555);

source = (source & 0x33333333) + (source >> 2 & 0x33333333);

source = (source & 0x0f0f0f0f) + (source >> 4 & 0x0f0f0f0f);

source = (source & 0x00ff00ff) + (source >> 8 & 0x00ff00ff);

return (source & 0x0000ffff) + (source >> 16 & 0x0000ffff);

}

ビットを反転する

code:cs

public int ReverseBit(int source)

{

source = (source & 0x55555555) << 1 | (source >> 1 & 0x55555555);

source = (source & 0x33333333) << 2 | (source >> 2 & 0x33333333);

source = (source & 0x0f0f0f0f) << 4 | (source >> 4 & 0x0f0f0f0f);

source = (source & 0x00ff00ff) << 8 | (source >> 8 & 0x00ff00ff);

source = (source & 0x0000ffff) << 16 | (source >> 16 & 0x0000ffff);

return source;

}

最下位ビットがどこに有るか調べる

code:cs

var value = CountBit((x & -x) - 1);