[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 nn is 11.

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)O(k).
  • Space Complexity: O(1)O(1).

API

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

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

Analysis

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

Divide and Conquer

In fact, the API Integer.bitCount\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)O(logk).
  • Space Complexity: O(1)O(1).

LowBit

We can get the Low Bit 11 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)O(k).
  • Space Complexity: O(1)O(1).

BitSet

We can change the lowest 11 of the binary bits of nn to 00 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)O(logn).
  • Space Complexity: O(1)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)O(logn).
  • Space Complexity: O(1)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. 😉😃💗