[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
12public 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
3public 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
8public 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
12public 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
9public 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
3public 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. 😉😃💗