この記事は何か?
立ちあがっているビットを数え上げるアルゴリズムについて取り上げる。
たとえば十進数で 7 という数は Python では 0b111 と表現できる。 0b は単に数が二進数であることを表現しているだけなので、数値表現部分は 111 である。つまり、立ちあがっているビットは 3 つである。このように、数を十進数で与えられたときに、それを二進数で表現した場合に立ちあがっているビット数を返す方法を探求したい。
最下位ビットからナイーブに数え上げる方法
次のような方法がもっともナイーブだろう。
def count_bits(n):
count = 0
while n:
if n & 1 == 1:
count += 1
n >>= 1
return count
なんのことはない。数を 1 ビットずつ右にシフトしながら、最下位ビットと 1 の AND が 1 になるものを数えているだけである。
立ち上がっているビットを右から落としていく方法
x = x & (x - 1) で x の最下位ビットを落とせる。したがって x が 0 になるまで x = x & (x - 1) を繰り返すことで、立ち上がっているビットを数えられる。
具体的には次のように書ける。
def count_bits(n):
count = 0
while n:
count += 1
n = n & (n - 1)
return count
数と立ち上がっているビット数のマップをあらかじめ作っておく方法
あらかじめ Python のリストに「立ち上がっているビット数」を計算してつめておく方法も考えられる。 CPython のリストは C 言語 での配列で実装されているため、この方法であれば与えられた数を二進数表現した際に立ち上がっているビットの数を O(1) で返せる。
仮に 64 ビットの整数が入力される場合、この方法を単純に適用するとリストが大きくなりすぎるため現実的ではない。そういうときは全体のビット列を n 分割するとよい。入力が 64 ビットの整数である場合、16 ビットごとに分割して考えると、2^16 (すなわち 65536) 個の要素を持つリストさえあればよい。
具体的には、まず次のように 16 ビットの整数に対応するリストを作成する。
def _count_bits(n):
count = 0
while n:
count += 1
n = n & (n - 1)
return count
PRE_CALCULATED_COUNT = []
for i in range(65536): # 65536 = 2^16
PRE_CALCULATED_COUNT.append(_count_bits(i))
ここで計算した PRE_CALCULATED_COUNT を使い、ビットマスクを使いながら 16 ビットずつ立ち上がりビット数を調べて足し合わせればよい。
def count_bits(n):
bitmask = 0xffff
return (PRE_CALCULATED_COUNT[(n & bitmask)] +
PRE_CALCULATED_COUNT[(n >> 16 & bitmask)] +
PRE_CALCULATED_COUNT[(n >> (16 * 2) & bitmask)] +
PRE_CALCULATED_COUNT[(n >> (16 * 3) & bitmask)])