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
ansto zero. This will be used to track the number of '1' bits. - Use a while loop to iterate as long as
nis not zero. - Inside the loop, perform the operation
n &= n - 1, which removes the rightmost '1' bit fromn. - Increment
ansby one after each bit-removal operation. - Once
nbecomes zero, which means all '1' bits have been removed, returnans, 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.
Which algorithm should you use to find a node that is close to the root of the tree?
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
nis reduced to zero. The condition of the while loopwhile n:takes advantage of the fact that in Python, zero is consideredFalseand all other integers are consideredTrue. Thus, the loop continues as long asnhas 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 numbern. In each iteration of the while loop,nis updated ton & (n - 1), which removes the rightmost '1' bit fromn. This is the core step that reduces the value ofnwhile also counting the number of '1' bits. -
Counter Variable (
ans): A counter variableansis 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.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
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
ansto 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. Forn = 1011(11 in decimal),n-1would be1010(10 in decimal). - Then, we perform
n &= n - 1, which is1011 & 1010resulting in1010(10 in decimal), thereby removing the last '1' bit. - We increment
ansby one.ansis now 1. nis now1010(10 in decimal), which is still not zero, so the while loop continues.- Again,
n-1is calculated to be1001(9 in decimal). - Performing
n &= n - 1now, which is1010 & 1001, results in1000(8 in decimal), removing another '1'. - Increment
ansby one again.ansis now 2. nis now1000(8 in decimal), which is still not zero.n-1is0111(7 in decimal).- Performing
n &= n - 1again results in1000 & 0111, which results in0000(0 in decimal). - We increment
ansby one last time.ansis now 3. - Now,
nis 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
181public 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}
251class 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};
131/**
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}
22What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
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.
Breadth first search can be used to find the shortest path between two nodes in a directed graph.
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.