【LeetCode】191. Number of 1 Bits 解答・解説【Python】

問題
1. 原文
2. 内容
解答
メモ・参考・感想

問題

原文

Write a function that takes the binary representation of an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

Example 1:

Input: n = 00000000000000000000000000001011 Output: 3 Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

1
2
3

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000 Output: 1 Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

1
2
3

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101 Output: 31 Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

1
2
3

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Constraints:

The input must be a binary string of length 32.

Follow up: If this function is called many times, how would you optimize it?

内容

※正しくない可能性があります。

解答

解答1：Python , ビット操作

class Solution:
    def hammingWeight(self, n: int) -> int:
        answer = 0
        
        for i in range(32):
            #"&" を使うことでnの下1桁とビットとしての1の論理積を取る。論理積の結果が1ならanswerをインクリメント
            answer += n&1
            #"%"でも同じような結果は得られるが、除算操作になるので計算量が大きくなる可能性あり。
            #answer += n%2
            #ビットシフト　
            n >>= 1

        return answer

class Solution:

def hammingWeight(self, n: int) -> int:

answer = 0

for i in range(32):

#"&" を使うことでnの下1桁とビットとしての1の論理積を取る。論理積の結果が1ならanswerをインクリメント

answer += n&1

#"%"でも同じような結果は得られるが、除算操作になるので計算量が大きくなる可能性あり。

#answer += n%2

#ビットシフト　

n >>= 1

return answer

論理積を取りながらビットシフトを繰り返すことでハミング重みを数える。

「&」はnの下一桁と1を比較し、どちらも1なら1を返す。それ以外は0を返す。

ビットシフトすることにより、桁を一つ右にずらす。右端の桁は除外されるイメージ。

右端から1桁ずつ論理積を取って桁を下げていくことで、ハミング重み(1の数)を数えている。

解答2：

follow up

この関数が何度も呼び出される場合、どのように最適化するか？

以下はchatGPTの解答

ルックアップテーブルを使用する：すべての可能な32ビットパターンに対して、ハミング重みを計算して事前に保存します。関数が呼び出されるたびに、入力パターンに対応する重みを返すことができます。これにより、ループ内でのビット単位の操作が不要になり、関数の速度が大幅に向上します。ただし、この方法は、32ビットの入力に対してのみ適用可能であり、RAMを多量に使用する可能性があることに注意してください。

1ビットごとの数え上げを使用する：整数をビット単位で処理する代わりに、各ビットを順番に数え上げます。ビットが1であれば、重みをインクリメントします。この方法は、入力が大きな場合でも効果的ですが、32ビットの入力に限定されていません。

ハードウェア命令を使用する：ハミング重みを計算するための特別なハードウェア命令がいくつかあります。たとえば、IntelプロセッサにはPOPCNT命令があります。この命令は、入力の1のビットの数をカウントするのに非常に効果的です。ただし、これはプロセッサに固有の機能であり、すべてのプラットフォームで利用できるわけではありません。

1は、全てのパターンを記憶しておく必要があるため、膨大な記憶容量が必要。多分現実的ではない。

2は、解答1に違い気がするが、ちょっとよくわからない。要勉強

3は、Pythonからだとハードウェア命令を直接呼び出すことはできないので、ライブラリを使ってC言語を呼び出し、C言語にあるハードウェア命令を呼び出すという形で実装することができると思われる。ただ、ここまで操作が低水準な段に至るとPythonは使われないような気もする。

chatGPTの解答自体が正しいかどうかの判断がつかないので、鵜呑みにしないようにしたい。