Count total bit flips when counting from 0 to n

Updated

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.

Comment
Mithlesh Upadhyay Published 20 Nov 2026 · 2 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials