Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

Count the number of set bits (1s) in the binary representation of a non-negative integer.

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with Qwenqwq-32b’s answer.
  1. User

    Count the number of set bits (1s) in the binary representation of a non-negative integer.

  2. Qwen 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 n and n - 1, we effectively clear the rightmost set bit. Repeating this process until n becomes zero allows us to count the number of set bits efficiently.


    ✅ Advantages of Brian Kernighan’s Algorithm

    • Time Complexity: O(k) where k is 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.

    1. n = 5, n & (n - 1) → 5 & 4 = 4 → count = 1
    2. n = 4, 4 & 3 = 0 → count = 2
    3. 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

    1. 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.
    1. 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.

Identical first prompt