191. Number of 1 Bits

Problem Description

The task is to write a function that receives an unsigned integer's binary representation and calculates the number of '1' bits (also called the Hamming weight) in it. A binary representation means the number is expressed in base 2, consisting only of '0's and '1's. For example, the binary representation of the decimal number 5 is '101', which has two '1' bits.

It's important to note that in some programming languages, such as Java, there isn't an unsigned integer type, which means that you might have to deal with negative numbers as well. However, for the purpose of counting '1' bits, you can consider the binary representation regardless of whether the integer is signed or unsigned. In 2's complement notation, which Java uses to represent signed integers, negative numbers also have a binary representation that can be used to count the number of '1' bits.

Intuition

The solution approach uses a bit manipulation technique that exploits a nice property of binary numbers: subtracting 1 from a number flips all the bits after the rightmost '1' bit (including the '1' bit). So, if we perform a bitwise AND between the number n and n-1, we effectively remove the rightmost '1' bit from n.

For instance, if n is 101100, n-1 is 101011. The bitwise AND of n and n-1 would be 101000, which removes the rightmost '1' bit from the original number. We repeatedly do this operation and count how many times we perform it until n becomes 0. The count gives us the number of '1' bits in the original number since each operation removes exactly one '1' bit.

By following this approach, we can calculate the Hamming weight efficiently. Let’s break down the steps involved in the provided solution:

Initialize a variable ans to zero. This will be used to track the number of '1' bits.
Use a while loop to iterate as long as n is not zero.
Inside the loop, perform the operation n &= n - 1, which removes the rightmost '1' bit from n.
Increment ans by one after each bit-removal operation.
Once n becomes zero, which means all '1' bits have been removed, return ans, the count of '1' bits.

This technique is efficient because it directly targets the '1' bits and minimizes the number of operations relative to the number of '1' bits in the binary representation.

Learn more about Divide and Conquer patterns.

Solution Approach

The provided Python solution implements a commonly known algorithm for counting the number of '1' bits in the binary representation of an unsigned integer using bit manipulation.

Here are the key components of the implementation:

Bitwise AND Operator (&): The bitwise AND operator is used to perform the AND operation on each bit of the binary representations of two numbers. It is a fundamental operation used in the given solution to remove the rightmost '1' bit.
While Loop: The solution utilizes a while loop to iterate until the given number n is reduced to zero. The condition of the while loop while n: takes advantage of the fact that in Python, zero is considered False and all other integers are considered True. Thus, the loop continues as long as n has at least one '1' bit remaining.
Bit Manipulation Trick (n &= n - 1): This specific operation is used to clear the least significant '1' bit of the number n. In each iteration of the while loop, n is updated to n & (n - 1), which removes the rightmost '1' bit from n. This is the core step that reduces the value of n while also counting the number of '1' bits.
Counter Variable (ans): A counter variable ans is used to track the number of '1' bits. It is incremented by 1 for each iteration of the while loop, which corresponds to the removal of each '1' bit.

The combination of these elements leads to an elegant and efficient approach to solving the problem. The solution does not require any additional data structures, since the count is maintained in a single integer variable, and the input number n is manipulated in place to count the number of '1' bits.

The pattern used here is quite effective for dealing with common bit manipulation problems and is a good example of using bitwise operators to simplify complex operations. Since each operation potentially reduces n by eliminating a '1' bit, the number of iterations is equal to the number of '1' bits, making the algorithm run in O(k) time complexity, where k is the number of '1' bits in the binary representation of n.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider the unsigned integer 11, which has the binary representation 1011. Let's apply the algorithm step-by-step to calculate the Hamming weight.

We initialize the counter ans to zero. This will keep track of the number of '1' bits.
The binary representation of the integer 11 is 1011, and it's not zero, so we enter the while loop.
We calculate n-1. For n = 1011 (11 in decimal), n-1 would be 1010 (10 in decimal).
Then, we perform n &= n - 1, which is 1011 & 1010 resulting in 1010 (10 in decimal), thereby removing the last '1' bit.
We increment ans by one. ans is now 1.
n is now 1010 (10 in decimal), which is still not zero, so the while loop continues.
Again, n-1 is calculated to be 1001 (9 in decimal).
Performing n &= n - 1 now, which is 1010 & 1001, results in 1000 (8 in decimal), removing another '1'.
Increment ans by one again. ans is now 2.
n is now 1000 (8 in decimal), which is still not zero.
n-1 is 0111 (7 in decimal).
Performing n &= n - 1 again results in 1000 & 0111, which results in 0000 (0 in decimal).
We increment ans by one last time. ans is now 3.
Now, n is zero, so we exit the while loop.

