Edited at

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


初めに。

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

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

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

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

関数の名称についても、いい名称がありましたらコメント下さると有難いです。


使用言語


  • C#


一覧

Standard

- Abs

- Sign

- InternalOrZero

- InternalOrDefault

- Clamp

- ClampNonRestriction

- LSB

- MSB

- FillMSBtoLowest

- FillLSBtoHighest

- BitCount

- NLZ

- NTZ

- Max

- Min

- GreaterThanZero

- LessThanZero

- GreaterOrEqualZero

- LessOrEqualZero

- NotZero

Set

- DigitsOfBits

- EnumerateAllSubsets


Standard


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



InternalOrZero

数値がa以上b以下であった場合そのまま返し、

それ以外であった場合0を返します。

a < b である必要があります。

public static int InternalOrZero(int num, int a, int b) => num & ~(((num - a) >> 31) | ((b - num) >> 31));



InternalOrDefault

数値がa以上b以下であった場合そのまま返し、

それ以外であった場合任意の数を返します。

a < b である必要があります。

public static int InternalOrDefault(int num, int a, int b, int @default)

{
var sab = ((num - a) >> 31) | ((b - num) >> 31);
return (num & ~sab) + (@default & sab);
}



Clamp

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

a < b である必要があります。

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



ClampNonRestriction

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

public static int ClampNonRestriction(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) => (FillMSBtoLowest(num) + 1) >> 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

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

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



NTZ

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

public static int NTZ(int num) => ((num >> 31) | (-num >> 31)) & BitCount((num & -num) - 1);



NextPowerOfTwo

より大きな2の冪を返します。

public static int NextPowerOfTwo(int num) => FillMSBtoLowest(num) + 1;



Max

より大きい方の数を返します。

public static int Max(int a, int b)

{
var mask = (a - b) >> 31;
return b & mask | a & ~mask;
}



GreaterThanZero

0より大きければ1を、0以下であれば0を返します。

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



LessThanZero

0未満であれば1を、0以上であれば0を返します。

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



GreaterOrEqualZero

0以上であれば1を返し、0未満であれば0を返します。

public static int GreaterOrEqualZero(int num) => 1 + (num >> 31);



LessOrEqualZero

0以下であれば1を返し、0より大きければ0を返します。

public static int LessOrEqualZero(int num) => 1 + (-num >> 31);



NotZero

0以外の数であれば1を返し、0ならば0を返します。

public static int NotZero(int num) => ~((num >> 31) | (-num >> 31));



Set


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を追加。

-2019/05/05-

Upper, Lower, InternalOrZeroを追加。

今までのClampをClampNonRestrictionに変更し、新たにClampを追加。

戻るボタン()を追加。

-2019/05/05 (2)-

InternalOrDefaultを追加。

-2019/08/19-

標準的な演算と集合用の演算をStandardとSetに分割。

MSBを少々高速化。

NextPowerOfTwo, Max, Min, GreaterThanZero, GreaterOrEqualZero, LessThanZero, LessOrEqualZero, NotZeroを追加。

-2019/08/20-

NTZとNLZが逆という致命的なミスを修正しました。

-2019/08/22-

Upper, Lowerを削除しました。

(Min, Maxと機能が同等なため。)