Count total set bits in all numbers from 1 to n [Amazon ]

#include <stdio.h>

 

int main() {

//code

int t,n,i,ans;

int powerOfTwo,dividend,m;

int arr[30];

arr[0]=1;

arr[1]=2;

arr[2]=5;

arr[3]=13;

int gapOfNumber=8;

for(i=4;i<30;i++)

{

arr[i]=(arr[i-1])*2+(gapOfNumber-1);

gapOfNumber=gapOfNumber*2;

}

scanf("%d",&t);

while(t--)

{

scanf("%d",&n);

ans=0;

while(n)

{

m=n;

dividend=1;

powerOfTwo=0;

while(m)

{

if(m/2)

{

powerOfTwo+=1;

dividend*=2;

m=m/2;

}

else

break;

}

n=n%dividend;

//printf("%d = div\npowerOfTwo=%d\n",n,powerOfTwo);

ans+=(arr[powerOfTwo]+n);

}

printf("%d\n",ans);

}

return 0;

}