[C++] Leetcode 191. Number of 1 Bits (Hint, Solution)

Problem

https://leetcode.com/problems/number-of-1-bits/

Number of 1 Bits - LeetCode

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

 

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.

Example 2:

Input: n = 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.

Example 3:

Input: n = 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

 

Constraints:

• The input must be a binary string of length 32.

 

Follow up: If this function is called many times, how would you optimize it?

 

 

 

Hint

Try using Bit Manipulation.

 

 

 

Solution

The basic way to convert decimal to binary is repeating below steps until n becomes 0.
1. Getting a remainder(1 or 0).
2. Dividing number by 2.

Goal is to count the number of 1, so we'll count when remainder is 1.

 

 

 

Code

Simple

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int answer = 0;
        while (n != 0) {
            if (n % 2 == 1) {
                answer++;
                n -= 1;
            }
            n /= 2;
        }

        return answer;
    }
};

Or we can use bitset.

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int answer = 0;
        bitset<32> nBit = bitset<32>(n);
        for (int i=0; i<32; i++)
            if (nBit[i]) answer++;

        return answer;
    }
};

Shorter version with Bit Manipulation is below.

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int answer = 0;
        while (n != 0){
            n &= n-1;
            answer++;
        }

        return answer;
    }
};

 

Whole Code with Test Case

// https://leetcode.com/problems/number-of-1-bits/
#include <iostream>
#include <bitset>

using namespace std;

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int answer = 0;
        while (n != 0){
            n &= n-1;
            answer++;
        }

        return answer;
    }
};

int main() {
    Solution s = Solution();
    cout << endl << s.hammingWeight(11) << endl;

    return 0;
}

 

 

 

Complexity

Time

Time complexity will be O(log n).

 

Space

Space complexity will be O(1).

 

 

 

Best Solution (Pinned)

 

 

 

Overall