おいおい学習者 この記事では、プログラミング言語 Python を使って、整数に設定されているビットの総数を計算します。
この問題では、Bit Manipulationの概念の意義と威力を示すことになるでしょう。
セットビットとは – はじめに
2進数の世界では、セットビットは1によって表されます。
つまり、基本的には、ある数の2進数に含まれる1の総量を求めればよいのです。
|
1
2
3
4
5
6
7
8
9
|
def countsetbits(A):
count = 0 while(A!=0):
A = A & (A-1)
count = count+1 return(count)
n = int(input("Enter the Number: "))
print(countsetbits(n))
|
問題を理解する
数 N が与えられた。
数Nの2進数版に存在するセットビットの総数を返せ。
例えば
与えられた数 (N) = 5 の場合。
5の2進数は101なので、結果は2です。
101の中に存在する1の総数は2であり、したがって、セットビットの数は2です。
アプローチ1：手動変換
与えられた10進数を2進数に変換し、変換後の2進数における1の総数を数えます。
しかし、これは問題の効率的な解決策とは言えない。
この例では、時間の複雑さは線形になるが、この作戦をより効率的にすることができる。
アプローチ2：ビット操作
このアプローチでは、Bit Manipulationのメソッドの1つを見ていきます。
この方法を採用することで、コードとアプローチの効率を向上させることができます。
以下にその手順を説明します。
- N>0かどうかをチェックする
- AとA-1のANDを計算する
-
- A != 0 になるまで手順 2 を繰り返す。
- 反復回数のカウントを保持する
- このカウントは、数Nのセットされたビットの数に等しい
Pythonを使ったセットビットの計算
Enter the Number: 5
2 |
サンプル出力
Enter the Number: 100
3 |
問題の背景となる概念、そして問題の解決策を理解していただけたでしょうか？
チュートリアルを読んでいただき、ありがとうございました。