Posted at

ビット演算の高速化メモ


はじめに

元ネタはハッカーのたのしみ(原題:Hacker's Delight)です。


ビットマップのループ

01011000


f(00001000)
f(00010000)
f(01000000)

右から走査して1のときだけ処理を行いたいとき、

ビットの長さ分ループしなくても1の数のループで済ませられる。

for (int x = 0b01011000; x > 0; x &= x - 1) {

f(x & -x);
}

このようにx & -xx &= x - 1を繰り返せば、1の部分だけ渡り歩くことができる。


x & -x

01011000 = x

10100111 = not(x)

10101000 = not(x)+1 = -x

つまり

00001000 = x & -x

となって、右端の1だけが残る。


x & x-1

01011000 = x

01010111 = x-1

つまり

01010000 = x & x-1

となって、右端の1が消える。


ビットカウント

00101110 10100000 11100101 11001011


16

1の数を数えたいとき、

ビットの数だけループしなくてもlog(ビット数)回のビット演算で求められる。

x = 0b00101110101000001110010111001011;

x = (x & 0x55555555) + ((x >>> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >>> 2) & 0x33333333)
x = (x & 0x0F0F0F0F) + ((x >>> 4) & 0x0F0F0F0F)
x = (x & 0x00FF00FF) + ((x >>> 8) & 0x00FF00FF)
x = (x & 0x0000FFFF) + ((x >>> 16) & 0x0000FFFF)

やっていることは、部分和をx自身に書き込んでいく分割統治。


手順


代入1回目

データを2ビットずつに区切り、2ビットごとの1の数を求めてxを上書きする。

00 10 11 10 10 10 00 00 11 10 01 01 11 00 10 11 = x



_0 _1 _2 _1 _1 _1 _0 _0 _2 _1 _1 _1 _2 _0 _1 _2(10進表現)



00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10 = 新しいx


00 10 11 10 10 10 00 00 11 10 01 01 11 00 10 11 = x

_0 _0 _1 _0 _0 _0 _0 _0 _1 _0 _1 _1 _1 _0 _0 _1 = x & 0x55555555

_0 _1 _1 _1 _1 _1 _0 _0 _1 _1 _0 _0 _1 _0 _1 _1 = ((x >>> 1) & 0x55555555)

2ビットで分けたときの上の桁、下の桁を同時に足し合わせる

00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10 = (x & 0x55555555) + ((x >>> 1) & 0x55555555)

やっていることは、2ビットのベクトル演算。


代入2回目

データを4ビットずつに区切り、4ビットごとの1の数を求めてxを上書きする。

0001 1001 0101 0000 1001 0101 1000 0110 = x



_0_1 _2_1 _1_1 _0_0 _2_1 _1_1 _2_0 _1_2(10進表現)



___1 ___3 ___2 ___0 ___3 ___2 ___2 ___3(10進表現)



0001 0011 0010 0000 0011 0010 0010 0011 = 新しいx


0001 1001 0101 0000 1001 0101 1000 0110 = x

__01 __01 __01 __00 __01 __01 __00 __10 = x & 0x33333333

__00 __10 __01 __00 __10 __01 __10 __01 = (x >>> 1) & 0x33333333

4ビットで分けたときの上の2ビット、下の2ビットを同時に足し合わせる

0001 0011 0010 0000 0011 0010 0010 0011 = (x & 0x33333333) + ((x >>> 2) & 0x33333333)

やっていることは、4ビットのベクトル演算。


代入3回目

データを8ビットずつに区切り、8ビットごとの1の数を求めてxを上書きする。

00010011 00100000 00110010 00100011 = x



___1___3 ___2___0 ___3___2 ___2___3(10進表現)



_______4 _______2 _______5 _______5(10進表現)



00000100 00000010 00000101 00000101 = 新しいx


代入4回目

データを16ビットずつに区切り、16ビットごとの1の数を求めてxを上書きする。

0000010000000010 0000010100000101 = x



_______4_______2 _______5_______5(10進表現)



_______________6 ______________10(10進表現)



0000000000000110 0000000000001010 = 新しいx


代入5回目

データ全体の1の数を求めて、xに上書きする。

0000000000000110 0000000000001010 = 新しいx



_______________6 ______________10(10進表現)



_______________________________16(10進表現)



0000000000000000 0000000000010000 = 新しいx



16


ちなみに

標準ライブラリで実装されていたりします。JavaとGoの例しか知りませんが、

Java : Integer.bitCount()、Long.bitCount()

Go : bitsパッケージのOnesCountXX()

(上記のコードよりも最適化されている)。

さらに言うと、10年前ぐらいからCPUの拡張命令(IntelであればSSE4.2のPOPCNT)としても実装されているので、

そもそも本気で高速化するなら直接POPCNTを呼べる言語を利用すべきです。

Javaに関してはJITがbitCount()をPOPCNTに置き換えてくれるらしいですが、

Goはどうなんでしょうか?


参考

wikipedia : SSE4、ハミング重み

https://en.wikipedia.org/wiki/SSE4

https://en.wikipedia.org/wiki/Hamming_weight

openjdk8のLongクラス(ソースコード)

https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/lang/Long.java

Goのbitsパッケージ(ソースコード)

https://golang.org/src/math/bits/bits.go?s=3946:3972#L103


ビットリバース

00101110 10100000 11100101 11001011


11010011 10100111 00000101 01110100

ビットを逆順にしたいときも分割統治が使える。

x = 0b00101110101000001110010111001011;

x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16;
x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >>> 8;
x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >>> 4;
x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >>> 2;
x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >>> 1;


手順


代入1回目

データを16ビットずつに区切り、入れ替える。

0010111010100000 1110010111001011 = x



1110010111001011 0010111010100000 = 新しいx


0010111010100000 1110010111001011 = x

1110010111001011 ________________ = (x & 0x0000FFFF) << 16

________________ 0010111010100000 = (x & 0xFFFF0000) >>> 16

1110010111001011 0010111010100000 = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16


代入2回目

データを8ビットずつに区切り、隣り合う同士で入れ替える。

11100101 11001011 00101110 10100000 = x



11001011 11100101 10100000 00101110 = 新しいx


11100101 11001011 00101110 10100000 = x

11001011 ________ 10100000 ________ = (x & 0x00FF00FF) << 8

________ 11100101 ________ 00101110 = (x & 0xFF00FF00) >>> 8

11001011 11100101 10100000 00101110 = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >>> 8


代入3回目

データを4ビットずつに区切り、隣り合う同士で入れ替える。

1100 1011 1110 0101 1010 0000 0010 1110 = x



1011 1100 0101 1110 0000 1010 1110 0010 = 新しいx


代入4回目

データを2ビットずつに区切り、隣り合う同士で入れ替える。

10 11 11 00 01 01 11 10 00 00 10 10 11 10 00 10 = x



11 10 00 11 01 01 10 11 00 00 10 10 10 11 10 00 = 新しいx


代入5回目

データを1ビットずつに区切り、隣り合う同士で入れ替える。

1 1 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 = x



1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0 = 新しいx

11010011101001110000010101110100 = もとのx

00101110101000001110010111001011 = 新しいx

となって、正しく逆順になっている。


ちなみに

こちらも標準ライブラリで実装されていることがあります。

Java -> Integer.reverseBytes()、Long.reverseBytes()

Go -> bitsパッケージのReverseXX()