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;
}

5 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);
    }
    }

  3. Abhay Singh on October 15, 2016 at 3:13 pm said:

    This program is working fine..

    #include
    #include
    void main()
    {
    int i, j, k, num, count=1;
    printf(“Enter your number:\r\n”);
    scanf(“%d”, &num);
    if(num==1){
    printf(“Count of bits is 1\r\n”);
    return;
    }
    for(i=1; i>1)&1){
    count++;
    }
    j = j>>1;
    }
    }
    printf(“Count of bits are %d\r\n”,count+1);
    }

    • Abhay Singh on October 15, 2016 at 3:16 pm said:

      This is working fine for me.. Previous one got updated wrongly on websites..

      #include
      #include
      void main()
      {
      int i, j, k, num, count=1;
      printf(“Enter your number:\r\n”);
      scanf(“%d”, &num);
      if(num==1){
      printf(“Count of bits is 1\r\n”);
      return;
      }
      for(i=1; i>1)&1){
      count++;
      }
      j = j>>1;
      }
      }
      printf(“Count of bits are %d\r\n”,count+1);
      }

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