popcount で 1 のビット数を数える

コンピューターサイエンス理論 / 全 5 枚

コンピューターサイエンス理論 - popcount で 1 のビット数を数える

立っている桁を数える

整数の中で 1 になっている桁の個数を求める処理です。集合の要素数や、2つの値がどれだけ違うかを測るハミング距離が、この数え上げ1つで出せます。

この 4 という数は図の一番下にも出ます。次の枚で確かめてください。

n & 1 で右端を見て、n >>= 1 で1桁ずつ右へ寄せます。0 になったら終わりです。

let count = 0;
for (let n = 106; n > 0; n >>= 1) count += n & 1;
// count は 4

1 / 5

← → キーでも送れます