Given a number N which is a power of 2. Calculate total number of set bits from 1 to N-1.
Examples :
Input : N = 8
Output : 12
Explanation : N – 1 = 7
000 : 0
001 : 1
010 : 2
011 : 3
100 : 4
101 : 5
110 : 6
111 : 7
Total set bits = 0 + 1 + 1 + 2 + 1 + 2 + 2 + 3 = 12
Thus, total number of set bits from 1 to 7 is 12.
Input : N = 4
Output : 4
Explanation : N – 1 = 3
00 : 0
01 : 1
10 : 2
11 : 3
Total set bits = 0 + 1 + 1 + 2 = 4.
Therefore, Output is 4
Approach :
Follow the steps below to solve the problem
- Since, it is given that N is an power of 2. Therefore we can easily calculate exponent of 2 using the formula-
int x = log2( N );
For eg-
Let N=32
Therefore, using the properties of log –
x = log2( 32 ) = log2( 25 ) = 5
- Now, we observe that in each column of bits, half of the bits are set and half are unset.
For eg –
Let N = 8. Therefore, x = 3
000 : 0
001 : 1
010 : 2
011 : 3
100 : 4
101 : 5
110 : 6
111 : 7
Using the concept, total number of set bits = x * 2(x-1)
Below is the implementation of this method :
// C++ program to calculate total no. of
// set bits from 1 to N-1
#include <iostream>
#include <math.h>
using namespace std;
// Driver code
int main()
{
int N = 8;
int x = log2(N);
int result = x * pow(2, x-1);
cout << result;
return 0;
}
Output :
12
