二進数における 1 の個数 ——《C/C++ ビット演算のブラックテクノロジー 03》

原理#

二進数の中の 1 の出現回数を計算するのは実際には非常に簡単で、v & (v - 1) を使って最後の 1 を取り除くだけで済みます。この原理については、こちらの記事を参照してください：2 の累乗 ——《C/C++ ビット演算ハイテク 02》

上記の方法は一般的な考え方ですが、ここでは別のアプローチである「並列カウンター」を紹介し、二進数における 1 の出現回数を計算します。

実際には、この数をすべて単位カウンターで構成されていると考えることができます。1 と 0 はそれぞれ単一のカウンターの状態を表し、隣接するカウンターを統合するだけで済みます。これは実際にはマージの考え方でもあります。

コード#

inline unsigned count_bits(uint64_t v)
{
    v = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
    v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
    v = (v & 0x0f0f0f0f0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f0f0f0f0f);
    v = (v & 0x00ff00ff00ff00ff) + ((v >> 8) & 0x00ff00ff00ff00ff);
    v = (v & 0x0000ffff0000ffff) + ((v >> 16) & 0x0000ffff0000ffff);
    v = (v & 0x00000000ffffffff) + ((v >> 32) & 0x00000000ffffffff);
    return v;
}

inline unsigned count_bits(uint32_t v)
{
    v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
    v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
    v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
    v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
    return v;
}

inline unsigned count_bits(uint16_t v)
{
    v = (v & 0x5555) + ((v >> 1) & 0x5555);
    v = (v & 0x3333) + ((v >> 2) & 0x3333);
    v = (v & 0x0f0f) + ((v >> 4) & 0x0f0f);
    v = (v & 0x00ff) + ((v >> 8) & 0x00ff);
    return v;
}

inline unsigned count_bits(uint8_t v)
{
    v = (v & 0x55) + ((v >> 1) & 0x55);
    v = (v & 0x33) + ((v >> 2) & 0x33);
    v = (v & 0x0f) + ((v >> 4) & 0x0f);
    return v;
}

原理の解析#

ここでは 1110001010011110 を例に、並列カウンターの統合方法を説明します：

val	1	1	1	0	0	0	1	0	1	0	0	1	1	1	1	0
& 0x5555	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
=	0	1	0	0	0	0	0	0	0	0	0	1	0	1	0	0

val >> 1	0	1	1	1	0	0	0	1	0	1	0	0	1	1	1	1
& 0x5555	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
=	0	1	0	1	0	0	0	1	0	1	0	0	0	1	0	1

次に、両者を加算すると隣接する 2 つのカウンターの統合カウントが得られます：1001000101011001。その後、2 ビット単位でカウンターをさらに統合します。

Val	10	01	00	01	01	01	10	01
& 0x3333	00	11	00	11	00	11	00	11
=	00	01	00	01	00	01	00	01

Val >> 2	00	10	01	00	01	01	01	10
& 0x3333	00	11	00	11	00	11	00	11
=	00	10	00	00	00	01	00	10

次に、両者を加算すると隣接する 4 つのカウンターの統合カウントが得られます：0011000100100011。その後、4 ビット単位でカウンターをさらに統合します。

Val	0011	0001	0010	0011
& 0x0f0f	0000	1111	0000	1111
=	0000	0001	0000	0011

Val >> 4	0000	0011	0001	0010
& 0x0f0f	0000	1111	0000	1111
=	0000	0011	0000	0010

次に、両者を加算すると隣接する 8 つのカウンターの統合カウントが得られます：0000010000000101。その後、8 ビット単位でカウンターをさらに統合します。

Val	00000100	00000101
&00ff	00000000	11111111
=	00000000	00000101

Val >> 8	00000000	00000100
&00ff	00000000	11111111
=	00000000	00000100

次に、両者を加算すると隣接する 8 つのカウンターの統合カウントが得られます：0000000000001001。これを十進数に変換すると 9 となり、元の数字の中の 1 の個数と一致します。

ベンチマーク#

#include "benchmark/benchmark.h"

