Pythonでのビット操作の話(LeetCode)

• この記事を書く理由
• 問題
• 解答

この記事を書く理由

LeetCodeでTop Interview Questions(面接のコーディング試験で聞かれやすい問題を集めたやつ)のEasy問題を解いている時にビット操作を求められたので念のため書いておきます。

問題

Number of 1 Bits

解答はここ。

符号なしの整数を引数として受け取り、その整数が持つ「1」ビットの数（ハミングウェイトとも呼ばれる）を返す関数を書いてください、という問題です。

Example 1:

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.

Example 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`.

解答

# O(N) Solution

class Solution:
    def hammingWeight(self, n: int) -> int:
        bits = 0
        for i in range(32):
            bits += (n&1)
            n = n >> 1
        return bits
# Runtime: 28 ms, faster than 89.38% of Python3 online submissions for Number of 1 Bits.
# Memory Usage: 14.1 MB, less than 90.33% of Python3 online submissions for Number of 1 Bits.

例えば、
00000000000000000000000000001011
の時を考えてみましょう。この場合、1の数は3つなので3を返せば正解になります。

今回2進数として渡される値の桁数は32桁までなのでfor文で32回回してあげると良いことになります。
そして、bitsを定義し、1の数をカウントしていきます。
bits += (n&1)で仮に値が1ならば1をbitsに加算し、0ならば加算をせずにそのままbitsの値を保持します。

その後、ビット右シフトを
n = n >> 1で行い、それを32回繰り返す、というものです。
ここを書く時に右シフトのやり方をすっかり忘れていたので困りました。

他にも以下のような書き方があります。

class Solution:
    def hammingWeight(self, n: int) -> int:
        sum = 0
        while n != 0:
            sum += 1
            n &= (n-1)
        return sum
# Runtime: 28 ms, faster than  89.33%  of  Python3  online submissions for  Number of 1 Bits.
# Memory Usage: 14.2 MB, less than  42.11%  of  Python3  online submissions for  Number of 1 Bits.

といっても、SolutionのJavaのコードを真似て書いただけですが。

簡単だけどちょっと困ったので今後忘れた頃に使われそうなので自戒のためにメモとして残しておきます。

ではでは。