Write an efficient program to count number of 1s in binary representation of an integer.
Input : n = 64
Output : 1
Binary representation of 64 is 1000000 and has 1 set bit
Input : n = 13
Output : 3
Binary representation of 13 is 1101 and has 3 set bits
Set bits in a binary number is represented by 1. So, the digit 1 is known as set bit in the terms of the computer.
Unset bits in a binary number is represented by 0. So, the digit 0 is known as unset bit in the terms of the computer.
In this below C++ Program, we are reading the unsigned integer using 'n' variable. Using while loop count the number of bits set to one using bitwise operations.
If condition statement is used to check the value which copies a bit to the result if it exists in both operands using Binary AND operator is not equal to 0. If the condition is true, then execute the statement and increment the number of bits set to 1 using count variable.
Using Binary Right Shift Operator, the left operand's value is moved right by the number of bits specified by the right operands and assign the value to 'n' variable. Hence we are displaying the output of the program. Print the count of the number of bits set to one using bitwise operations.
//C++ program for finding the number of set bits
using namespace std;
int countSetBits(int n)
cout<<"Number of Set bits in "<<n<<" is "<<countSetBits(n);
Number of Set bits in 64 is 1
Number of Set bits in 15 is 4
Time Complexity of this Approach is O(n)
Space Complexity of this Approach is O(1)