1 が立っているビット数を数えることを「ビットカウント」や "population count" 等と呼びます。
このときのビット数は 2 進数の「ハミング重み (hamming weight)」と一致します。
既に様々な高速なアルゴリズムが見つかっていますが、C 言語や Rust 等で高速だからと言って JavaScript でも高速とは限らないため、実際に実行時間を測ってみました。
JavaScript のビット演算では値を 32 ビットの整数として扱うため、ビットカウントも 32 ビットの整数について考えます。
参考「バイナリービット演算子 - 式と演算子 - JavaScript | MDN」
1. 様々なアルゴリズム
おおよそ速い順に紹介します。
1.1. 分割統治法
ビットカウントの有名なアルゴリズムです (固有の名前は付いていない？) 。
環境によりますが、かなり速いです (具体的な実行時間の比較は後述します) 。
const popCountA = x => {
const a = x - (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = b + (b >>> 4) & 0x0f0f0f0f;
const y = c * 0x01010101 >>> 24;
return y;
};
const popCountB = x => {
const a = x - (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = b + (b >>> 4) & 0x0f0f0f0f;
const y = c % 0xff;
return y;
};
const popCountC = x => {
const a = x - (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = b + (b >>> 4) & 0x0f0f0f0f;
const d = c + (c >>> 8);
const e = d + (d >>> 16);
const y = e & 0xff;
return y;
};
const popCountD = x => {
const a = (x & 0x55555555) + (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = (b & 0x0f0f0f0f) + (b >>> 4 & 0x0f0f0f0f);
const d = (c & 0x00ff00ff) + (c >>> 8 & 0x00ff00ff);
const y = (d & 0x0000ffff) + (d >>> 16 & 0x0000ffff);
return y;
};
const popCountE = x => {
const a = x >>> 1 & 0o3_3333333333;
const b = x - a - (a >>> 1 & 0o3_3333333333);
// メモ: JavaScript でのビット演算は基本的に符号ありで計算されるため、符号なしの数に変換する
const c = (b + (b >>> 3) & 0o3_0707070707) >>> 0;
const y = c % 0o77;
return y;
};
const popCountF = x => {
const a = x >>> 1 & 0o3_3333333333;
const b = x - a - (a >>> 1 & 0o3_3333333333);
// メモ: JavaScript でのビット演算は基本的に符号ありで計算されるため、符号なしの数に変換する
const c = (b + (b >>> 3) & 0o3_0707070707) >>> 0;
const y = Number(BigInt(c) * 0o1_0101010101n >> 30n & 0o77n);
return y;
};
1 ビットずつのカウント、2 ビットずつのカウント、4 ビットずつのカウント、8 ビットずつのカウント…というように分割統治法で計算します。
初めて見ると謎の定数が並んでいるように見えますが、定数を 2 進数にすると分かりやすいと思います。
0x55555555 === 0b01010101010101010101010101010101;
0x33333333 === 0b00110011001100110011001100110011;
0x0f0f0f0f === 0b00001111000011110000111100001111;
0x00ff00ff === 0b00000000111111110000000011111111;
0x0000ffff === 0b00000000000000001111111111111111;
popCountC 関数内の式を変形してできるのが popCountB および popCountA 関数になります。
※計算方法に関するより詳しい説明は後述します。
1.2. 計算済みのルックアップテーブルを作成する方法
あらかじめ値ごとにビットカウントして保存しておき、実際にビットカウントしたいときにルックアップテーブルを参照するだけにする方法です。
実際には 32 ビットの値全てに関してルックアップテーブルを作成するとメモリを消費しすぎるため、16 ビットや 8 ビットの値に関してルックアップテーブルを作成し、32 ビットの値を分割して計算します。
JavaScript では 32 ビットの値を配列のように単純に分割することができないため、ビット演算や DataView を用いて値を分割します。
1.2.1. 16 ビットに分割する場合
ほぼルックアップテーブルを参照するだけなので高速に動作しそうですが、TypedArray へのアクセスが遅い環境では前述の方法程は速くなりませんでした。
const POP_COUNTS_16 = new Uint8Array(0x10000);
for (let x = 0; x < POP_COUNTS_16.length; x++) {
POP_COUNTS_16[x] = popCountA(x); // ここの計算は他のアルゴリズムでも良い
}
// ビット演算で値を分割する場合
const popCountG = x => POP_COUNTS_16[x & 0xffff] + POP_COUNTS_16[x >>> 16 & 0xffff];
// DataView で値を分割する場合
const aH = new Uint16Array(2);
const dataViewH = new DataView(aH.buffer);
const popCountH = x => {
dataViewH.setUint32(0, x);
return POP_COUNTS_16[aH[0]] + POP_COUNTS_16[aH[1]];
};
1.2.2. 8 ビットに分割する場合
速度的には 16 ビットに分割する方が 8 ビットに分割するより速いのは当たり前ですが、メモリ使用量は 8 ビットに分割する方が少なくできます。
const POP_COUNTS_8 = new Uint8Array(0x100);
for (let x = 0; x < POP_COUNTS_8.length; x++) {
POP_COUNTS_8[x] = popCountA(x); // ここの計算は他のアルゴリズムでも良い
}
// ビット演算で値を分割する場合
const popCountI = x => (
POP_COUNTS_8[x & 0xff] +
POP_COUNTS_8[x >>> 8 & 0xff] +
POP_COUNTS_8[x >>> 16 & 0xff] +
POP_COUNTS_8[x >>> 24 & 0xff]
);
// DataView で値を分割する場合
const aJ = new Uint8Array(4);
const dataViewJ = new DataView(aJ.buffer);
const popCountJ = x => {
dataViewJ.setUint32(0, x);
return POP_COUNTS_8[aJ[0]] + POP_COUNTS_8[aJ[1]] + POP_COUNTS_8[aJ[2]] + POP_COUNTS_8[aJ[3]];
};
1.3. WebAssembly の i32.popcnt 命令を使用する方法
WebAssembly にビットカウントするための命令 i32.popcnt があるため高速に動作するかと思いましたが、値のやり取りに時間がかかるのか、前述の方法程は速くなりませんでした。
(module
(func (export "popcnt") (param i32) (result i32)
local.get 0
i32.popcnt
)
)
AGFzbQEAAAABBgFgAX8BfwMCAQAHCgEGcG9wY250AAAKBwEFACAAaQsACgRuYW1lAgMBAAA=
const code = Uint8Array.from(
atob('AGFzbQEAAAABBgFgAX8BfwMCAQAHCgEGcG9wY250AAAKBwEFACAAaQsACgRuYW1lAgMBAAA='),
binaryChar => binaryChar.charCodeAt(0),
);
const { instance } = await WebAssembly.instantiate(code.buffer);
const { popcnt: popCountK } = instance.exports;
参考「Population count - WebAssembly | MDN」
参考「wat2wasm demo」
参考「[JavaScript] Unicode 文字列やバイナリデータを Base64 エンコードおよびデコードする - Qiita」
1.4. 1 が立っているビットを 1 つずつ消していく方法
右 (下位) から 1 が立っているビットを 1 つずつ消していき、その回数を数えることでビットカウントする方法です。
1 が立っているビットが少ない場合は速いですが、32 ビットの値をまんべんなく受け取る可能性がある場合は期待値 (平均) 的にはかなり遅いです。
(ソースコードだけ見ると賢いやり方に見えますが、性能は良くないです。)
const popCountL = x => {
let y = 0;
for (let a = x; a !== 0; a &= a - 1) {
y++;
}
return y;
};
a & a - 1 とすると 1 が立っている一番右のビットを 0 にできます。
0b10000001 & 0b10000001 - 1 === 0b10000001 & 0b10000000 === 0b10000000;
0b10001000 & 0b10001000 - 1 === 0b10001000 & 0b10000111 === 0b10000000;
2. 実行時間を比較
値によって実行時間が大きく異なるアルゴリズムがあるため、単純に考えると 0x00000000 から 0xffffffff まで計算したいですが、実行時間があまりにも長くなり過ぎる可能性があるため、等しい個数の乱数で測ります。
2.1. 実行時間
具体的なコードは後述します。
Google Chrome で確認した結果の平均は以下の表の通りです。
| 関数名 | 実行時間 | 備考 |
|---|---|---|
| popCountX | 48.133 | ビットカウント以外の処理 |
| popCountA | 75.633 | 分割統治、乗算 |
| popCountB | 89.400 | 分割統治、剰余 |
| popCountC | 80.167 | 分割統治、減算、論理積 |
| popCountD | 92.667 | 分割統治 |
| popCountE | 90.700 | 分割統治、3 ビットずつ、剰余 |
| popCountF | 780.767 | 分割統治、3 ビットずつ、乗算、BigInt 変換 |
| popCountG | 97.333 | ルックアップテーブル、16 ビット、ビット演算 |
| popCountH | 148.700 | ルックアップテーブル、16 ビット、DataView
|
| popCountI | 108.800 | ルックアップテーブル、8 ビット、ビット演算 |
| popCountJ | 160.667 | ルックアップテーブル、8 ビット、DataView
|
| popCountK | 115.233 | WebAssembly の i32.popcnt 命令 |
| popCountL | 554.633 | 1 が立っているビットを 1 つずつ数える |
Deno (--allow-hrtime オプション使用) で確認した結果の平均は以下の表の通りです。
| 関数名 | 実行時間 | 備考 |
|---|---|---|
| popCountX | 60.295 | ビットカウント以外の処理 |
| popCountA | 81.789 | 分割統治、乗算 |
| popCountB | 94.585 | 分割統治、剰余 |
| popCountC | 89.185 | 分割統治、減算、論理積 |
| popCountD | 99.545 | 分割統治 |
| popCountE | 98.218 | 分割統治、3 ビットずつ、剰余 |
| popCountF | 791.697 | 分割統治、3 ビットずつ、乗算、BigInt 変換 |
| popCountG | 74.178 | ルックアップテーブル、16 ビット、ビット演算 |
| popCountH | 106.869 | ルックアップテーブル、16 ビット、DataView
|
| popCountI | 88.058 | ルックアップテーブル、8 ビット、ビット演算 |
| popCountJ | 122.055 | ルックアップテーブル、8 ビット、DataView
|
| popCountK | 100.639 | WebAssembly の i32.popcnt 命令 |
| popCountL | 563.477 | 1 が立っているビットを 1 つずつ数える |
(Deno に別途ベンチマークの機能がありますが、ここでは Web ブラウザと同じ方法で比較しています。)
参考「now(): number - Performance | Runtime APIs | Deno」
Deno の方が Google Chrome より TypedArray のアクセスが速いらしく、分割統治法とルックアップテーブルを作成する方法の実行時間の大小が逆転しました。
2.2. コード
ここでは以下のコードで実行時間を測ることにします。
JavaScript エンジンの最適化の影響を小さくするため、入力を乱数にし、ビットカウントの値全てを出力に影響させるようにしました。
// 実行時間を確認
const sleep = milliseconds => new Promise(resolve => { setTimeout(resolve, milliseconds); });
const bench = (name, fn) => {
const beginTime = performance.now();
fn();
const endTime = performance.now();
console.log(`${name}: ${endTime - beginTime}`);
};
for (let i = 0; i < 3; i++) {
await sleep(1000);
bench('popCountX', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= values[k];
}
}
console.log(z);
});
await sleep(1000);
bench('popCountA', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountA(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountB', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountB(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountC', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountC(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountD', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountD(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountE', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountE(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountF', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountF(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountG', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountG(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountH', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountH(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountI', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountI(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountJ', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountJ(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountK', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountK(values[k]);
}
}
console.log(z);
});
await sleep(1000);
bench('popCountL', () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCountL(values[k]);
}
}
console.log(z);
});
}
ちなみに以下のようにコードをまとめてしまうと最適化の影響か安定した結果が得られなくなるため、しない方が良さそうです。
const popCounts = popCount => () => {
const values = new Uint32Array(0x4000);
let z = 0;
for (let j = 0; j < 0x800; j++) {
crypto.getRandomValues(values);
for (let k = 0; k < 0x4000; k++) {
z ^= popCount(values[k]);
}
}
console.log(z);
};
bench('popCountA', popCounts(popCountA));
bench('popCountB', popCounts(popCountB));
bench('popCountC', popCounts(popCountC));
bench('popCountD', popCounts(popCountD));
bench('popCountE', popCounts(popCountE));
bench('popCountF', popCounts(popCountF));
bench('popCountG', popCounts(popCountG));
bench('popCountH', popCounts(popCountH));
bench('popCountI', popCounts(popCountI));
bench('popCountJ', popCounts(popCountJ));
bench('popCountK', popCounts(popCountK));
bench('popCountL', popCounts(popCountL));
3. 分割統治法によるビットカウントの説明
3.1. 基本の計算方法
3.1.1. 2 ビットずつから計算を始める場合
1 ビットずつのカウント、2 ビットずつのカウント、4 ビットずつのカウント、8 ビットずつのカウント…というように分割統治法で計算します。
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11111111
2 2 2 2 10 10 10 10 10101010
4 4 0100 0100 01000100
8 00001000 00001000
1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 11011011
2 1 1 2 10 01 01 10 10010110
3 3 0011 0011 00110011
6 00000110 00000110
0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 01001001
1 0 1 1 01 00 01 01 01000101
1 2 0001 0010 00010010
3 00000011 00000011
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000000
0 0 0 0 00 00 00 00 00000000
0 0 0000 0000 00000000
0 00000000 00000000
例えば、8 ビットまでのビットカウントは以下のコードによって計算できます。
const a = (x & 0b01010101) + (x >>> 1 & 0b01010101);
const b = (a & 0b00110011) + (a >>> 2 & 0b00110011);
const y = (b & 0b00001111) + (b >>> 4 & 0b00001111);
const a = (x & 0x55) + (x >>> 1 & 0x55);
const b = (a & 0x33) + (a >>> 2 & 0x33);
const y = (b & 0x0f) + (b >>> 4 & 0x0f);
同様に 32 ビットまでビットカウントすると、以下のコードになります。
const popCountD = x => {
const a = (x & 0x55555555) + (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = (b & 0x0f0f0f0f) + (b >>> 4 & 0x0f0f0f0f);
const d = (c & 0x00ff00ff) + (c >>> 8 & 0x00ff00ff);
const y = (d & 0x0000ffff) + (d >>> 16 & 0x0000ffff);
return y;
};
各定数を 2 進数にすると以下のようになります。
0x55555555 === 0b01010101010101010101010101010101;
0x33333333 === 0b00110011001100110011001100110011;
0x0f0f0f0f === 0b00001111000011110000111100001111;
0x00ff00ff === 0b00000000111111110000000011111111;
0x0000ffff === 0b00000000000000001111111111111111;
3.1.2. 3 ビットずつから計算を始める場合
1 ビットずつのカウント、3 ビットずつのカウント、6 ビットずつのカウント…というように分割統治法で計算します。
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 11111111
2 3 3 10 011 011 10011011
2 6 10 000110 10000110
8 00001000 00001000
1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 11011011
2 2 2 10 010 010 10010010
2 4 10 000100 10000100
6 00000110 00000110
0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 01001001
1 1 1 01 001 001 01001001
1 2 01 000010 01000010
3 00000011 00000011
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00000000
0 0 0 00 000 000 00000000
0 0 00 000000 00000000
0 00000000 00000000
例えば、8 ビットまでのビットカウントは以下のコードによって計算できます。
const a = (x & 0b01001001) + (x >>> 1 & 0b01001001) + (x >>> 2 & 0b01001001);
const b = (a & 0b11000111) + (a >>> 3 & 0b11000111);
const y = (b & 0b00111111) + (b >>> 6 & 0b00111111);
const a = (x & 0o1_11) + (x >>> 1 & 0o1_11) + (x >>> 2 & 0o1_11);
const b = (a & 0o3_07) + (a >>> 3 & 0o3_07);
const y = (b & 0o0_77) + (b >>> 6 & 0o0_77);
※上記のコード中で下線 _ は見やすさのための数値の区切りとして書いているだけで、文法上必須なものではありません。
※ 9 ビットずつのビットカウントを計算することもできますが、後に式変形して演算の回数を減らせるようにするため 6 ビットずつのビットカウントを計算しています。
同様に 32 ビットまでビットカウントすると、以下のコードになります。
const a = (x & 0o1_1111111111) + (x >>> 1 & 0o1_1111111111) + (x >>> 2 & 0o1_1111111111);
// メモ: JavaScript でのビット演算は基本的に符号ありで計算されるため、符号なしの数に変換する
const b = (a & 0o3_0707070707) + (a >>> 3 & 0o3_0707070707) >>> 0;
const y = (
(b & 0o77) +
(b >>> 6 & 0o77) +
(b >>> 12 & 0o77) +
(b >>> 18 & 0o77) +
(b >>> 24 & 0o77) +
(b >>> 30 & 0o77)
);
※ 12 ビットずつのビットカウントを計算することもできますが、後に式変形して演算の回数を減らせるようにするため 6 ビットずつのままビットカウントを計算しています。
各定数を 2 進数にすると以下のようになります。
0o1_1111111111 === 0b01_001001001001001001001001001001;
0o3_0707070707 === 0b11_000111000111000111000111000111;
0o77 === 0b111111;
3.2. 演算の回数を減らす
3.2.1. 2 ビットずつのビットカウントで減算を用いる
基本の計算方法では、2 ビットまでのビットカウントは以下のコードによって計算します。
const y = (x & 0b01) + (x >>> 1 & 0b01);
ここで、以下のような式変形をすることができます。
(x >>> 1 & 0b01) + (x >>> 1 & 0b01) === ((x >>> 1 & 0b01) << 1);
(x >>> 1 & 0b01) === ((x >>> 1 & 0b01) << 1) - (x >>> 1 & 0b01);
(
(x & 0b01) + ((x >>> 1 & 0b01) << 1)
) === (
(x & 0b01) + (x & 0b10)
) === (
x
);
(
(x & 0b01) + (x >>> 1 & 0b01)
) === (
(x & 0b01) + ((x >>> 1 & 0b01) << 1) - (x >>> 1 & 0b01)
) === (
x - (x >>> 1 & 0b01)
);
よって、2 ビットまでのビットカウントは以下のコードでも計算できます。
const y = x - (x >>> 1 & 0b01);
同様に考えると、32 ビットまでのビットカウント時の 2 ビットずつのビットカウントは以下のコードによって計算できます。
const a = x - (x >>> 1 & 0x55555555);
3.2.2. 8 ビットずつのビットカウントの論理積の計算をまとめる
基本の計算方法では、8 ビットまでのビットカウントは以下のコードによって計算します。
const y = (b & 0b00001111) + (b >>> 4 & 0b00001111);
ここで、y の最大値が 8 === 0b00001000 となり 4 ビットで表現できるため、論理積 & 0b00001111 によって 4 ビット切り出す計算をまとめることができます。
const y = b + (b >>> 4) & 0b00001111;
同様に考えると、32 ビットまでのビットカウント時の 8 ビットずつのビットカウントは以下のコードによって計算できます。
const c = b + (b >>> 4) & 0x0f0f0f0f;
ちなみに上記の式変形は「8 ビットまでのビットカウントを 4 ビットで表現できる」ために成り立ちます。
「2 ビットまでのビットカウントは 2 ビット」、「4 ビットまでのビットカウントは 3 ビット」が表現するために必要なため、同様の式変形はできません。
3.2.3. 16 ビットずつから 32 ビットまでのビットカウントの論理積の計算をまとめる
基本の計算方法では、16 ビットずつから 32 ビットまでのビットカウントは以下のコードによって計算します。
const d = (c & 0x00ff00ff) + (c >>> 8 & 0x00ff00ff);
const y = (d & 0x0000ffff) + (d >>> 16 & 0x0000ffff);
ここで、y の最大値が 32 === 0b00100000 より「16 ビットまでのビットカウント」も「32 ビットまでのビットカウント」も 8 ビット以下で表現できるため、論理積によって 8 ビット切り出す計算をまとめることができます。
const d = c + (c >>> 8);
const e = d + (d >>> 16);
const y = e & 0xff;
また、以下のコードでも同様に計算できます。
const y = c + (c >>> 8) + (c >>> 16) + (c >>> 24) & 0xff;
3.2.4. 16 ビットずつから 32 ビットまでのビットカウントで剰余を用いる
以下のように式変形すると、16 ビットずつから 32 ビットまでのビットカウントを剰余によって計算できることが分かります。
c0 = c & 0xff;
c1 = c >>> 8 & 0xff;
c2 = c >>> 16 & 0xff;
c3 = c >>> 24 & 0xff;
c === c0 + (c1 << 8) + (c2 << 16) + (c3 << 24);
0x00000001 % 0xff === 1;
0x00000100 % 0xff === 1;
0x00010000 % 0xff === 1;
0x01000000 % 0xff === 1;
(
c % 0xff
) === (
(c0 + (c1 << 8) + (c2 << 16) + (c3 << 24)) % 0xff
) === (
(c0 * 0x00000001 + c1 * 0x00000100 + c2 * 0x00010000 + c3 * 0x01000000) % 0xff
) === (
(c0 + c1 + c2 + c3) % 0xff
) === (
c0 + c1 + c2 + c3
) === (
(c & 0xff) + (c >>> 8 & 0xff) + (c >>> 16 & 0xff) + (c >>> 24 & 0xff)
) === (
c + (c >>> 8) + (c >>> 16) + (c >>> 24) & 0xff
);
よって、以下のように計算をまとめることもできます。
const y = c % 0xff;
3.2.5. 16 ビットずつから 32 ビットまでのビットカウントで乗算を用いる
論理積をまとめた式から、以下のような式変形をすることができます。
(
c + (c >>> 8) + (c >>> 16) + (c >>> 24) & 0xff
) === (
(c << 24) + (c << 16) + (c << 8) + c >>> 24 & 0xff
) === (
c * 0x01010101 >>> 24 & 0xff
);
ここでは c の最大値が 0x08080808 のため、c * 0x01010101 の最大値は 0x08080808 * 0x01010101 === 0x00081018_20181008 となり 52 ビットの数になります。
JavaScript での通常の (Number 型の) 数は 53 ビットまでの正の整数を正しく扱えるため、問題なく計算できます。
参考「Number.MAX_SAFE_INTEGER - JavaScript | MDN」
符号なし右シフト >>> は値を 32 ビットとして扱うため、32 ビットの値を右に 24 ビットシフトすることで 8 ビットの値しか残らないため、論理積 & 0xff を取り除くことができます。
(
c * 0x01010101 >>> 24 & 0xff
) === (
c * 0x01010101 >>> 24
);
よって、以下のように計算をまとめることもできます。
const y = c * 0x01010101 >>> 24;
3.2.6. 3 ビットずつのビットカウントで減算を用いる
基本の計算方法では、3 ビットまでのビットカウントは以下のコードによって計算します。
const y = (x & 0b001) + (x >>> 1 & 0b001) + (x >>> 2 & 0b001);
ここで、以下のような式変形をすることができます。
(x >>> 1 & 0b001) + (x >>> 1 & 0b001) === ((x >>> 1 & 0b001) << 1);
(x >>> 1 & 0b001) === ((x >>> 1 & 0b001) << 1) - (x >>> 1 & 0b001);
(x >>> 2 & 0b001) + (x >>> 2 & 0b001) + ((x >>> 2 & 0b001) << 1) === ((x >>> 2 & 0b001) << 2);
(x >>> 2 & 0b001) === ((x >>> 2 & 0b001) << 2) - ((x >>> 2 & 0b001) << 1) - (x >>> 2 & 0b001);
(
(x & 0b001) + ((x >>> 1 & 0b001) << 1) + ((x >>> 2 & 0b001) << 2)
) === (
(x & 0b001) + (x & 0b010) + (x & 0b100)
) === (
x
);
(
(x & 0b001) +
(x >>> 1 & 0b001) +
(x >>> 2 & 0b001)
) === (
(x & 0b001) +
((x >>> 1 & 0b001) << 1) - (x >>> 1 & 0b001) +
((x >>> 2 & 0b001) << 2) - ((x >>> 2 & 0b001) << 1) - (x >>> 2 & 0b001)
) === (
x - (x >>> 1 & 0b001) - ((x >>> 2 & 0b001) << 1) - (x >>> 2 & 0b001)
) === (
x - (x >>> 1 & 0b001) - (x >>> 1 & 0b010) - (x >>> 2 & 0b001)
) === (
x - (x >>> 1 & 0b011) - (x >>> 2 & 0b001)
) === (
x - (x >>> 1 & 0b011) - ((x >>> 1 & 0b011) >>> 1 & 0b011)
);
よって、3 ビットまでのビットカウントは以下のコードでも計算できます。
const y = x - (x >>> 1 & 0b011) - ((x >>> 1 & 0b011) >>> 1 & 0b011);
ここで、一部の計算結果を変数に代入することで計算量をさらに減らせます。
const a = x >>> 1 & 0b011;
const y = x - a - (a >>> 1 & 0b011);
同様に考えると、32 ビットまでのビットカウント時の 3 ビットずつのビットカウントは以下のコードによって計算できます。
const a = x >>> 1 & 0o3_3333333333;
const b = x - a - (a >>> 1 & 0o3_3333333333);
3.2.7. 6 ビットずつのビットカウントの論理積の計算をまとめる
基本の計算方法では、6 ビットまでのビットカウントは以下のコードによって計算します。
const y = (b & 0b000111) + (b >>> 3 & 0b000111);
ここで、y の最大値が 6 === 0b000110 となり 3 ビットで表現できるため、論理積 & 0b000111 によって 3 ビット切り出す計算をまとめることができます。
const y = b + (b >>> 3) & 0b000111;
同様に考えると、32 ビットまでのビットカウント時の 6 ビットずつのビットカウントは以下のコードによって計算できます。
// メモ: JavaScript でのビット演算は基本的に符号ありで計算されるため、符号なしの数に変換する
const c = (b + (b >>> 3) & 0o3_0707070707) >>> 0;
ちなみに上記の式変形は「6 ビットまでのビットカウントを 3 ビットで表現できる」ために成り立ちます。
「3 ビットまでのビットカウントは 2 ビット」が表現するために必要なため、同様の式変形はできません。
3.2.8. 6 ビットずつから 32 ビットまでのビットカウントの論理積の計算をまとめる
基本の計算方法では、6 ビットずつから 32 ビットまでのビットカウントは以下のコードによって計算します。
const y = (
(c & 0o77) +
(c >>> 6 & 0o77) +
(c >>> 12 & 0o77) +
(c >>> 18 & 0o77) +
(c >>> 24 & 0o77) +
(c >>> 30 & 0o77)
);
ここで、y の最大値が 32 === 0b100000 より「32 ビットまでのビットカウント」を 6 ビット以下で表現できるため、論理積によって 6 ビット切り出す計算をまとめることができます。
const y = c + (c >>> 6) + (c >>> 12) + (c >>> 18) + (c >>> 24) + (c >>> 30) & 0o77;
3.2.9. 6 ビットずつから 32 ビットまでのビットカウントで剰余を用いる
以下のように式変形すると、6 ビットずつから 32 ビットまでのビットカウントを剰余によって計算できることが分かります。
c0 = c & 0o77;
c1 = c >>> 6 & 0o77;
c2 = c >>> 12 & 0o77;
c3 = c >>> 18 & 0o77;
c4 = c >>> 24 & 0o77;
c5 = c >>> 30 & 0o77;
c === c0 + (c1 << 6) + (c2 << 12) + (c3 << 18) + (c4 << 24) + (c5 << 30);
0o0_0000000001 % 0o77 === 1;
0o0_0000000100 % 0o77 === 1;
0o0_0000010000 % 0o77 === 1;
0o0_0001000000 % 0o77 === 1;
0o0_0100000000 % 0o77 === 1;
0o1_0000000000 % 0o77 === 1;
(
c % 0o77
) === (
(
c0 +
(c1 << 6) +
(c2 << 12) +
(c3 << 18) +
(c4 << 24) +
(c5 << 30)
) % 0o77
) === (
(
c0 * 0o0_0000000001 +
c1 * 0o0_0000000100 +
c2 * 0o0_0000010000 +
c3 * 0o0_0001000000 +
c4 * 0o0_0100000000 +
c5 * 0o1_0000000000
) % 0o77
) === (
(c0 + c1 + c2 + c3 + c4 + c5) % 0o77
) === (
c0 + c1 + c2 + c3 + c4 + c5
) === (
(c & 0o77) +
(c >>> 6 & 0o77) +
(c >>> 12 & 0o77) +
(c >>> 18 & 0o77) +
(c >>> 24 & 0o77) +
(c >>> 30 & 0o77)
) === (
c + (c >>> 6) + (c >>> 12) + (c >>> 18) + (c >>> 24) + (c >>> 30) & 0o77
);
よって、以下のように計算をまとめることもできます。
const y = c % 0o77;
3.2.10. 6 ビットずつから 32 ビットまでのビットカウントで乗算を用いる
論理積をまとめた式から、理論上は以下のような式変形をすることができます。
(
c + (c >>> 6) + (c >>> 12) + (c >>> 18) + (c >>> 24) + (c >>> 30) & 0o77
) === (
(c << 30) + (c << 24) + (c << 18) + (c << 12) + (c << 6) + c >>> 30 & 0o77
) === (
c * 0o1_0101010101 >>> 30 & 0o77
);
ここでは c の最大値が 0o2_0606060606 のため、c * 0o1_0101010101 の最大値は理論上は 0o2_0606060606 * 0o1_0101010101 === 0o2_1016243240_3630221406 となり 62 ビットの数になります。
JavaScript での通常の (Number 型の) 数で正しく扱える正の整数は 53 ビットまでのため、計算で問題が発生します。
実際に JavaScript で計算すると 0o2_0606060606 * 0o1_0101010101 === 0o2_1016243240_3630222000 になります。
参考「Number.MAX_SAFE_INTEGER - JavaScript | MDN」
Math.imul() 関数を使用することで 32 ビットまでの乗算を行うことができますが、ここでは 36 ビットまでの値を計算に用いるため、使えません。
参考「Math.imul() - JavaScript | MDN」
よって、正しく計算するためには BigInt を使う必要があります。
ただし BigInt は常に符号ありとして扱われるため、符号なし右シフト >>> を使用することはできません。
参考「演算子 - BigInt - JavaScript | MDN」
よって、以下のように計算をまとめることもできます。
const y = Number(BigInt(c) * 0o1_0101010101n >> 30n & 0o77n);
ちなみに最長 62 ビットの値を右に 30 ビットシフトすることで 32 ビットの値が残る可能性があるため、論理積 & 0o77n を取り除くことはできません。
3.3. 演算の回数を減らした計算方法
実際に演算の回数を減らす式変形をすると、以下のようなコードで 32 ビットまでのビットカウントを行えます。
const popCountA = x => {
const a = x - (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = b + (b >>> 4) & 0x0f0f0f0f;
const y = c * 0x01010101 >>> 24;
return y;
};
const popCountB = x => {
const a = x - (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = b + (b >>> 4) & 0x0f0f0f0f;
const y = c % 0xff;
return y;
};
const popCountC = x => {
const a = x - (x >>> 1 & 0x55555555);
const b = (a & 0x33333333) + (a >>> 2 & 0x33333333);
const c = b + (b >>> 4) & 0x0f0f0f0f;
const d = c + (c >>> 8);
const e = d + (d >>> 16);
const y = e & 0xff;
return y;
};
const popCountE = x => {
const a = x >>> 1 & 0o3_3333333333;
const b = x - a - (a >>> 1 & 0o3_3333333333);
// メモ: JavaScript でのビット演算は基本的に符号ありで計算されるため、符号なしの数に変換する
const c = (b + (b >>> 3) & 0o3_0707070707) >>> 0;
const y = c % 0o77;
return y;
};
const popCountF = x => {
const a = x >>> 1 & 0o3_3333333333;
const b = x - a - (a >>> 1 & 0o3_3333333333);
// メモ: JavaScript でのビット演算は基本的に符号ありで計算されるため、符号なしの数に変換する
const c = (b + (b >>> 3) & 0o3_0707070707) >>> 0;
const y = Number(BigInt(c) * 0o1_0101010101n >> 30n & 0o77n);
return y;
};