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