DSA | Day 14 of Google Interview Preparation Journey | Challenge 16: 191. Number of 1 Bits

Introduction

Counting the number of set bits (1s) in the binary representation of an integer is a classic problem(#191 on LeetCode ) in computer science. Known as the Hamming Weight problem, it is both simple and powerful, testing your understanding of bitwise operations. In this article, we’ll explore the problem, break down an optimized solution, and analyze its efficiency.

Problem Statement

Given a positive integer n, write a function that returns the number of set bits in its binary representation. This is also known as the Hamming weight.

Example 1:

Input:

n = 11

Output:

3

Explanation: The binary representation of 11 is 1011, which contains three set bits.

Example 2:

Input:

n = 128

Output:

1

Explanation: The binary representation of 128 is 10000000, which contains one set bit.

Example 3:

Input:

n = 2147483645

Output:

30

Explanation: The binary representation of 2147483645 is 1111111111111111111111111111101, which contains thirty set bits.

Constraints:

• 1≤n≤231−11 \leq n \leq 2^{31} — 1

Approach and Explanation

The key to solving this problem efficiently lies in understanding the bitwise AND operation. Specifically, we can leverage the property that n & (n - 1) clears the lowest set bit of n. By repeatedly applying this operation, we can count the number of set bits in O(k)O(k), where kk is the number of set bits.

Step-by-Step Explanation:

Initialize a Counter: Start with a counter variable ans set to 0.

Iterate While n is Non-Zero: As long as n is not zero, perform the following steps:

• Update n using the operation n &= (n - 1). This clears the lowest set bit in n.
• Increment the counter ans by 1.

Return the Counter: Once n becomes zero, the counter will hold the number of set bits.

Code Implementation

Here is the Python implementation of the solution:

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            n &= (n - 1)  # Clear the lowest set bit
            ans += 1      # Increment the count of set bits
        return ans

Complexity Analysis

• Time Complexity: O(k)O(k), where kk is the number of set bits in n. Each iteration of the loop removes one set bit, and the loop runs kk times.
• Space Complexity: O(1)O(1), as we use only a constant amount of extra space.

Example Walkthrough

Example 1:

Input:

n = 11

Execution:

1. Binary representation: 1011.
2. Iteration 1: n = 1011, n &= (n - 1) → n = 1010, ans = 1.
3. Iteration 2: n = 1010, n &= (n - 1) → n = 1000, ans = 2.
4. Iteration 3: n = 1000, n &= (n - 1) → n = 0, ans = 3.

Output:

3

Example 2:

Input:

n = 128

Execution:

1. Binary representation: 10000000.
2. Iteration 1: n = 10000000, n &= (n - 1) → n = 0, ans = 1.

Output:

1

Example 3:

Input:

n = 2147483645

Execution:

1. Binary representation: 1111111111111111111111111111101.
2. Iterate 30 times, clearing one set bit at a time until n = 0.

Output:

30

Real-World Applications

1. Networking: Hamming weight is used in error detection and correction algorithms.
2. Cryptography: It is often employed in algorithms for encryption and hashing.
3. Graphics Processing: Bit manipulation is frequently used in rendering and image processing.
4. Data Compression: Efficiently counting set bits can aid in encoding schemes.

Conclusion

The Hamming Weight problem is a straightforward yet powerful example of how bitwise operations can simplify complex tasks. By understanding and leveraging the n & (n - 1) operation, we achieve an elegant and efficient solution.

For the full implementation and further exploration, check out my submissions:

• LeetCode Submission: Link
• GitHub Repository: Link