Count Total Set Bits in All Numbers From 1 to N


Given a positive integer n, count the total number of set bits in binary representation of all numbers from 1 to n.

Input: n = 3
Output: 4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13


The solution is to run a loop from 1 to n and sum the count of set bits in all numbers from 1 to n.

int countSetBits(unsigned int n)
  unsigned int c; // the total bits set in n
  for (c = 0; n; n >>= 1)
    c += n & 1;
  return c;

2 Thoughts on “Count Total Set Bits in All Numbers From 1 to N

  1. Amritesh on August 25, 2016 at 12:52 am said:

    Can you also share a C program on how to toggle alternate bits of an integer using bitwise operators.

  2. #include

    int countBitSet(unsigned int );
    void main()
    unsigned int x,count;
    printf(“Enter interger value: “);

    int countBitSet(unsigned int n)
    unsigned int i,val,count=0;
    printf(“%d intiger value have %d bit set\n”,n,count);

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation