[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 is .
1 | public int hammingWeight(int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
API
Use API: .
1 | public static int hammingWeight(int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Divide and Conquer
In fact, the API is use the divide and conquer method.
1 | public int hammingWeight(int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
LowBit
We can get the Low Bit by x & -x.
1 | public int hammingWeight_lowbit(int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
BitSet
We can change the lowest of the binary bits of to by using x &= (x - 1).
1 | public int hammingWeight_log(int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Recursion
A recursion version of the previous method.
1 | public int hammingWeight(int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
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. 😉😃💗