Leetcode 191. Number of 1 Bits

Problem Explanation

This problem is about bitwise operations, specifically, it's about counting the number of 1 bits in a 32-bit integer. '1' bits are also known as the Hamming weight. If you are familiar with how binary numbers work, you'll know that each binary digit (bit) in a number is either 0 or 1.

A binary number is just a representation of a decimal number converted into base 2. For example, the decimal number 5 is represented as 101 in binary, which means two '1' bits, while the number 3 in binary is 11 which means two '1' bits as well.

To solve this problem, we need a function that takes an integer as an input, converts it to binary, and counts the number of '1' bits.

The solution uses a simple approach by iterating through each bit of the number, shifting the bits to the right one by one, and checking if the least significant bit is 1. This can be done using bitwise AND operation. The process is repeated for all 32 bits of the input number.

Let's walk through example 1: Input: 00000000000000000000000000001011 (which is 11 in decimal)

  • At the first iteration, we do (11 >> 0) & 1 = 1, so we increment our count
  • At the second iteration, we do (11 >> 1) & 1 = 1, so we increment our count again
  • At the third iteration, we do (11 >> 2) & 1 = 0, so we don't increment our count
  • At the fourth iteration, we do (11 >> 3) & 1 = 1, so we increment our count for the last time
  • The rest of the iterations will yield 0 Finally, the output is 3, which is the correct count of '1' bits.

Python Solution

1
2python
3class Solution:
4    def hammingWeight(self, n: int) -> int:
5        count = 0
6        for _ in range(32):
7            count += n & 1
8            n >>= 1
9        return count

This python solution mimics the same bits shifting process in the C++ solution.

Java Solution

1
2java
3public class Solution {
4    public int hammingWeight(int n) {
5        int count = 0;
6        for (int i = 0; i < 32; i++) {
7            if ((n & 1) == 1) {
8                count++;
9            }
10            n = n >> 1;
11        }
12        return count;
13    }
14}

This Java solution also uses the same logic of bit shifting and counting the number of '1' bits.

Javascript Solution

1
2javascript
3var hammingWeight = function(n) {
4    let count = 0;
5    for(let i = 0; i < 32; i++){
6        if((n & 1) === 1){
7            count++;
8        }
9        n = n >>> 1;
10    }
11    return count;
12};

In the javascript solution, we use the triple right shift operator (>>>) which is the unsigned right shift operator to ensure it works for negative numbers.

C++ Solution

1
2c++
3class Solution {
4public:
5    int hammingWeight(uint32_t n) {
6        int count = 0;
7        for (int i = 0; i < 32; ++i) {
8            if ((n >> i) & 1) {
9                ++count;
10            }
11        }
12        return count;
13    }  
14};

The provided solution is in C++, it works by shifting the bits of the input number to the right one by one, and checks if the least significant bit is 1 using bitwise AND operation.

C# Solution

1
2csharp
3public class Solution {
4    public int HammingWeight(uint n) {
5        int count = 0;
6        for(int i = 0; i < 32; i++){
7            if((n & 1) == 1){
8                count++;
9            }
10            n = n >> 1;
11        }
12        return count;
13    }
14}

The C# solution is quite straightforward, it follows the same logic as the other solutions of performing bitwise operations to evaluate the number of '1' bits in the binary representation of the input number.## Ruby Solution

1
2ruby
3def hamming_weight(n)
4    count = 0
5    32.times do
6        count += n & 1
7        n >>= 1
8    end
9    count
10end

This Ruby solution works similar to the solutions in other languages. It makes use of bitwise operations to analyze the binary form of the input integer, counting the number of '1' bits.

Swift Solution

1
2swift
3class Solution {
4    func hammingWeight(n: UInt) -> Int{
5        var count = 0
6        for _ in 0..<32{
7            if n & 1 == 1{
8                count += 1
9            }
10            n = n >> 1
11        }
12        return count
13    }
14}

This Swift solution implements similar logic to our other solutions, performing bitwise shifting and checking if the least significant bit is 1.

Rust Solution

1
2rust
3impl Solution {
4    fn hammingWeight(n: u32) -> i32 {
5        let mut count = 0;
6        let mut n = n;
7        for _ in 0..32{
8            count += n & 1;
9            n = n >> 1;
10        }
11        count as i32
12    }
13}

In the Rust solution, we adopt the same method of bitwise operation to check and count the 1 bits in the binary representation of the given number.

In conclusion, all of these solutions use the same fundamental approach to solve this problem. They iterate over the bits of the number and use bitwise operations to check the value of each bit and count the number of 1 bits. By iterating 32 times, they ensure that they check all bits of the 32-bit input integer.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