Given an integer n we have to calculate the no of times the bits flips in binary representation form 0 to n.
Examples :
Input : n = 5 Output : 8 Explanation : 000 001 010 011 100 101 no of bits flip = 1 + 2 + 1 + 3 + 1 = 8 Input : n = 11 Output : 19
Naive Approach :
run a for loop from 0 to n and check no of bits flips in two consecutive numbers inn this the complexity will be O(nlogn). Efficient Approach : Let us start by calculating the result for n = \(2^k\) it can be quickly done by calculating the results for each bits separately and summing these up. For i-th bit, the result is equal to \(2^k/2^i\) as this bit is different in d-1 and d iff d is a multiple of \(2^i\) . Summing these up we get that the result for n = \(2^k\) is equal to \(2^{k+1}-1 = 2n-1\) . How to compute the answer for arbitrary n? Let us denote b1 > b2 > … >bk as set bits in the binary representation of n. I claim that the answer is equal to the sum of answers for \(2^{b1}\) , \(2^{b2}\) , …, \(2^{bk}\) . Why? We can compute results for intervals \([0,2^{b1}]\) , \([2^{b1}, 2^{b1} + 2^{b2}]\) , \([2^{b1} + 2^{b2}, 2^{b1} + 2^{b2} + 2^{b3}]\) . We can notice that the result for interval \([s,s+2^i]\) where s is a multiple of \(2^i\) , is equal to the answer for \([0,2^i]\) so we can just compute the results for intervals \([0,2^{b1}]\) , \([0,2^{b2}]\) , …., \([0,2^{bk}]\) This allows us to compute the answer for arbitrary n in O(logn) – just iterate over all bits b and add \(2^{b+1}-1\) if b is set. Equivalently we can just write down 2n – #bits set as the answer.
Implementation :
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
// function for counting no of time bits filp
int count(int n)
{
int ans = 0;
for (int i = 0; i < 60; i++)
{
// check if bit is set then add it to the ans
if (n & (1LL << i))
ans = ans + (1LL << (i + 1)) - 1;
}
return ans;
}
// Driver Code
int main()
{
int n = 5;
cout << count(n) <<endl;
return 0;
}
This solution take O(logn) time.