[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$.

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}$.

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.

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.

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).

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.

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. 😉😃💗