Number of 1 Bits

easyFREEBit ManipulationBlind 75

Given a positive integer, return the number of set bits (1s) in its binary representation (also known as Hamming weight).

Example

Input

Output

Reasoning

The input n is a non-negative integer given in ordinary decimal form, here $11$ . The question is about how it is written in base 2, not about its decimal digits.
Write $11$ as a sum of distinct powers of two: $11 = 8 + 2 + 1 = 2^3 + 2^1 + 2^0$ . The power $2^2 = 4$ is not needed.
Each power that appears becomes a $1$ in that position and each missing power becomes a $0$ , so reading positions $3, 2, 1, 0$ gives $1011_2$ .
The Hamming weight is the number of $1$ digits: three of the four positions are set, so the output is 3.
Notice that the answer depends only on how many powers of two are used, not on their size: $128 = 2^7$ gives 1 even though it is large, while $255 = 2^8 - 1 = 11111111_2$ gives 8. An input of $0$ uses no powers, so its weight is $0$ .

Constraints

0 <= n <= 2^31 - 1

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The problem revolves around bit manipulation, which involves performing operations directly on the binary representation of a number. To tackle this problem, it's essential to understand how numbers are represented in binary and how to manipulate individual bits. In binary, each digit (or bit) can be either 0 or 1. The Hamming weight of a binary number is the number of bits that are set to 1.

Understanding the binary number system and basic bitwise operations is crucial. Bitwise operations include AND (&), OR (|), XOR (^), and NOT (~), among others. These operations allow you to manipulate the bits of a number directly. For example, the bitwise AND operation (&) compares each bit of the first operand to the corresponding bit of the second operand. If both bits are 1, the corresponding result bit is set to 1. Otherwise, the corresponding result bit is set to 0.

The concept of bit shifting is also important in bit manipulation. Bit shifting involves moving the bits of a number to the left or right and filling the vacant positions with zeros. This can be useful for dividing or multiplying a number by a power of 2. For instance, shifting the bits of the number 10 (which is 1010 in binary) one position to the left results in 20 (which is 10100 in binary).

Algorithm/Approach

The general approach to solving bit manipulation problems involves understanding the binary representation of numbers and using bitwise operations to achieve the desired outcome. In the case of counting the number of set bits (1s) in a binary representation, the algorithm likely involves iterating through each bit of the number and checking if it's set to 1.

Step-by-Step Strategy

To solve this problem, follow these steps:

Understand the binary representation of the given positive integer.
Determine a method to iterate through each bit of the number.
Decide on a bitwise operation or approach to check if a bit is set to 1.
Count the number of bits that are set to 1.
Return the total count of set bits.

Common Pitfalls

When implementing the solution, watch out for:

Incorrectly handling the iteration through the bits of the number.
Failing to properly check if a bit is set to 1.
Not considering the case where the input number is 0.

Time & Space Complexity

The expected time complexity for this problem is $O(\text{log}(n))$ , where $n$ is the input number, because in the worst case, you need to iterate through all the bits of the number, and the number of bits in the binary representation of $n$ is proportional to $\text{log}(n)$ . The space complexity is $O(1)$ , as you only need a constant amount of space to store the count of set bits and any other necessary variables.

solution.py

Python 3.13

Test results