Algorithm
Problem Name: 191. Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
Note:
- 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.
- In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer.
-3.
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.
Constraints:
- The input must be a binary string of length
32.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int helper(uint32_t n, uint32_t b) {
uint64_t k;
if (n == 0) return 0;
k = ((uint64_t)1 << b) - 1;
if (n == k) return b;
b >>= 1;
return helper(n >> b, b) +
helper(n & ((1 << b) - 1), b);
}
int hammingWeight(uint32_t n) {
#if 0
int c = 0;
while (n) {
c ++;
n &= (n - 1);
}
return c;
#else
return helper(n, 32);
#endif
}
Input
n = 00000000000000000000000000001011
Output
3
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while(n){
if(n & 1) count++;
n >>= 1;
}
return count;
}
};
Input
n = 00000000000000000000000000001011
Output
3
#3 Code Example with Java Programming
Code -
Java Programming
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int bits = 0;
int mask = 1;
for (int i = 0; i < 32; i++) {
if ((n & mask) != 0) {
bits++;
}
mask <<= 1;
}
return bits;
}
}
Input
n = 00000000000000000000000010000000
Output
1
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const hammingWeight = function(n) {
let res = 0
while(n > 0) {
if(n & 1) res++
n = n >>> 1
}
return res
};
Input
n = 00000000000000000000000010000000
Output
1
#5 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0191_NumberOf1Bits
{
public int HammingWeight(uint n)
{
var num = 0;
while (n > 0)
{
n &= n - 1;
num++;
}
return num;
}
}
}
Input
n = 11111111111111111111111111111101
Output
31