After exiting the loop, ans is 3, which is the number of '1' bits in the binary representation of the unsigned integer 11 (1011). Thus, the Hamming weight of 11 is 3.

This technique minimizes the number of operations by ensuring that each iteration removes one '1' bit, leading to a time complexity that is linear with respect to the number of '1' bits in the binary representation.

Solution Implementation

1class Solution:
2    def hammingWeight(self, n: int) -> int:
3        # Initialize count of set bits to 0
4        count_of_set_bits = 0
5      
6        # Iterate until all bits are traversed
7        while n:
8          
9            # Perform bitwise AND operation between n and (n-1)
10            # This operation removes the rightmost set bit from n
11            n &= n - 1
12          
13            # Increment count of set bits
14            count_of_set_bits += 1
15      
16        # Return the total count of set bits in the integer
17        return count_of_set_bits
18

1public class Solution {
2    /**
3     * This method calculates the number of 1-bits in the binary representation of a number.
4     * Treats the input number as an unsigned value.
5     *
6     * @param n - The input integer (considered as unsigned) to count the 1-bits in.
7     * @return The number of 1s in the binary representation of n.
8     */
9    public int hammingWeight(int n) {
10        int onesCount = 0; // Store the count of 1-bits encountered
11      
12        // Use '!=0' in the condition to ensure we process all bits of n.
13        // Since Java does not support unsigned int natively, we interpret n as unsigned by comparing directly to 0.
14        while (n != 0) {
15            // Apply the bit manipulation trick n & (n - 1) which clears the least significant 1-bit in n.
16            n &= n - 1;
17          
18            // Increment the count of 1-bits for every 1-bit cleared by the operation above.
19            ++onesCount;
20        }
21      
22        return onesCount; // Return the total count of 1-bits found
23    }
24}
25

1class Solution {
2public:
3    // This function returns the number of '1' bits in the binary representation of the given unsigned integer.
4    int hammingWeight(uint32_t n) {
5        int count = 0;  // Initialize a counter for the '1' bits
6        while (n) {  // Continue until all bits are traversed
7            n &= n - 1;  // Clear the least significant '1' bit
8            ++count;  // Increment the counter by one
9        }
10        return count;  // Return the total count of '1' bits
11    }
12};
13

1/**
2 * Function to count the number of 1 bits in the binary representation of a positive integer.
3 * @param n - a positive integer
4 * @returns The number of 1's in the binary representation of n.
5 */
6function hammingWeight(n: number): number {
7    // Initialize a count for the number of 1 bits
8    let count: number = 0;
9
10    // Continue looping as long as n is not 0
11    while (n !== 0) {
12        // Apply bitwise AND between n and n-1, which flips the least significant 1 bit of n to 0
13        n &= n - 1;
14      
15        // Increment the count of 1 bits
16        count++;
17    }
18
19    // Return the final count of 1 bits in n
20    return count;
21}
22

Time and Space Complexity

The given Python code defines a function hammingWeight that calculates the number of 1s in the binary representation of a given integer n. The algorithm works by turning off the rightmost 1-bit of n at each step until n becomes 0.

Time Complexity

The time complexity of the algorithm is O(k), where k is the number of 1-bits in n. In the worst case, when n is a power of 2, k will be logarithmic in the value of n because there will be only one 1-bit. In the average case, it will be less than logarithmic since numbers typically have fewer than the maximum possible number of 1-bits. Therefore, in terms of n, the time complexity can be considered O(log n) because k will not exceed the number of bits in n, which is the logarithm of n.

Space Complexity

The space complexity of the algorithm is O(1) because it uses a fixed number of variables (ans and n) whose size does not depend on the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don't know