[LeetCode][191. Number of 1 Bits] 6 Approaches: Cycle, API, Divide and Conquer, Low Bit, Bit Set, Recursion

By Long Luo

This article is the solution 6 Approaches: Cycle, API, Divide and Conquer, Low Bit, Bit Set, Recursion of Problem 191. Number of 1 Bits.

Here shows 6 Approaches to slove this problem: Cycle, Divide and Conquer, LowBit, Bit Set, Recursion.

Brute Force: Cycle

Juse use a Loop to check if each bit of the binary bits of the given integer \(n\) is \(1\).

1
2
3
4
5
6
7
8
9
10
11
12
public int hammingWeight(int n) {
int cnt = 0;
for (int i = 0; i < 32 && n != 0; i++) {
if ((n & 0x01) == 1) {
cnt++;
}

n = n >>> 1;
}

return cnt;
}

Analysis

  • Time Complexity: \(O(k)\).
  • Space Complexity: \(O(1)\).

API

Use API: \(\texttt{Integer.bitCount}\).

1
2
3
public static int hammingWeight(int n) {
return Integer.bitCount(n);
}

Analysis

  • Time Complexity: \(O(logk)\).
  • Space Complexity: \(O(1)\).

Divide and Conquer

In fact, the API \(\texttt{Integer.bitCount}\) is use the divide and conquer method.

1
2
3
4
5
6
7
8
public int hammingWeight(int n) {
n = (n & 0x55555555) + ((n >>> 1) & 0x55555555);
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
n = (n & 0x0f0f0f0f) + ((n >>> 4) & 0x0f0f0f0f);
n = (n & 0x00ff00ff) + ((n >>> 8) & 0x00ff00ff);
n = (n & 0x0000ffff) + ((n >>> 16) & 0x0000ffff);
return n;
}

Analysis

  • Time Complexity: \(O(logk)\).
  • Space Complexity: \(O(1)\).

LowBit

We can get the Low Bit \(1\) by \(x & -x\).

1
2
3
4
5
6
7
8
9
10
11
12
public int hammingWeight_lowbit(int n) {
int ans = 0;
for (int i = n; i != 0; i -= lowbit(i)) {
ans++;
}

return ans;
}

public int lowbit(int n) {
return n & -n;
}

Analysis

  • Time Complexity: \(O(k)\).
  • Space Complexity: \(O(1)\).

BitSet

We can change the lowest \(1\) of the binary bits of \(n\) to \(0\) by using \(x &= (x - 1)\).

1
2
3
4
5
6
7
8
9
public int hammingWeight_log(int n) {
int cnt = 0;
while (n != 0) {
n = n & (n - 1);
cnt++;
}

return cnt;
}

Analysis

  • Time Complexity: \(O(logn)\).
  • Space Complexity: \(O(1)\).

Recursion

A recursion version of the previous method.

1
2
3
public int hammingWeight(int n) {
return n == 0 ? 0 : 1 + hammingWeight(n & (n - 1));
}

Analysis

  • Time Complexity: \(O(logn)\).
  • Space Complexity: \(O(1)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