💬 Discord
Sign In
NeetCode #853LC-191EasyBit ManipulationBlind 75NC 150NC 250
← Back to All Problems

#853 · #191 · Number of 1 Bits(位 1 的个数)

📌 Problem Statement & Constraints

Write a function that takes an unsigned integer n and returns the number of set bits in its binary representation (the Hamming weight). Constraints: 1 <= n <= 2^31 - 1, so the value fits in 32 bits.

💡 Core Algorithmic Approaches

  1. The naive loop tests the lowest bit with n & 1 and shifts n right until it becomes zero.
  2. A faster variant is Brian Kernighan's trick: n &= n - 1 clears the lowest set bit, so the loop runs exactly once per set bit instead of once per bit position.
  3. Both are correct because clearing bits never creates new ones; the loop terminates when no set bits remain.
  4. Python also exposes the built-in int.bit_count, but the interview expects the manual loop.

💻 Benchmark Python3 Implementation

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1              # clears the lowest set bit
            count += 1
        return count


# Shift-and-test variant: runs once per bit position
class Solution2:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(k) where k is the number of set bits (Kernighan); O(32) for the shift variant.
💾 Space Complexity
O(1): a single counter.

⚠️ Interview Pitfalls & Follow-ups

  • Treating n as signed: in fixed-width languages an arithmetic right shift on a negative value never reaches zero, so the loop hangs. Python's integers are unbounded, but n &= n - 1 is the portable fix.
  • Assuming the Kernighan loop always runs 32 times: it runs once per set bit, so n = 8 finishes after one iteration.
  • Using bin(n).count as the whole answer: it is idiomatic Python but skips the bit manipulation the problem is testing.
  • Shifting the wrong direction: n >>= 1 discards the bit just tested; shifting left would loop forever.