Count Total Set Bits in All Numbers From 1 to N

Problem:

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

Examples:
Input: n = 3
Output: 4

Input: n = 6
Output: 9

Input: n = 7
Output: 12

Input: n = 8
Output: 13

Solution:

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
    #include

    int countBitSet(unsigned int );
    void main()
    {
    unsigned int x,count;
    printf(“Enter interger value: “);
    scanf(“%d”,&x);
    countBitSet(x);
    }

    int countBitSet(unsigned int n)
    {
    unsigned int i,val,count=0;
    val=n;
    for(i=0;i>1;
    }
    printf(“%d intiger value have %d bit set\n”,n,count);
    if(–n)
    {
    countBitSet(n);
    }
    }

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