Start learning free

LESSON 590 OF 673 · BIT MANIPULATION

Number of 1 Bits in Python: O(k) with n & (n - 1)

Practice O(k) Read the full explanation

Given a non-negative integer n, return the number of 1 bits in its binary representation (also called its Hamming weight).

 

Example 1:

Input: n = 11
Output: 3
Explanation: 11 in binary is 1011, which has three 1 bits.

Example 2:

Input: n = 128
Output: 1
Explanation: 128 in binary is 10000000, which has a single 1 bit.

Example 3:

Input: n = 2147483645
Output: 30
Explanation: 2147483645 in binary is 1111111111111111111111111111101: thirty-one digits, and all but one of them are 1.

 

Constraints:

  • 0 <= n <= 231 - 1
Note:

Your algorithm should run in O(k) time, where k is the number of 1 bits in n, and use O(1) extra space.



Look at what subtracting 1 does to a number in binary: its lowest 1 bit turns into 0, every 0 below it turns into 1, and the higher bits stay the same. For example, 12 is 1100 and 11 is 1011.

So n AND n - 1 is n with its lowest 1 bit removed: 1100 AND 1011 is 1000. Keep doing it until n becomes 0, and count how many times you did it.

Each pass of the loop removes one 1 bit, so the loop runs k times, at most 31 for these values: O(k) time.
We keep only the count and the number we change, so the extra space is O(1).
STEP 1 OF 5
    Ctrl + Enter to check

    PYTHON · BIT MANIPULATION

    Number Of 1 Bits in Python, explained

    Problem overview

    The method hammingWeight receives a non-negative integer n and returns how many 1 bits its binary form has. This count is also called the Hamming weight.

    For n = 11 the binary form is 1011, which has three 1 bits, so the result is 3. For n = 128, the binary form is 10000000, a single 1 bit, so the result is 1.

    The lesson asks for O(k) time, where k is the number of 1 bits in n, and O(1) extra space.

    Approach: remove the lowest 1 bit, again and again

    The obvious way is to check all the bits: test the last bit, shift right, and repeat until n is 0. That takes one step per bit position, including the 0 bits. This lesson uses a trick that takes one step per 1 bit only.

    Look at what subtracting 1 does to a number in binary. The lowest 1 bit turns into 0, every 0 below it turns into 1, and the bits above it stay the same. For example, 12 is 1100 and 11 is 1011. If you combine the two with a bitwise AND, which keeps a bit only where both numbers have a 1, you get 1000. The bits above the lowest 1 match in both numbers and survive. The lowest 1 bit and everything below it disagree and vanish.

    So n & (n - 1) is n with its lowest 1 bit removed. Repeating it until n is 0 takes exactly as many rounds as n has 1 bits, and counting the rounds gives the answer.

    Step by step

    1. Start a counter. Create count and set it to 0. It will count the bits as they are removed.
    2. Loop while n != 0. Each pass removes one 1 bit, so n becomes 0 right after its last 1 bit is removed.
    3. Remove the lowest 1 bit. Set n = n & (n - 1). This is the key line of the lesson.
    4. Count it. Add 1 to count in the same pass.
    5. Return count after the loop.

    The solution in Python

    class Solution:
        def hammingWeight(self, n: int) -> int:
            count = 0
            while n != 0:
                n = n & (n - 1)
                count += 1
            return count
    

    Python details worth knowing

    • The parentheses are optional here, but worth keeping. In Python, - binds tighter than &, so n & n - 1 means the same thing. The parentheses make the intent clear, and the order matters when + is involved: 6 & 1 + 1 means 6 & (1 + 1), which is 2, not (6 & 1) + 1.
    • Python integers have no fixed width. There is no 32-bit overflow here, and n - 1 never wraps. The loop would work for numbers far beyond 31 bits too.
    • The loop condition could be written while n: since 0 is false and every other integer is true. The lesson keeps n != 0 because it says exactly what is meant.

    Trace on n = 11

    Running the solution with n = 11 (1011 in binary), n takes these values after each pass:

    Passn in binary after the passcount
    110101
    210002
    303

    The loop stops, and the method returns 3.

    Complexity

    Time: each pass removes one 1 bit, so the loop runs k times, where k is the number of 1 bits. For the lesson's values that is at most 31 passes. So the time is O(k). A number like 128 needs one pass even though it has eight bits.

    Space: only count and n are kept, so the extra space is O(1).

    Edge cases and common mistakes

    • Zero. The loop never runs, and the method returns 0.
    • A power of two. There is one 1 bit, so the loop runs once. For n = 128 the result is 1.
    • All bits set. For n = 2147483645 (thirty-one bits, all but one of them 1) the loop runs 30 times and the result is 30.
    • Forgetting to update n. Writing n & (n - 1) without assigning it back leaves n unchanged and the loop never ends.
    • Mixing up the operators. & is bitwise AND. The word and is logical and gives a different kind of result.

    Testing

    These results come from running the solution:

    nResult
    00
    113
    1281
    214748364530
    Keep going with Python650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free