Challenge 1: Count Set Bits
Explore how to count set bits in an integer by applying the bitwise AND operator. Understand the binary representation of numbers and implement efficient solutions with bit manipulation. This lesson helps you develop skills to optimize code performance while solving common coding interview challenges.
Introduction
Let’s see how we can count the set bits using the AND operator.
What are set-bits?
1 = set-bit
0 = unset-bit
For example:
Input: 5
Output: 0101 (in binary)
There are two set bits are two in the above example, as we have two 1’s in the binary representation.
Problem statement
Write a program to count set bits of an integer.
Input: 125
Output: 6
Explanation: Input has six 1’s or set-bits so the output will be 6.
Basic solution
In this program, a while-loop is iterated until the expression number > 0 is evaluated to 0 (false).
Let’s see the iterations for number = 125.
Iterations
-
After the first iteration,
number(125)will be divided by2, its value will be62, and the count incremented to1. -
After the second iteration, the value of ...