Count the number of set bits (1s) in the binary representation of a non-negative integer.
- User
Count the number of set bits (1s) in the binary representation of a non-negative integer.
Assistant
To count the number of set bits (1s) in the binary representation of a non-negative integer, we can utilize an efficient algorithm known as Brian Kernighan’s Algorithm. This method leverages the property that subtracting 1 from a number flips all the bits from the rightmost set bit (1) onward. By performing a bitwise AND between
nandn - 1, we effectively clear the rightmost set bit. Repeating this process untilnbecomes zero allows us to count the number of set bits efficiently.
✅ Advantages of Brian Kernighan’s Algorithm
- Time Complexity:
O(k)wherekis the number of set bits. This is more efficient than looping through all bits (O(log n)), especially for numbers with few 1s. - Space Complexity:
O(1)— no extra space used beyond a few variables. - Handles Edge Cases: Works correctly for
n = 0(returns 0), which has no set bits.
🧠 How It Works (Example with
n = 5)Binary of 5 is
101.n = 5,n & (n - 1)→5 & 4 = 4→ count = 1n = 4,4 & 3 = 0→ count = 2- Loop ends as
n = 0
Result: 2 set bits.
🧪 Sample Code
def count_bits(n): """ Count the number of set bits (1s) in the binary representation of a non-negative integer. Args: n (int): A non-negative integer. Returns: int: The number of 1s in the binary representation of n. """ count = 0 while n: n &= n - 1 # Clear the rightmost set bit count += 1 return count
📈 Example Usage
print(count_bits(0)) # Output: 0 print(count_bits(1)) # Output: 1 print(count_bits(5)) # Output: 2 (binary: 101) print(count_bits(7)) # Output: 3 (binary: 111) print(count_bits(8)) # Output: 1 (binary: 1000) print(count_bits(1023)) # Output: 10 (binary: 1111111111)
🆚 Alternative Approaches
- String Conversion Method (Simple but less efficient):
def count_bits(n): return bin(n).count('1')- Pros: Very readable and easy to implement.
- Cons: Involves string conversion, which may be slower for large integers.
- Bit Shifting Method (More efficient than string):
def count_bits(n): count = 0 while n: count += n & 1 n >>= 1 return count- Pros: No string conversion, efficient for small integers.
- Cons: Always loops through all bits, even if many are 0.
✅ Conclusion
Brian Kernighan’s algorithm is the optimal choice for this problem due to its efficiency and clarity. It is both time-efficient and readable, making it ideal for real-world applications where performance matters.
- Time Complexity:
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.