ある10進数の数について、その数を2進数にしたときに含まれる「１」の数を数える方法を考えます。
Pythonのbin()という組み込み関数を使うと、10進数を2進数に変換できます。
>>> bin(2) '0b10' >>> bin(10) '0b1010' >>> bin(10000) '0b10011100010000' >>> bin(100000) '0b11000011010100000'
10進数2は2進数10で1の数は1、10進数10は2進数1010で1の数は2、10進数10000は2進数10011100010000で1の数は5、10進数100000は2進数11000011010100000で1の数は6、となります。
以下を参照しています。
組み込み関数bin()を使う
- bin()で2進数に変換する。
- 最初の0bを削除して、それぞれの桁の1を足す。
def count_ones_by_bin(num):
bin_num = bin(num)[2:]
count = 0
for i in bin_num:
count += int(i)
return count
一桁ずつビットマスク
一桁ずつ1と&をとっていきます。
10進数10で考えてみます。10進数10は2進数1010でした。
| 1 | 0 | 1 | 0 |
これと10進数1、つまり2進数0001のANDを取ります。
| 0 | 0 | 0 | 1 |
1桁目は(0&1)で0です。
10進数10、つまり2進数1010を1つ右シフトして、また1とANDをとります。
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 |
1桁目は(1&1)で1です。 …
…シフト演算を0になるまで続ければ、1の数が分かります。
def count_ones_by_bitmask(num):
count = 0
while num:
count += num & 1
num >>= 1
return count
1を引いてANDをとる
10進数10で考えてみます。10進数10は2進数1010でした。
| 1 | 0 | 1 | 0 |
この数字から１を引きます。
| 1 | 0 | 0 | 1 |
ANDを取ることで一番小さい1を取っている桁を0にすることができます。
def count_ones_by_minus(num):
count = 0
while num:
num &= num -1
count += 1
return count
ビットカウントテーブルを使う
1桁ずつビットマスクをしていたのを、テーブルを作っておくとことで、まとめてやってしまおうというような考え方です。ここでは8ビット単位で考えています。
事前に、0から255までの1の数を数えて、リストにしておきます。
10進数10000は2進数10011100010000です。
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
16進数FFを考えます。
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
ANDを取ります。
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
10進数に直すと16です。事前作成していた配列から下8ビットには1つの1が含まれていることが分かります。
次に元の数を8ビット右シフトします。
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
これと16進数FFとのANDを取ります。…
…シフト演算を0になるまで続ければ、1の数が分かります。
def count_ones_by_table(num):
bit_table_256 = [
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
]
count = 0
count += bit_table_256[num & 0xFF]
count += bit_table_256[(num >> 8) & 0xFF]
count += bit_table_256[(num >> 16) & 0xFF]
count += bit_table_256[(num >> 24) & 0xFF]
return count
各桁を1の個数と考えてまとめてシフト
以下の40ページ目から分かりやすく説明されています。
def count_ones_by_shift(num):
num = (num & 0x55555555) + ((num & 0xAAAAAAAA) >> 1)
num = (num & 0x33333333) + ((num & 0xCCCCCCCC) >> 2)
num = (num & 0x0F0F0F0F) + ((num & 0xF0F0F0F0) >> 4)
num = (num & 0x00FF00FF) + ((num & 0xFF00FF00) >> 8)
num = (num & 0x0000FFFF) + ((num & 0xFFFF0000) >> 16)
return num
同じことですが、下のようにも書けます。こちらのほうがコードの意味はわかりやすいです。
def count_ones_by_shift_2(num):
num = (num & 0x55555555) + (num >> 1 & 0x55555555)
num = (num & 0x33333333) + (num >> 2 & 0x33333333)
num = (num & 0x0F0F0F0F) + (num >> 4 & 0x0F0F0F0F)
num = (num & 0x00FF00FF) + (num >> 8 & 0x00FF00FF)
num = (num & 0x0000FFFF) + (num >>16 & 0x0000FFFF)
return num