191. Number of 1 Bits

Problem Statement

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

What we have to do: Given an integer, find number of 1’s from the binary representation of the given integer.

Solution

There are 3 methods to solve this problem:

1. The Brute-force way
2. Brian Kernighan’s Algorithm
3. Simple and standard way

Code Repo: https://github.com/mrunalnshah/Algorithms/tree/main/00_Bits-and-Computers/Arena/0191_Number-of-1-Bits

Python Solution

Python Solution: https://github.com/mrunalnshah/Algorithms/tree/main/00_Bits-and-Computers/Arena/0191_Number-of-1-Bits/Python

Method 1: The Brute-force way Code

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
 
        while n > 0:
            if n & 1:
                count += 1
            n = n >> 1
 
        return count

Method 2: Brian Kernighan’s Algorithm Code

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0  
 
        while n:
            n &= (n - 1)
            count += 1
        return count

Brian Kernighan’s Algorithm Explanation:

Method 3: Simple and Standard Way Code

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count('1')