Code โ€บ algorithm-study

LeetCode 191 - Number of 1 Bits

A Python solution that counts 1 bits by repeatedly dividing by 2

algorithmleetcodebit-manipulationpythonlearning

This problem asks for the number of 1s in the binary representation of an integer. The loop simply checks the last bit, counts it if needed, and then removes it.

  • Problem link: 191. Number of 1 Bits
  • Summary: Given an integer n, return the number of 1 bits in its binary representation.

For example, if n = 11, the binary form is 1011, which contains three 1s.

This problem does not require converting the number into a string. The last bit can be checked directly by taking n % 2, and then the value can be reduced by dividing by 2.

Approach

The most direct idea is to look at the remainder when dividing by 2. For any integer, the remainder by 2 is the last binary bit. If the remainder is 1, I count one bit. If it is 0, I move on. Then I divide n by 2 to discard that last bit and repeat the process.

count = 0
while n > 0:
    count += n % 2
    n //= 2

This keeps the logic simple and avoids building the full binary representation as a string.

Troubleshooting

The main thing to get right is the loop condition. The loop has to continue until n becomes 0, or the last bit can be missed.

It is also cleaner to start count at 0. Since the remainder check already counts each 1 bit directly, there is no need for a separate initial offset.

Complexity analysis

  • Time complexity: O(log n)

    • n is cut in half on every iteration.
    • The loop runs once per binary digit.

  • Space complexity: O(1)

    • Only a counter and the current value are stored.
    • No extra array or string is created.

Implementation code

The final solution counts 1 bits by checking the remainder and shrinking the number one bit at a time.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n > 0:
            count += n % 2
            n //= 2

        return count

The idea is straightforward: inspect the last bit, count it if it is 1, and remove it. Once that loop is clear, the whole problem is just repeated bit inspection.

Summary and reflection

This problem is a good reminder that binary reasoning can stay simple. I do not need to materialize the bits as a string, and I do not need a data structure at all. Repeatedly dividing by 2 turns the binary representation into a step-by-step check, and that is enough to make the solution short and predictable.