8ビットの数値が偶数パリティかを計算する

問題

8ビット符号なし整数 (0～255) が与えられる。
この整数を2進数で表したときの「1」の数は偶数 (=偶数パリティ) か否か？

計算方法

愚直

1ビットずつ「1」かどうかを判定し、「1」のビットの数を数える。
そして、最後にその数が偶数かどうかを判定する。

function isEvenParity8bit(value) {
	let cnt = 0;
	for (let i = 0; i < 8; i++) {
		if ((value >> i) & 1) cnt++;
	}
	return cnt % 2 == 0;
}

有名手法の応用 (シフト加算)

数の中で「1」のビットがいくつあるかを求める有名な方法がある。
数を細かい数が並んだものと考え、それらの細かい数を足していくことで求める方法である。
この方法で「1」のビットがいくつあるかを求め、それが偶数かどうかを判定する。

function isEvenParity8bit(value) {
	value = (value & 0x55) + ((value & 0xaa) >> 1);
	value = (value & 0x33) + ((value & 0xcc) >> 2);
	value = (value & 0x0f) + ((value & 0xf0) >> 4);
	return value % 2 == 0;
}

有名手法の応用の応用 (XOR)

上の手法では、加算を行うために、ビットANDによるマスクが必要だった。
しかし、「1」のビットの数の偶奇のみを求める場合、加算のかわりにXORをすればよい。
XORならば各ビットごとに独立に計算でき、ほかのビットに影響を与えないため、使わないビットをマスクせず、単純に無視すればよい。

function isEvenParity8bit(value) {
	value ^= value >> 1;
	value ^= value >> 2;
	value ^= value >> 4;
	return !(value & 1);
}

検証

今回用意した3種類の手法の計算結果を比較し、違いがないことを確かめた。

function isEvenParity8bit1(value) {
	let cnt = 0;
	for (let i = 0; i < 8; i++) {
		if ((value >> i) & 1) cnt++;
	}
	return cnt % 2 == 0;
}

function isEvenParity8bit2(value) {
	value = (value & 0x55) + ((value & 0xaa) >> 1);
	value = (value & 0x33) + ((value & 0xcc) >> 2);
	value = (value & 0x0f) + ((value & 0xf0) >> 4);
	return value % 2 == 0;
}

function isEvenParity8bit3(value) {
	value ^= value >> 1;
	value ^= value >> 2;
	value ^= value >> 4;
	return !(value & 1);
}

for (let i = 0; i < 256; i++) {
	const a = isEvenParity8bit1(i);
	const b = isEvenParity8bit2(i);
	const c = isEvenParity8bit3(i);
	if (a !== b || b !== c) console.log(i, a, b, c);
}

性能比較

今回用意した3種類の手法の実行効率を、JSBench.me で1回測定した。
それぞれの関数の後に以下のコードを追加し、それぞれの入力について1回ずつ計算を行った。

let cnt = 0;
for (let i = 0; i < 256; i++) {
	if (isEvenParity8bit(i)) cnt++;
}
if (cnt !== 128) throw new Error();

isEvenParity8bit (version 1) - JavaScript benchmark at JSBench.me

その結果は以下のようになった。

手法	Firefox 135.0.1	Google Chrome 133.0.6943.142
愚直	43万 ops/s ± 0.76%	25万 ops/s ± 1.04%
シフト加算	337万 ops/s ± 0.67%	80万 ops/s ± 1.87%
XOR	483万 ops/s ± 1.2%	116万 ops/s ± 1.41%

有名手法を用いて「1」のビットを数えることで、愚直にビットを数えるよりもかなり効率が上がっているが、XORを用いてAND演算を削減することでそれよりもさらに効率が上がっていることがわかる。

よりビットが多い場合への応用

16ビット・32ビットなどより多くのビットを扱う場合にも、有名手法と同様に、シフトの幅を増やした計算を追加することで対応できるはずである。

まとめ

「1」のビットの数を求める有名な手法を応用し、XOR演算を用いて余計なAND演算を省くことで、より効率よく与えられた数値が偶数パリティかどうかを求めることができた。