C#
bitOperation

Bit演算のちょっとしたテクニック備忘録。


初めに。

あくまで自分用のメモです。

最適化しきれていなかったり、時々間違えたりします。

間違いのご指摘や、何か他に良い方法をご存知でしたら、

コメントの方よろしくお願いいたします。


使用言語


  • C#


一覧



Abs

絶対値を返します。

public static int Abs(int num) => (num ^ (num >> 31)) - (num >> 31);



Sign

符号を返します。 (負数 => -1,零 => 0,正数 => 1)

public static int Sign(int num) => (num >> 31) - (-num >> 31);



Clamp

数値を a以上b以内 もしくは b以上a以内 に制限します。

public static int Clamp(int num, int a, int b) => (a + b + ((Abs(num - a) - Abs(num - b)) ^ ((b - a) >> 31)) - ((b - a) >> 31)) >> 1;



LSB

最下位ビットを取得します。

public static int LSB(int num) => num & -num;



MSB

最上位ビットを取得します。

public static int MSB(int num) => num & ~(FillMSBtoLowest(num) >> 1);



FillMSBtoLowest

最上位ビットから下位のビットすべてを1で埋めます。

public static int FillMSBtoLowest(int num)

{
num |= num >> 1;
num |= num >> 2;
num |= num >> 4;
num |= num >> 8;
return num | num >> 16;
}



FillLSBtoHighest

最下位ビットから上位のビットすべてを1で埋めます。

public static int FillLSBtoHighest(int num)

{
num |= num << 1;
num |= num << 2;
num |= num << 4;
num |= num << 8;
return num | num << 16;
}



BitCount

立っているビットの個数(1の個数)を取得します。

public static int BitCount(int num)

{
num = (num & 0x55555555) + ((num >> 1) & 0x55555555);
num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
num = (num & 0x0F0F0F0F) + ((num >> 4) & 0x0F0F0F0F);
num = (num & 0x00FF00FF) + ((num >> 8) & 0x00FF00FF);
return (num & 0x0000FFFF) + ((num >> 16) & 0x0000FFFF);
}



NLZ

最下位ビットより下位にある零の個数を取得します。

public static int NLZ(int num) => BitCount((num & -num) - 1);



NTZ

最上位ビットより上位にある零の個数を取得します。

public static int NTZ(int num) => BitCount(~FillMSBtoLowest(num));



DigitsOfBits

すべての立っているビットのNLZを取得します。

    public static IEnumerable<int> DigitsOfBits(int num)

{
for(; num != 0; num &= ~(num & -num)) yield return NLZ(num);
}



EnumerateAllSubsets

0 ~ num-1までの集合の部分集合を列挙します。

public static IEnumerable<IEnumerable<int>> EnumerateAllSubsets(int num)

{
if(num > 31) throw new ArgumentOutOfRangeException();

for(int bit = 0; bit < (1 << num); bit++) yield return DigitsOfBits(num);
}



変更履歴

-2019/03/13-

FillMSBtoLowest, FillLSBtoHighestの

return文に「num |」が無い

という致命的なミスがあったため修正。

NLZ, NTZ, DigitsOfBits, EnumerateAllSubsetsを追加。