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 fromn
. - Increment
ans
by one after each bit-removal operation. - Once
n
becomes 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.
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 loopwhile n:
takes advantage of the fact that in Python, zero is consideredFalse
and all other integers are consideredTrue
. Thus, the loop continues as long asn
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 numbern
. In each iteration of the while loop,n
is updated ton & (n - 1)
, which removes the rightmost '1' bit fromn
. This is the core step that reduces the value ofn
while also counting the number of '1' bits. -
Counter Variable (
ans
): A counter variableans
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 EvaluatorExample 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
. Forn = 1011
(11 in decimal),n-1
would be1010
(10 in decimal). - Then, we perform
n &= n - 1
, which is1011 & 1010
resulting in1010
(10 in decimal), thereby removing the last '1' bit. - We increment
ans
by one.ans
is now 1. n
is now1010
(10 in decimal), which is still not zero, so the while loop continues.- Again,
n-1
is calculated to be1001
(9 in decimal). - Performing
n &= n - 1
now, which is1010 & 1001
, results in1000
(8 in decimal), removing another '1'. - Increment
ans
by one again.ans
is now 2. n
is now1000
(8 in decimal), which is still not zero.n-1
is0111
(7 in decimal).- Performing
n &= n - 1
again results in1000 & 0111
, which results in0000
(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.
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
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
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
Want a Structured Path to Master System Design Too? Donāt Miss This!