inline unsigned count_bits(uint64_t v)
{
  v = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
  v = (v & 0x3333333333333333) + ((v >> 2) & 0x3333333333333333);
  v = (v & 0x0f0f0f0f0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f0f0f0f0f);
  v = (v & 0x00ff00ff00ff00ff) + ((v >> 8) & 0x00ff00ff00ff00ff);
  v = (v & 0x0000ffff0000ffff) + ((v >> 16) & 0x0000ffff0000ffff);
  v = (v & 0x00000000ffffffff) + ((v >> 32) & 0x00000000ffffffff);
  return v;
}

inline unsigned count_bits(uint32_t v)
{
  v = (v & 0x55555555) + ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  v = (v & 0x0f0f0f0f) + ((v >> 4) & 0x0f0f0f0f);
  v = (v & 0x00ff00ff) + ((v >> 8) & 0x00ff00ff);
  v = (v & 0x0000ffff) + ((v >> 16) & 0x0000ffff);
  return v;
}

inline unsigned count_bits(uint16_t v)
{
  v = (v & 0x5555) + ((v >> 1) & 0x5555);
  v = (v & 0x3333) + ((v >> 2) & 0x3333);
  v = (v & 0x0f0f) + ((v >> 4) & 0x0f0f);
  v = (v & 0x00ff) + ((v >> 8) & 0x00ff);
  return v;
}

inline unsigned count_bits(uint8_t v)
{
  v = (v & 0x55) + ((v >> 1) & 0x55);
  v = (v & 0x33) + ((v >> 2) & 0x33);
  v = (v & 0x0f) + ((v >> 4) & 0x0f);
  return v;
}

static void BM_count_64(benchmark::State &state) {
  for (auto _: state) {
    uint64_t n = UINT64_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

static void BM_count_32(benchmark::State &state) {
  for (auto _: state) {
    uint32_t n = UINT32_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

static void BM_count_16(benchmark::State &state) {
  for (auto _: state) {
    uint16_t n = UINT16_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

static void BM_count_8(benchmark::State &state) {
  for (auto _: state) {
    uint8_t n = UINT8_MAX;
    benchmark::DoNotOptimize(count_bits(n));
  }
}

BENCHMARK(BM_count_8);
BENCHMARK(BM_count_16);
BENCHMARK(BM_count_32);
BENCHMARK(BM_count_64);

BENCHMARK_MAIN();

ここでは、MacBook Air (M1, 2020) と Apple clang 13.1.6 を使用して得られた結果を示します。

/Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/count_bits
Unable to determine clock rate from sysctl: hw.cpufrequency: No such file or directory
2022-03-27T14:09:30+08:00
Running /Users/hominsu/CLionProjects/bit-hacks-bench/cmake-build-release-appleclang/bench/count_bits
Run on (8 X 24.1205 MHz CPU s)
CPU Caches:
  L1 Data 64 KiB (x8)
  L1 Instruction 128 KiB (x8)
  L2 Unified 4096 KiB (x2)
Load Average: 2.64, 2.22, 1.79
------------------------------------------------------
Benchmark            Time             CPU   Iterations
------------------------------------------------------
BM_count_8       0.319 ns        0.319 ns   1000000000
BM_count_16      0.321 ns        0.321 ns   1000000000
BM_count_32      0.313 ns        0.313 ns   1000000000
BM_count_64      0.316 ns        0.316 ns   1000000000

次に、i5-9500 と gcc 8.5.0 (Red Hat 8.5.0-10) を使用して CentOS-8-Stream で得られた結果を示します。

/tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/count_bits
2022-03-27T14:10:07+08:00
Running /tmp/tmp.CtmwmpTLjC/cmake-build-release-1104/bench/count_bits
Run on (6 X 4100.35 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x6)
  L1 Instruction 32 KiB (x6)
  L2 Unified 256 KiB (x6)
  L3 Unified 9216 KiB (x1)
Load Average: 0.57, 0.54, 0.51
------------------------------------------------------
Benchmark            Time             CPU   Iterations
------------------------------------------------------
BM_count_8       0.244 ns        0.244 ns   1000000000
BM_count_16      0.246 ns        0.246 ns   1000000000
BM_count_32      0.245 ns        0.244 ns   1000000000
BM_count_64      0.249 ns        0.248 ns   1000000000