Teaching Kids Programming – Compute the Number of Set Bits in an Integer

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given an integer n, return the number of 1 bits in n.

Constraints
0 ≤ n < 2 ** 31
Example 1
Input
n = 0
Output
0
Example 2
Input
n = 1
Output
1
Example 3
Input
n = 2
Output
1
Explanation
2 is 10 in binary.
Example 4
Input
n = 3
Output
2
Explanation
3 is 11 in binary.
Example 5
Input
n = 4
Output
1
Explanation
4 is 100 in binary.

Number of 1’s bits using bit by bit

We can use n & 1 to get the rightmost bit, then we shift the integer one position to the right until it is zero.

1
2
3
4
5
6
7

class Solution:
    def numberOfSetBits(self, n):
        ans = 0
        while n > 0:
            ans += n & 1
            n >>= 1
        return ans

class Solution:
    def numberOfSetBits(self, n):
        ans = 0
        while n > 0:
            ans += n & 1
            n >>= 1
        return ans

The complexity is O(1) as maximum 32 loops.

Sum Set Bits by Removing Rightmost 1’s

We can use n & (n – 1) to remove the rightmost 1 – and increment 1 when we get rid of each 1.

1
2
3
4
5
6
7

class Solution:
    def numberOfSetBits(self, n):
        ans = 0
        while n > 0:
            ans += 1
            n &= (n - 1)
        return ans

class Solution:
    def numberOfSetBits(self, n):
        ans = 0
        while n > 0:
            ans += 1
            n &= (n - 1)
        return ans

The complexity is O(1) as maximum there will be 32 One’s.

We can also use the bin() function in Python to convert integer to binary – and count ‘1’:

1
2
3
4

class Solution:
    def solve(self, n):
        s = bin(n)[2:]
        return s.count("1")

class Solution:
    def solve(self, n):
        s = bin(n)[2:]
        return s.count("1")

–EOF (The Ultimate Computing & Technology Blog) —