kamalbanga
10/21/2013 - 2:57 PM

## Total no. of 1's in 2's complement representation between A and B, inclusive. Hackerrank's "2's complement" problem.

Total no. of 1's in 2's complement representation between A and B, inclusive. Hackerrank's "2's complement" problem.

``````#include <stdio.h>
#include <math.h>
#include <limits.h>

unsigned int prevTwo(unsigned int x) // bit twiddling
{
unsigned int y = x;
x--;
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x++;
if(x != y)
x = x >> 1;
return x;
}

long long countOneZero(int n)
{
if(n == 0 || n == 1)
return n;
int k = prevTwo((unsigned int)n);
int p = 1, k2 = k;
while((k>>1) != 1)
{
k = k>>1;
p++;
}
return (long long)pow((double)2, p-1)*p + (n-k2+1) + countOneZero(n-k2);
}

long long countOnes(int a, int b)
{
if(a <= 0)
a = 1;
return countOneZero(b) - countOneZero(a-1);
}

int main()
{
int a, b, flag;
int t, T;
scanf("%d",&T);
for(t=0;t<T;t++)
{
flag = 0;
scanf("%d %d", &a, &b);
if(a == 0 && b == 0)
{
printf("%d\n",0);
continue;
}
if(a == 0)
a++;
if(b == 0)
b--;
if(a == INT_MIN && b == INT_MIN)
{
printf("%d\n",1);
continue;
}
if(a == INT_MIN)
{
flag = 1;
a++;
}
if(a < 0 && b < 0)
{
a = -a;
b = -b;
printf("%lld\n",(long long)32*(a-b+1)-countOnes(b-1,a-1) + flag);
}
else if(a > 0 && b > 0)
{
printf("%lld\n",countOnes(a,b));
}
else
{
a = -a;
printf("%lld\n",(long long)32*a-countOnes(1,a-1)+countOnes(1,b) + flag);
}
}
return 0;
}``````