アルゴリズムのすばらしさをうかがう——整数の2進数の中の1の個数を統計します

原文は私のブログのホームページで発表して、転載して出典を明記して下さい
前言
私はずっとアルゴリズムが好きな人で、アルゴリズムは本当にとてもすばらしくて不思議だと思います!!!春節にアルゴリズムの本を読む時間があって、思想と技術が沈殿したすばらしさを体得して、今日統計のバイナリの中の1の個数というもともととても簡単なテーマを見て、前にも見たことがあって、しかし今回本を読んで深く考えた後に中の水がまだ深いことを発見して、特にpythonのプログラムの猿で更に理解するべきで、雑談は少なくて、本題を始めます.
タイトル
1つの関数を実現して、1つの整数を入力して、この数のバイナリ表現の中の1の数を出力します
テーマ分析
このテーマを手に入れると、誰もがすぐに考えを持っているに違いない.いくつかのキーワードがすぐに頭の中に現れた.「循環」、「右に移動」、「と」.そしてすぐに関数を書き出して、適当にいくつかの数を入力して検証して、大丈夫です...しかし、この問題で注意しなければならないのは、まず整数であり、正の整数と負の整数を含む.次にpythonでは、データビット数は比較的曖昧な概念であり、プログラムにはほとんど存在しない.オフセット後、intを自動的にlongタイプに変換するので、pythonプログラマーにとって、整数のビット数を事前に理解したり、python言語でC言語を呼び出したりする必要がある.その中の集中解法を以下に挙げる.
テクニック:pythonの左シフトと右シフトは他のC/C++などの定義と結果とは異なり、自分で実験することができます.pythonの定義:右シフトnビットはpow(2,n)で除算され、左シフトnビットはpow(2,n)で乗算され、オーバーフローはありません(削除されたintはlongタイプにアップグレードされます).
解法
上のテーマを分析したとき、誰もがテーマを見て心の中に最もnaiveが現れると言ったが、間違った解法(どんな言語を使っても):

def count(num):
    cnt = 0
    while num:
        if num & 1 == 1:
            cnt += 1
        num = num >> 1
    return cnt

なぜ彼が間違っているのか、みんなは1つの負の整数を入力して見ることができて、プログラムは死の循環に陥ることができて、他の言語の中で、負数はコンピュータの中で補符号で表して、最高位は1で、右に移動する過程の中で、高位はすべて1で埋めて、だからwhile numのこの条件はずっと本当です;pythonでは,右シフトの定義に基づいて自己推定できる.現在numを右にシフトしてはいけない以上、私たちは1を左にシフトすることができ、32の整数の中で、最大32ビットを左にシフトすると、1がゼロになるので、これは判断条件として、C言語では上記と似たようなコードを書くことができますが、pythonでは、一緒に左にシフトすることができます(仮想メモリサイズの桁数まで)、ここではpythonのライブラリctypesを使いました.pythonでC言語を使用します.コードは次のとおりです.

from ctypes import *
def count(num):
    cnt = 0
    flag = 1
    while c_int(flag).value:
        if c_int(num & flag).value:
            cnt += 1
        flag = flag << 1
    return cnt

上記のコードは正数負数を入力してもゼロを入力しても正しい答えが得られますが、すべての整数に対して32回ループして結果を得る必要があり、改善を続けます.簡単な例を見ると、整数12のバイナリは1100と表示され、それを1011に減らし、得られた結果を元の木とビットアンドを行い、1000を得るので、法則がないことがわかりますか?1つの整数から1を減算して元の整数とビットを合わせた結果,整数のバイナリ表現のうち右端の1つを0にすることに相当し,この法則に従って遍歴すると,関数のループ回数はバイナリのうちの1回数となる.コードは次のとおりです.

from ctypes import *
def count(num):
    cnt = 0
    while c_int(num).value:
        cnt += 1
        num = (num -1) & num
    return cnt

テクニック:1つの整数から1を減算して元の整数とビットを押すと、整数のバイナリ表現の右端の1つが0になる
以上は様々な言語で通用する方法であり、pythonを例に挙げたにすぎないが、pythonでは言語で彼のライブラリ関数を利用してこの問題を簡単に解決することができる.コードは以下の通りである.

def num_of_one(num):
    '''
 count the num of "one" in num n
 bin():convert the num to binary string
 :param num: num num
 :return: the num of "one" in num
 '''
    if num >= 0:
        nbin = bin(num)
        return nbin.count('1')
    else:
        num = abs(num)
        nbin = bin(num-1)
        return 32 - nbin.count('1')

上のコードは正数と負数をより詳細に区別するために使用されていますが、pythonのいくつかの特性を利用して、コードを簡略化するのは以下の通りです.

def num_of_one(num):
    nbin = bin(n & 0xffffffff)
    return nbin.count('1')

テクニック:バイナリにとって、まず1を減らしてから逆を取るのは、先に逆を取ってから1を加えるのと同じです.
ブロガーのJohn Ramboは私のブログの下でもう一つの方法を提供しました.この方法も非常に巧みで、まず1つのリストで0から15のバイナリの中の1の数を保存して、計算する時に4人ごとに表を調べて、コードは以下の通りです.

#Add up the number of 1 bits in every 4 bits.
#number of 1 bits in 0x0 to 0xF.
counts = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4]

def num_of_one(num):
    result = 0
    for i in range(0,32,4):
        result += counts[num >> i & 0xf]
    return result

テクニック:pythonでは、負の数と0 xffffffffはビットと後に符号なしの数になり、バイナリは符号化形式として表されます.
PowerShellの無料ソフトウェアは、巧みな方法を提供しています.

$num=Read-Host -Prompt "       (     )"
([System.Convert]::ToString($num,2)).replace("0","").length
#      

まとめ
このブログのテーマは多くのプログラマーにとって少しもよく知られていませんが、これらの問題を完璧に解決するにはいくつかの思考が必要です.同時に、テクニックも少なくありません.アルゴリズムはこんなに美しくて、コンピュータの世界は憧れています.