比較的高度なビット演算

はじめに

有名な ビット演算のハックをまとめたページがある。

• Bit Twiddling Hacks By Sean Eron Anderson
  • 可搬性についてしっかり検討されている
  • ユースケースで引ける（逆引き）なので便利
• awesome-bits By Keon Kim
  • 説明がない分簡潔
  • github のマークダウンのレンダリングは読みやすい
• Hacker's Delight Second Edition
  • この業界のバイブル
  • 第2章が無料公開されていてそこだけでもすごい情報量

使えるケースが多いけど、ぱっと見理解ができない ハック を理解した際のメモ。ポータビリティは一旦脇に置き、符号あり/なし32ビットで考える。対話的にやりたいので 検証の多くは JavaScript上で行った（Cとの大きな違いは、unsigned な場合 右シフトには >>> が必要ということ）。

コレじゃない方

n が a か b かのどちらかであることがわかっている。その他方を知りたい時の操作は n ^ a ^ bとなる。XOR は2回実施すると 0 になるので a^a^bは0^bつまりbになる。b^a^bも交換可能なので a^b^bつまりa^0つまりaになる。 もう少し詳しい説明はWikipedia .

const theOther = (n, a, b) => n ^ a ^ b;

theOther(32, 32, 100) // 100
theOther(100, 32, 100) // 32

ビットのスワップ

i 番目と j番目のビットを交換する操作。1 ビットだけ交換してもよいのだが、より一般に iから左に続く長さLの列と jから左に続く長さLの列を交換するとしても計算量はそれほど変わらない。以下がその実装と、実行例:

const bitsSwap = (n, i, j, L = 1) => {
  const x = ((n >>> i) ^ (n >>> j)) & ((1 << L) - 1);
  return n ^ ((x << i) | (x << j));
};

bitsSwap(0b11110000, 1, 5);    // 11010010
bitsSwap(0b11110000, 1, 5, 2); // 10010110
bitsSwap(0b00101111, 1, 5, 3); // 11100011

簡単のため L=1 で考察(簡単に一般化できる）。x は i番目のビット値 I と j番目のビット値 J を XOR で混ぜ込んだ I ^ J となる。これに I を XOR してあげると J になるし、逆に J を XOR してあげると I になる（一つ上のコレじゃない方を参照）。 したがって マスク(x << i) | (x << j) を作って XOR すれば、狙った結果になる。列同士がオーバーラップしてはいけないので注意。

べき判定

べき判定は n && !(n & (n - 1)) となる。前半部は非ゼロを主張しているだけなので、以降 n は非ゼロの場合のみ考える。ポイントは n & (n - 1)という操作。[n が負の場合]: n-1をしても 負であるので MSBはセットされたまま。よって AND すると少なくともMSBはセットされるので非ゼロ。[正でべきの場合]、以下のように 唯一の1でボローが発生して 結果 1 だらけになる。ANDすると 0 になる。

1<<5      00000000000000000000000000100000
(1<<5)-1  00000000000000000000000000011111

[正でべきでない場合]、n-1においてボローが起きるとしても、それが一番左の1以外である。よって n-1 でも 一番左の1はセットされたまま。よってANDすると非ゼロになる。以上すべての場合で意図通りの動作をする。

const isPowered = n => n && !(n & (n - 1));

[1, 2, 4, 8, 16].every(isPowered); // true
[-4, -3, 0, 3, 9].every(x => !isPowered(x)); // true 

符号のテスト

2の補数表現では 最上位ビットのみで符号が判定可能。つまり n >> 31 の値が 「-1 なら負で 0 なら非負」とわかる。1 | (n >> 31) にすると「負なら -1 で非負なら 1」になるので使いやすくなる。 (n > 0) - (n < 0) は「負なら -1, ゼロなら 0, 正なら 1」となる。

sign.js

// equivalents to : n => (n > 0) ? 1 : (n === 0) ? 0 : -1 
const sign = n => (n > 0) - (n < 0);

sign(4) // 1
sign(0) // 0
sign(-4) // -1

応用として絶対値/abs。 M = n >> 31 として (n + M) ^ M 及び (n ^ M) - Mが絶対値を返す。非負の場合は M=0 なのでどちらもnに評価されるし、負の場合はM=-1なので(n-1)^(-1),n^(-1)+1となるが、-1 との XOR が NOT であることを考慮すると、これは共に NEG であるとわかる。

abs.js

// equivalent to Math.abs
const abs = n => (n + (n >> 31)) ^ (n >> 31);
const abs2 = n => (n ^ (n >> 31)) - (n >> 31);

abs(4) === 4 && abs2(4) === 4 // true
abs(-4) === 4 && abs2(-4) === 4 // true
abs(0) === 0 && abs2(0) === 0 // true

フラグセット/クリアのどちらか実施

フラグ f が false の場合にはマスクMでセットして、そうでない場合はマスクでクリアするという操作は n ^ ((-f ^ n) & M)とかける。fの真偽で場合分けして考察:[f が false すなわちクリアしたい時]: -f^nは n になるので (-f^n)&Mは、「今セットされているが、クリアすべきビット一覧」を表す。よって これを n に XOR すると、該当箇所がクリアされる。これは意図どおり。[f が true すなわちセットしたい時]: -f^n は -1^n すなわち ~n になる。よって(-f^n)&Mは、「今クリアだが、セットすべきビット一覧」を表す。よってこれを n に XOR すると該当する箇所がセットされる。これは意図どおり。

conditionalFlagManupulation.js

const cMaskOp = (n, M, f) => n ^ ((-f ^ n) & M);

cMaskOp(0b1100, 0b0110, true) // 0b1110
cMaskOp(0b1100, 0b0110, false) // 0b1000

条件付きNEG

フラグ f がtrueのときのみ NEG するには (n ^ -f) + f。f がfalseの時は n になるのは すぐわかる。 f が true の時は NOTして 1 を足す操作になるがこれは NEG そのものであるので意図どおり。

conditionalNegation.js

const cNEG = (n, f = true) => (n ^ -f) + f;

cNEG(3, true) // -3
cNEG(3, false) // 3
cNEG(-1, true) // 1
cNEG(-1, false) // -1

重要用語（おまけ）

MSB/LSB: 一番左がMSBで一番右がLSB。負数のMSBは必ずセットされる(2の補数の場合)
FFS/CTZ: LSBから見て最初にセットされたビット位置を知りたいときの操作。
CLZ: MSBから見て最初にセットされたビット位置を知りたい時の操作。
isolation: 特定の(セットされた)ビットのみを抽出する操作。
popcount: セットされたフラグの個数を知りたい時の操作。