Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

この記事は何か?

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

たとえば十進数で 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)])
ataham
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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした