191. Number of 1 Bits
The number of 1 bits, also known as the Hamming weight, is a fundamental concept in computer science and programming. It refers to the count of 1-bits in a binary representation of a number. In this article, we will explore the number of 1 bits problem, its significance, and various approaches to solve it.
Problem Statement
Given an integer n, write a function to return the number of 1 bits in the binary representation of n.
Example
For example, if n = 9, the binary representation of n is 1001, which has 2 1-bits. Therefore, the function should return 2.
Approaches
There are several approaches to solve the number of 1 bits problem. Here are a few:
1. Bitwise Operations
One way to solve this problem is to use bitwise operations. We can use the bitwise AND operator (&) to check if the least significant bit of n is 1. If it is, we increment a counter. Then, we use the bitwise right shift operator (>>) to shift the bits of n to the right by 1 position. We repeat this process until n becomes 0.
Here is an example implementation in C:
int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>= 1;
}
return count;
}
2. Brian Kernighan's Algorithm
Another approach is to use Brian Kernighan's algorithm, which is an optimized method for counting the number of 1 bits in a binary number. The algorithm works by iterating through the bits of n and flipping the least significant 1 bit in each iteration.
Here is an example implementation in C:
int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= n - 1;
count++;
}
return count;
}
3. Lookup Table
A third approach is to use a lookup table to store the number of 1 bits for each possible binary number. This approach is particularly useful when we need to perform this operation frequently.
Here is an example implementation in C:
int hammingWeight(int n) {
static int lookup[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
// ...
};
return lookup[n & 0xFF] + lookup[(n >> 8) & 0xFF] + lookup[(n >> 16) & 0xFF] + lookup[(n >> 24) & 0xFF];
}
Conclusion
In conclusion, the number of 1 bits problem is a fundamental concept in computer science and programming. We have explored various approaches to solve this problem, including bitwise operations, Brian Kernighan's algorithm, and using a lookup table. Each approach has its own advantages and disadvantages, and the choice of approach depends on the specific requirements of the problem.
