Codefest

Problem 3:No Bitwise

Time limit: 2 secs

For any given value of x, consider the following code snippet:

		
    a=(( (x | (x-1)) + 1 ) & x);
    b =a^x;
    b = b - ((b >> 1) & 1431655765);
    b = (b & 858993459) + ((b >> 2) & 858993459);
    c = ((b + (b >> 4) & 252645135) * 16843009) >> 24;
    printf("%d\n",c);

Input :

First line contains integer t, number of test cases.
Next t lines contains an integer n.

Output :

t lines each containing an integer.

Constraints :

t<20
n is a 32-bit integer

Sample Input:

1
7

Sample Output:

3

Score :

USE OF FUNCTIONS IN "math.h" IS NOT ALLOWED
B = Number of bitwise operators ( ~, |, &, ^, >>, << )
L = Number of loops ( for, while, do) and goto
K = Number of keywords
C = Number of semicolons ';'
P = Number of parentheses '(' ')'
S= 15000/ ( 100 + P + 10*C + 15000*B + 5000*L +50*K )

Solution:

For any given n, the code snippet counts the number of right most consecutive 1s in it's binary representation. For example, in 1011, answer is 2,
in 1111000, answer is 4
and in 110001, answer is 1.
The above part can be solved using recurrence.

If n is negative, then following operations of binary representation of abs(n):
1) from the right-most position, find the position of first occurance of 1. Let it be a.
2) from the right-most position, find the position of second occurance of 1. let it be b.
3) the answer is (b-a).
4) the cases of -1,-2,-4,-8....can be solved by applying a little extra condition.

Reference:2.9 Bitwise Operators, Dennis Ritchie

Code:

n,x,y,v,z;
r()
{
    if(n&&n%2==v){
        n/=2;
        ++y;
        r();
    }
}
in()
{
    if (scanf("%d",&n)==1){
        x=n,y=0;
        n=n<0?n*-1:n;
        v=0,
        r(),
        z=y;
        y=0,
        v=1,
        r(),
        x>=0?:(y>1?y=1:(n==0?(y=32-z):(y=1,v=0,r())));
        printf("%d\n",y),in();
    }
}
main()
{
    scanf("%*d");
    in();
}
 Check the Best Solutions