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

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

  4. nani on July 24, 2017 at 4:33 pm said:

    This code also works fine
    #include
    void main()
    {
    int n,i=1,d,c;
    static int count=0;
    clrscr();
    printf(“enter no. upto which set bits r to b found\n”);
    scanf(“%d”,&n);
    while(i=1)
    {
    d=c%2;
    if(d==1)
    count++;
    c=c/2;
    }
    i++;
    }
    printf(“no. of set bits:&d\n”,count);
    getch();
    }

  5. nani on July 24, 2017 at 4:35 pm said:

    my program is also getting updated wrongly though i type it properly

  6. riyuzaki on November 27, 2017 at 1:50 am said:

    #include
    int main()
    {
    int a,b,i,sum=0;
    scanf(“%d”,&a);
    while(a)
    {
    sum=sum+(a&1);
    a=a>>1;
    }
    printf(“%d”,sum);
    return 0;
    }

  7. #include

    int main()
    {
    int num,i,count=0;
    printf(“enter the number\n”);
    scanf(“%d”,&num);
    for(i=1;i>1;}

    }
    printf(“%d”,count);

    return 0;
    }

  8. Lavanya on July 9, 2018 at 9:18 pm said:

    #include

    int main()
    {
    int n,r,c=0,i,x;
    scanf(“%d”,&n);
    for(i=1;i<=n;i++)
    {
    x=i;
    while(x!=0)
    {
    r=x%2;
    if(r==1)
    c=c+1;
    x=x/2;
    }

    }
    printf("%d",c);
    return 0;
    }

  9. Ankush Batra on November 15, 2018 at 10:59 pm said:

    #include
    int print_set_bits(int i, int set_bits);

    int main()
    {
    int n, i;
    static int set_bits;
    printf(“Enter the number: “);
    scanf(“%d”, &n);

    for(i=1; i=0; bits–)
    {
    bit = ((i >> bits) & 1 == 1) ? 1 : 0;
    if(bit == 1)
    set_bits++;
    }
    return set_bits;
    }

  10. DEIVENDRAN CHINNACHAMY on November 7, 2020 at 9:03 am said:

    int main()
    {
    int val,count=0;
    scanf(“%d”,&val);
    do
    {
    count+=(val&1);
    } while(val=val>>1);
    printf(“%d”,count);
    return 0;
    }

  11. Sandeep Jeevan on January 14, 2021 at 10:48 am said:

    Program will fail in case of signed number

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