ビットカウント（ビットが 1 である個数）

「ビットカウントする高速アルゴリズムをPythonで実装しながら詳しく解説してみる」というのを見つけた。

Python の整数は 64 ビット整数，R は 32 ビット整数であることを考慮し，以下のように翻訳した。

bitcount = function(n) {
  # nの立っているビット数をカウントする関数(nは64bit整数)
  # 2bitごとの組に分け、立っているビット数を2bitで表現する
  n = n - bitwAnd(bitwShiftR(n, 1), 0x55555555)
  # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
  n = bitwAnd(n, 0x33333333) + bitwAnd(bitwShiftR(n, 2), 0x33333333)
  n = bitwAnd((n + bitwShiftR(n, 4)), 0x0f0f0f0f) # 8bitごと
  n = n + bitwShiftR(n, 8) # 16bitごと
  n = n + bitwShiftR(n, 16) # 32bitごと = 全部の合計
  return(bitwAnd(n, 0x0000007f))
}

正しく移植できたか，確認してみる。

> bitcount(7)
[1] 3
> bitcount(127)
[1] 7
> bitcount(2^31-1)
[1] 31
> bitcount(-1)
[1] 32

R の intToBits() は，整数の二進表記を得るものである。これを用いてビット 1 を数えるのは自然である。 intToBits() のクラスは "raw" なので，as.integer() で整数化してから合計する。

bitcount2 = function(n) {
  return(sum(as.integer(intToBits(n))))
}

同じ結果になることが確認できる。

> bitcount2(7)
[1] 3
> bitcount2(127)
[1] 7
> bitcount2(2^31-1)
[1] 31
> bitcount2(-1)
[1] 32

では，両者の速度比較をしてみる。intToBits() がベクトルに対応していないので，心ならずも for ループで検証する。

> mx = 1000000000
> n = sample(mx, 1000000) # 100 万個の整数
> a = integer(mx)
> b = integer(mx)
> system.time({for (i in n) a = bitcount(i)})
   ユーザ   システム       経過  
     6.915      0.198      7.118
> system.time({for (i in n) b = bitcount2(i)})
   ユーザ   システム       経過  
     1.620      0.148      1.769
> all(a == b) # どちらの結果も同じか？
[1] TRUE

結論は，「intToBits() を使う方が 4 倍ほど速い」ということだが，100 万個の整数を処理して 2 〜 7 秒なので，1 個や 100 個なら，どちらの方法でも，ゴミのような差しかない。

======================================

ついでに，Python でも代替関数について調べてみた。

Python には二進表記をするための bin() がある。これは文字列として二進数を返すので，文字列の中に '1' がいくつあるか数える。

大元のビットカウントのプログラム

def bitcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''
    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)
    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

対する，bin() を使う関数。短い。

def bitcount2(x):
    return sum([i == '1' for i in bin(x)])

100 万個の整数を対象とする。

import scipy as sp
a = sp.random.randint(-10, 100000000, 1000000)


def func1(): # 4.383 sec.
    x = [bitcount(i) for i in a]

def func2(): # 3.416 sec.
    y = [bitcount2(i) for i in a]

やはり，bin() を使う方が速い。
sp.all(x == y) は True である。