2進数で１が立っているビットを高速にカウントする方法

tadanori

この記事では、２進数表記で1が立っているビットの数を高速に数える（カウントする）アルゴリズムを紹介します。

Contents

はじめに
普通にカウントする方法（ループを利用）
高速にカウントする方法
まとめ

はじめに

整数値の２進数表記で1の数を数える（立っているビットをカウント）する関数は、色々なプログラミング言語に備わっています。例えばGo言語ならmath/bitsパッケージにbits.OnesCount()関数が用意されていますし、Pythonなら整数型にbit_count()メソッドが用意されています。

ここでは、ビットが立っている数を高速にカウントする方法について解説したいと思います。

なこ、ここでは簡単のために16bitの値の場合について解説します。

※プログラムコードはPythonです。

普通にカウントする方法（ループを利用）

まず、普通にカウントする方法です。bit_count()が１が立っているビット数を計算する関数になります。

関数の中身を見るとビットをシフトしながらn%2==1、つまり、最下位ビットに１が立っているかどうかカウントしています。

これにより16bitのそれぞれの位置に1が立っているかどうかチェックし、1が立っていたらカウントされます。

import random

def bit_count(n) :
    cnt = 0
    for i in range(16):
        if n%2 == 1 :
            cnt+=1
        n = n >> 1

    return cnt


for i in range(10) :
    n = random.randint(0, 1<<16)
    ret = bit_count(n)
    print(f"{n:5d} {format(n, '016b')} {ret:2d}")

## 結果
# 10990 0010101011101110  9
#  6376 0001100011101000  6
# 16317 0011111110111101 12
#   461 0000000111001101  6
# 32862 1000000001011110  6
# 33942 1000010010010110  6
# 20334 0100111101101110 10
# 12231 0010111111000111 10
#  5558 0001010110110110  8
# 45558 1011000111110110 10

結果を見ると、ビットが１の数を正しくカウントできていることがわかります。

高速にカウントする方法

アルゴリズム

アルゴリズムの概要は以下になります。まず0b10（0x5555）でマスクします。すると2ビットの上位1ビットがマスクされた値ができます。次に値を1ビットシフトして同じように0b10でマスクします。すると、上位ビットがをシフトした結果をマスクした結果ができます。

ここで両者を足すと、1bitの足し算が8個行われることになります（各演算は0+0=0, 1+0=1, 0+1=1, 1+1=2(0b10)なので、2ビットに収まります）。

次に、幅を4bitに変えて（0b0011, 0x3333のマスク)演算を行います。これで4つの足し算ができます。

さらに幅を8bitに変えて（0b00001111, 0x0f0fのマスク）演算を行います。これで２つの足し算が行われることになります。

最後に16bitで（0b0000000011111111, 0x00ffのマスク）演算を行います。これで全体で加算が行われます。

これで１が立っているビットの数を数えることができます。

わかりにくいの具体例で解説します。下図は、0001010111000000の1のビット数を数える例です。まず、2桁に区切って足し算を行います。このとき上位1bitはマスクします（０にします）。

図では、マスクされた部分をグレーにしています。

2bitずつ演算したら、今度は4bitごとで演算します。このとき上位2bitをマスクします。

次は8bitで演算します（4bitをマスク）。

これを繰り返すと1が立っている数が、足し込まれていき、最終的に全体の数が計算できます。

この演算では結果は5となり、正しいことがわかります。

具体的なプログラムコード

上記のアルゴリズムをプログラムしたのがbit_count2()です。

プログラムを見たらわかるように、ループは存在せず、4回のシフト、８回のand、４回の足し算だけで計算が終了します。

ループを使ったプログラムでは、(条件判定１回、加算１回、シフト１回）×16回行っているので、演算量が少なくなっていることがわかります。

def bit_count2(n) :
    n = (n & 0x5555) + (n >> 1 & 0x5555)
    n = (n & 0x3333) + (n >> 2 & 0x3333)
    n = (n & 0x0f0f) + (n >> 4 & 0x0f0f)
    n = (n & 0x00ff) + (n >> 8 & 0x00ff)
    return n

このやり方は、bit数が多いほど効果が高いです。例えば32bit長、64bit長でのビットカウントはさらに効果的になります。

結果確認

正しく計算できているか、bit_count()とbit_count2()の結果を比較してみます。

import random

def bit_count(n) :
    cnt = 0
    for i in range(16):
        if n%2 == 1 :
            cnt+=1
        n = n >> 1

    return cnt

def bit_count2(n) :
    n = (n & 0x5555) + (n >> 1 & 0x5555)
    n = (n & 0x3333) + (n >> 2 & 0x3333)
    n = (n & 0x0f0f) + (n >> 4 & 0x0f0f)
    n = (n & 0x00ff) + (n >> 8 & 0x00ff)
    return n


for i in range(10) :
    n = random.randint(0, 1<<16)
    ret = bit_count(n)
    print(f"{n:5d} {format(n, '016b')} {ret:2d}")
 

for i in range(10) :
    n = random.randint(0, 1<<16)
    ret1 = bit_count(n)
    ret2 = bit_count(n)
    print(f"{n:5d} {format(n, '016b')} {ret1:2d} {ret2:2d}")

## 結果
# 65357 1111111101001101 12 12
# 38119 1001010011100111  9  9
# 28729 0111000000111001  7  7
# 13614 0011010100101110  8  8
#  9112 0010001110011000  6  6
# 43197 1010100010111101  9  9
# 31144 0111100110101000  8  8
# 24819 0110000011110011  8  8
# 43637 1010101001110101  9  9
# 58173 1110001100111101 10 10

結果をみると、正しく計算できていることがわかります。

処理時間計測

では、どれくらい高速化できたかをチェックしてみます。下記のプログラムでは、処理を1000万回繰り返して測定しています。

import time

def bit_count(n) :
    cnt = 0
    for i in range(16):
        if n%2 == 1 :
            cnt+=1
        n = n >> 1

    return cnt

def bit_count2(n) :
    n = (n & 0x5555) + (n >> 1 & 0x5555)
    n = (n & 0x3333) + (n >> 2 & 0x3333)
    n = (n & 0x0f0f) + (n >> 4 & 0x0f0f)
    n = (n & 0x00ff) + (n >> 8 & 0x00ff)
    return n


start = time.time()

n = 10_000_000
for i in range(n) :
    bit_count(i)

end = time.time()
print(f"{(end - start)} sec")
# 7.029723882675171 sec

start = time.time()

for i in range(n) :
    bit_count2(i)

end = time.time()
print(f"{(end - start)} sec")
# 1.8477487564086914 sec

結果を見るとループ版（bit_count）では7.03秒、高速化版（bit_count2）では1.85秒と3.8倍高速に処理できています。

ビットをカウントする処理を繰り返すようなプログラムの場合、この処理時間の差は結構効いてきます。