Number of 1 Bits
Problem Statement
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
Constraints:
- The input must be a binary string of length 32
- In Java, the input is given as an integer, but you need to process it as if it were an unsigned value.
Input Format:
- An unsigned integer n
Output Format:
- Return the number of '1' bits in n.
Examples:
Example 1:
Input:
n = 00000000000000000000000000001011
Output:
3
Explanation:
The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:
Input:
n = 00000000000000000000000010000000
Output:
1
Explanation:
The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:
Input:
n = 11111111111111111111111111111101
Output:
31
Explanation:
The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.
Solutions
Loop and Bit Manipulation Approach
Use a loop to check each bit in the number. Shift the number right after each check to examine the next bit.
Brian Kernighan's Algorithm
This approach uses a trick that clears the rightmost set bit in each iteration, reducing the number of iterations needed.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize count = 0
- Iteration 1: Check rightmost bit, n & 1 = 1, so count = 1. Then n >>> 1 = 00000000000000000000000000000101
- Iteration 2: Check rightmost bit, n & 1 = 1, so count = 2. Then n >>> 1 = 00000000000000000000000000000010
- Iteration 3: Check rightmost bit, n & 1 = 0, so count = 2. Then n >>> 1 = 00000000000000000000000000000001
- Iteration 4: Check rightmost bit, n & 1 = 1, so count = 3. Then n >>> 1 = 00000000000000000000000000000000
- All remaining bits are 0, so final count = 3
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the process of checking each bit in the binary representation, or the process of clearing the rightmost 1 bit in each iteration.
Key visualization elements:
- current bit
- current bit count
- remaining bits to check
Similar Questions
Counting Bits
EasyGiven an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Reverse Bits
EasyReverse bits of a given 32 bits unsigned integer. Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
Implementation Notes
This problem is a classic bit manipulation problem. Brian Kernighan's algorithm provides an efficient way to count bits, which is useful for many other bit manipulation problems.