Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationEventAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What are the problem?

More than 1 year has passed since last update.

@ataham

立ちあがっているビットを数え上げるアルゴリズム

この記事は何か?

立ちあがっているビットを数え上げるアルゴリズムについて取り上げる。

たとえば十進数で 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 の最下位ビットを落とせる。したがって x0 になるまで 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)])
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
2
Help us understand the problem. What are the problem?