はじめに
元ネタはハッカーのたのしみ（原題：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 & -xとx &= 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)
２ビットで分けたときの上の桁、下の桁を同時に足し合わせる
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ビット、下の２ビットを同時に足し合わせる
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()