算法 Java Leetcode

Return the number of ‘1’ bits

Question

Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).
See it on Leetcode

1
2
3
4
For example,
the 32-bit integer '11' has binary representation - 
00000000000000000000000000001011,
so it should return 3.

Hint

  1. It should use bit manipulation.
  2. Integer.bitCount(<int>) also helps.

Solution in Loop and Flip

  • java
1
2
3
4
5
6
7
8
9
10
11
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;
}

Solution in Bit Manipulation Trick

AND-ing N and N-1 flips the least-significant 11-bit to 0AND-ing N and N-1 flips the least-significant 11-bit to 0
  • java
1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
    int sum = 0;
    while (n != 0) {
        sum++;
        n &= (n - 1);
    }
    return sum;
}

Solution in CSharp with one single line

  • cs
1
2
3
4
5
public class Solution {
    public int HammingWeight(uint n) {
        return Convert.ToString(n,2).Replace("0","").Length;
    }
}

Solution in Integer.bitCount()

  • java
1
2
3
4
5
public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}