wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> A puzzler
        
(Message started by: u_think_u_succeed on Jul 22nd, 2007, 1:53am)
Title: A puzzler
Post by u_think_u_succeed on Jul 22nd, 2007, 1:53am
Given a number, how can u determine using C, whether it is divisible by 3, without using *, /, % operators.

You may assume that itoa() function is available.
Title: Re: A puzzler
Post by I_am_searching on Jul 22nd, 2007, 6:21am
convert  the number to the string using itoa();

add up all the digits  
checkDivisibility(int num){
char *str=itoa(num)

while (1)
{
for (i =0 ; i < strlen(str);i++)
sum= sum + (str[i] - "0");

if (sum > 10)
str=itoa(sum);  
else
break;
}

if(sum == 3 || sum == 6 || sum == 9)
printf("Number divisible by 3");
else
printf("Number not divisible by 3");

}
Title: Re: A puzzler
Post by I_am_searching on Jul 22nd, 2007, 6:23am
Correction....

add sum=0;
just at the beginning of while loop
Title: Re: A puzzler
Post by towr on Jul 22nd, 2007, 7:04am
Doesn't seem very nice to use itoa

How about something along the lines of

Code:
if(n < 0)
 n = -n;

while (n >= 3)
{
n = (n & 1) - (n & 2)>>1 + n >> 2;
}

return n==0;


[edit]Added the >>1 for (n & 2) which was mistakenly left out. (Pointed out in replies 30,32)[/edit]
Title: Re: A puzzler
Post by u_think_u_succeed on Jul 22nd, 2007, 8:03am
Towr,

Could you please explain the logic .. ?
Title: Re: A puzzler
Post by towr on Jul 22nd, 2007, 9:09am

on 07/22/07 at 08:03:03, u_think_u_succeed wrote:
Could you please explain the logic .. ?
A rightshift by two is a divide by 4 and
1 = 1 (mod 3)
2 = -1 (mod 3)
4 = 1 (mod 3)
etc
Adding the bits alternately positive and negative can therefore be used for the divisibility test. Just like when you test for 11 in decimal. (For testing divisibility by 3 in decimal you add all digits, because 10n = 1 (mod 3) ).
And of course you can repeat this until you have a number n, 0 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif n < 3.

So we take Nk = a * 22 + b * 21 + c * 20, with a http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif 0 and b,c http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/in.gif {0,1}
And turn it into Nk+1 = a - b + c
Title: Re: A puzzler
Post by towr on Jul 22nd, 2007, 9:58am
An approach based on the bit counting puzzle.

Code:
if (n < 0)
 n = -n;

n = n & 00110011001100110011001100110011 + (n >> 2) & 00110011001100110011001100110011;
n = n & 00001111000011110000111100001111 + (n >> 4) & 00001111000011110000111100001111;
n = n & 00000000111111110000000011111111 + (n >> 8) & 00000000111111110000000011111111;
n = n & 00000000000000001111111111111111 + (n >> 16) & 00000000000000001111111111111111;
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;

n = n & 1 - (n >> 1) & 1 + (n >> 2) & 1;
return n==0;


First take the absolute value of n.
Then calculate the sum of digits in base 4: a base 4 number is divisible by 3 if the sum of its digits is divisible by 3. With a 32 bit integer we sum 16 digits, so we get at most a sum of 47 (*); which is contained in the last 6 bits of n. We can sum these as 3, base-4 digits again, and the result fits in 3 bits (**).
And then as final steps we checks divisibility by 3: add bit 1 and 3 and subtract bit 2, if this yield 0 we have a number divisible by 3.

(*) We could get 48 only if all bits were 1s, but that can only be for n=-1 and we take the absolute value before summing the base-4 digits.
(**) If we could get a sum of 48 at (*), we might spill into the 4th bit, but luckily that's avoided.

PS, those bitmasks should probably not be written in binary, because C might mistake them for octal instead; but for clarity's sake I think writing it as bitmasks makes sense.
Title: Re: A puzzler
Post by u_think_u_succeed on Jul 22nd, 2007, 11:30am
Marvellous Towr !!  :D ::)
Hats off to you.

Well, if we know the size of the number a priori, then simply adding bits 0, 2,4, 6,8, ... 31 and subtracting bits 1,3,5,7,...30; and testing if the result is zero will do the trick (i.e. if the result is zero, then the number is divisible by 3).
Title: Re: A puzzler
Post by towr on Jul 22nd, 2007, 11:48am

on 07/22/07 at 11:30:08, u_think_u_succeed wrote:
Well, if we know the size of the number a priori, then simply adding bits 0, 2,4, 6,8, ... 31 and subtracting bits 1,3,5,7,...30; and testing if the result is zero will do the trick.
True, but I think that that might be slower. In my second approach you do a lot of additions parallel.
Title: Re: A puzzler
Post by u_think_u_succeed on Jul 22nd, 2007, 11:51am
Any more examples of such type ?  ::)
Title: Re: A puzzler
Post by towr on Jul 22nd, 2007, 11:54am
In general in base b :
a*bn = a (mod b-1)

and

a*bn = a (mod b+1) for even n and  
a*bn = - a (mod b+1) for odd n

So for binary, you can easily do things for n = 3,5,7,9,15,17,31,33 etc.
For the other numbers it will be more work (because you're dealing with longer sequences that repeatedly 1 or alternating 1 and -1.)

[edit]switched b and n halfway through writing..[/edit]
Title: Re: A puzzler
Post by u_think_u_succeed on Jul 22nd, 2007, 8:36pm
Well, how about this extension,

given a number, you now actually need to divide that number by 3. The same constraints apply : No use of *, /, % operators. Again it may assumed that itoa() is available.
Title: Re: A puzzler
Post by towr on Jul 23rd, 2007, 12:39am
You could do a binary search for the largest K such that N > (K << 1 + K ).
I'm sure there's a more clever way, but I'll need to think a bit.
Title: Re: A puzzler
Post by Grimbal on Jul 23rd, 2007, 1:04am

on 07/22/07 at 07:04:08, towr wrote:
while (n >= 3)

Are you sure it works for n=3?  ::)
Arhum... I must have been posting random text by mistake while cleaning my keyboard... :-[

This being said, the alternate bit count solution is nice.
Title: Re: A puzzler
Post by towr on Jul 23rd, 2007, 2:05am

on 07/23/07 at 01:04:05, Grimbal wrote:
Are you sure it works for n=3?  ::)
Yes.
Title: Re: A puzzler
Post by u_think_u_succeed on Jul 23rd, 2007, 2:21am

Quote:
You could do a binary search for the largest K such that N > (K << 1 + K ).




I doubt I understand the above, but binary search anyway might involve some use of / operator.

Do you have any solution (even if it runs in linear time in number of bits) in mind ?
Title: Re: A puzzler
Post by towr on Jul 23rd, 2007, 2:29am

on 07/22/07 at 20:36:09, u_think_u_succeed wrote:
Well, how about this extension,

given a number, you now actually need to divide that number by 3. The same constraints apply : No use of *, /, % operators. Again it may assumed that itoa() is available.


I think this should work:
[edit v2]Fixed the function to handle negative n. There is some choice whether you want -2 div 3 to be 0 or -1, I choose the latter.[/edit]

Code:
int div3(int n)
{
 if (n < 0)
   return -div3(2-n);

 n += 1;
 n += (n >> 2);
 n += (n >> 4);
 n += (n >> 8);
 n += (n >> 16);
 n >>= 2;
 
 return n;
}

Rationale: multiply by 1/3 = 0.01010101.. (binary)
step 1 = 1.01 N
step 2 = 1.010101 N
step 3 = 1.01010101010101 N
step 4 = 1.010101010101010101010101010101 N
step 5 = 0.01010101010101010101010101010101 N

[edit]Some frantic editing was needed because I had the wrong order (I had the final 2-right-shift at the top, which yielded wrong answer; this should now be fixed. And hopefully the rest of the reasoning is now correct.[/edit]

You need to add one if N is divisible by 3, because the binary expansion of 1/3 continues infinitely, so you alway have less than 1/3 N in step 5 (which is only a problem if N is divisible by 3, becuase its an integer divide and in the other two cases the difference is the rest value)
[edit v2]Adding 1 at the start is more effective[/edit]

It seems actually dividing by three might yield a more efficient divisibility test than the earlier approaches.
[edit v2]Just test with k=div3(n) whether (k+ k<<1) == n [/edit]
Title: Re: A puzzler
Post by towr on Jul 23rd, 2007, 2:30am

on 07/23/07 at 02:21:46, u_think_u_succeed wrote:
I doubt I understand the above, but binary search anyway might involve some use of / operator.
No, you'd just use shifting and adding.


Quote:
Do you have any solution (even if it runs in linear time in number of bits) in mind ?
Yup, just now :)
Title: Re: A puzzler
Post by I_am_searching on Jul 23rd, 2007, 2:35am
How abt my soln....does it not confirms to what actually the problem states....

ne comments....

i dont understand these bit fiddlings at all.... :( ;D
Title: Re: A puzzler
Post by I_am_searching on Jul 23rd, 2007, 2:37am
and now i have started hating these bit manipulation operations as I screwed up My google 3rd interview today jus beacuse of these bits... :( :(
Title: Re: A puzzler
Post by towr on Jul 23rd, 2007, 2:39am

on 07/23/07 at 02:35:56, I_am_searching wrote:
How abt my soln....does it not confirms to what actually the problem states....

ne comments....

i dont understand these bit fiddlings at all.... :( ;D
Yeah, yours works too (although there's still a small mistake where you subtract "0" instead of '0'; subtracting c-strings from characters will give weird results if it works). The main difference is you solve it in decimal rather than binary; and with the conversion to string it will be a bit slower.
Title: Re: A puzzler
Post by I_am_searching on Jul 23rd, 2007, 2:41am
yeah towr....

I approached the problem as it was stated ...... I need to start thinking out of the box!!!!!! :-X
Title: Re: A puzzler
Post by Shashikant on Jul 25th, 2007, 12:29am
int ans=0;
While(num<=3)
{
num = num-3;
ans = ans+1;
}
if(num==0)
printf("Number is divisible by 3 and Answer is %d",ans);
else
printf("Number not divisible by 3 and Answer is %d and remainder is %d",ans,num);
Title: Re: A puzzler
Post by towr on Jul 25th, 2007, 12:42am

on 07/25/07 at 00:29:10, Shashikant wrote:
int ans=0;
While(num<=3)
{
num = num-3;
ans = ans+1;
}
if(num==0)
printf("Number is divisible by 3 and Answer is %d",ans);
else
printf("Number not divisible by 3 and Answer is %d and remainder is %d",ans,num);
That while condition seems a bit suspect, and it would take very long for large numbers.
Title: Re: A puzzler
Post by gowrikumar on Jul 25th, 2007, 10:19pm

on 07/22/07 at 01:53:18, u_think_u_succeed wrote:
Given a number, how can u determine using C, whether it is divisible by 3, without using *, /, % operators.

You may assume that itoa() function is available.


Here is what I can think of :
The decimal equivalent of a binary representation of number  abcdef is (where all a,b,c,d,e,f are either zero or 1):

2^0 * f + (2^1) * e + (2^2) * d + (2^3) *c + .....
(Note : ^ is used to denote power (and not xor:-)

Now replace 2 by 3-1 in the above representation
(3-1)^0 *f + ((3-1)^1)*e + ((3-2)^2)*d + ....

Applying binomial theorm, we can notice that each of the every term of the expansion (3-1)^n will have a 3 except the last term, which would either be a 1 or -1 depending on the value of n.

We can use this observation as follows:
- Get every bit in the number
- check if it is  1
- If so, add -1 or 1 depending on the position of the bit.

If the resutant sum is dicisible by 3, then the original number is divisible by 3. The implementation of it is as follows (the code also includes the verification part):

Code:
#include <stdio.h>
#include <assert.h>

int arr[32] = {1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0,0,
1,0};
 
int main()
{
int sign ;
int sum ;
int num ;
int i;

for(i=0;i<1000000;i++)
{
sign = 1;
sum = 0;
num = i;

while(num)
{
if(num&1)
{
sum += sign;
}
sign = -sign;
num = num >> 1;
}

if(sum<0)
sum = -sum;

printf("i : %d\n",i);
assert ( (arr[sum]) == (i%3==0));
}
return 0;

}




There is further optimization possible:
It is possible to do away with the array. We can try simulating a finite state machine which keeps track of the modulo 3, with the sum.
Title: Re: A puzzler
Post by Sameer on Jul 26th, 2007, 9:05am

on 07/23/07 at 02:37:28, I_am_searching wrote:
and now i have started hating these bit manipulation operations as I screwed up My google 3rd interview today jus beacuse of these bits... :( :(


Working in bits can be trick especially if you are new to it...
Here's how you can improve it!!

Take some numbers and manually try to convert them to binary, octal and hex!!! (You can verify your answer using a calculator). Once you are able to do this pretty fast you will realize doing bit manipulations is easy. You will see that expressing a number in HEX is very convenient.. It allows you to quickly express numbers in binary and understand it as well as quickly apply the bit manipulations to it.. Soon you will be an expert!!  :D Anybody else want to add to this?
Title: Re: A puzzler
Post by mad on Jul 31st, 2007, 3:34pm
With the stream of bits input from one end... find if it is divisible by 3..
Title: Re: A puzzler
Post by towr on Aug 1st, 2007, 12:50am

on 07/31/07 at 15:34:48, mad wrote:
With the stream of bits input from one end... find if it is divisible by 3..
Just alternately add and subtract; precisely as has been done earlier in the thread. If the result is 0 modulo 3 it's divisible otherwise it's not.
Title: Re: A puzzler
Post by el_nino on Aug 2nd, 2007, 8:08pm
if (n < 0)  
 n = -n;

n = n & 00110011001100110011001100110011 + (n >> 2) & 00110011001100110011001100110011;
n = n & 00001111000011110000111100001111 + (n >> 4) & 00001111000011110000111100001111;
n = n & 00000000111111110000000011111111 + (n >> 8) & 00000000111111110000000011111111;
n = n & 00000000000000001111111111111111 + (n >> 16) & 00000000000000001111111111111111;
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;

towr , can you please explain the above code to me. i am new to this bit fiddling
Title: Re: A puzzler
Post by towr on Aug 3rd, 2007, 12:43am

on 08/02/07 at 20:08:20, el_nino wrote:
if (n < 0)  
 n = -n;

n = n & 00110011001100110011001100110011 + (n >> 2) & 00110011001100110011001100110011;
n = n & 00001111000011110000111100001111 + (n >> 4) & 00001111000011110000111100001111;
n = n & 00000000111111110000000011111111 + (n >> 8) & 00000000111111110000000011111111;
n = n & 00000000000000001111111111111111 + (n >> 16) & 00000000000000001111111111111111;
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;

towr , can you please explain the above code to me. i am new to this bit fiddling
Pretty much the entire explanation was given in the same post.
You skipped the last lines though; so what you have here is only part that adds the digits of the absolute value in base 4.

What I'm doing essentially is at each step sum two adjacent partial sums (starting with the single digits). Because the result of summing two n-bit number won't be greater than 2n bits, you don't have to worry about the partial sums carrying over into each other; this allows doing sums parallel.
So if e.g. we have base-4 number 10230212 (and we want 1+0+2+3+0+2+1+2)
we first make the sum   0030202 + 1020001 =  1110203 (representing 1+11+2+3)
then 0110003 + 10002 = 120011 (representing 12+11)
then 11+12 = 23, which is the sum of the digits in base 4 (i.e. 11 in decimal).
Title: Re: A puzzler
Post by aileen529 on Oct 2nd, 2007, 6:30pm

on 07/22/07 at 07:04:08, towr wrote:
Doesn't seem very nice to use itoa

How about something along the lines of

Code:
if(n < 0)
 n = -n;

while (n >= 3)
{
n = (n & 1) - (n & 2) + n >> 2;
}

return n==0;


should it be

n = (n & 1) - (n & 2)>>1 + n >> 2;

?
Title: Re: A puzzler
Post by saurabh.ngarg on Oct 5th, 2007, 7:19pm
To test the divisibility by 3 and if we are allowed to use itoa function, we can first convert the  number  to base 3 using itoa and check this least significant digit in the string. if it is zero...number is divisible by 3 else not.
Title: Re: A puzzler
Post by naveen on Oct 5th, 2007, 11:54pm

on 07/22/07 at 07:04:08, towr wrote:
Doesn't seem very nice to use itoa

How about something along the lines of

Code:
if(n < 0)
 n = -n;

while (n >= 3)
{
n = (n & 1) - (n & 2) + n >> 2;
}

return n==0;



I think, the assignment in while loop should be

n = (n & 1) - (n & 2)>>1 + n >> 2;

As we are extracting the bits and alternatively adding & subtracting them so we have to right shift the second one to get the bit at one's place. Otherwise , it will not provide the desired results.
Title: Re: A puzzler
Post by towr on Oct 6th, 2007, 12:25pm

on 10/02/07 at 18:30:55, aileen529 wrote:
should it be

n = (n & 1) - (n & 2)>>1 + n >> 2;

?


on 10/05/07 at 23:54:31, naveen wrote:
I think, the assignment in while loop should be

n = (n & 1) - (n & 2)>>1 + n >> 2;
It's been a while since I wrote it, but I think you two are right.
Title: Re: A puzzler
Post by johny_cage on Nov 25th, 2007, 7:47am

on 07/22/07 at 07:04:08, towr wrote:
Doesn't seem very nice to use itoa

How about something along the lines of

Code:
if(n < 0)
 n = -n;

while (n >= 3)
{
n = (n & 1) - (n & 2) + n >> 2;
}

return n==0;


@towr,

plz explain with an example, i tried the above code, it is not working... correct me if i m wrong....
Title: Re: A puzzler
Post by towr on Nov 25th, 2007, 8:15am
The reason it doesn't work is because I haven't fixed the error pointed out in the last few posts.

The correct line should be
n = (n & 1) - (n & 2)>>1 + n >> 2;


So if we take 71 = 64+4+2+1 = 1000111 (in binary)
1000111
->
1 - 1 + 10001 = 10001
->
1 - 0 + 100 = 101
->
1 - 0 + 1 = 10 = 2 (in decimal)

2 < 3 and 2 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ne.gif0, so 3 does not divide 71 (in fact it has remainder 2)
Title: Re: A puzzler
Post by johny_cage on Nov 27th, 2007, 12:33pm

on 07/22/07 at 09:58:24, towr wrote:
An approach based on the bit counting puzzle.

Code:
if (n < 0)
 n = -n;

n = n & 00110011001100110011001100110011 + (n >> 2) & 00110011001100110011001100110011;
n = n & 00001111000011110000111100001111 + (n >> 4) & 00001111000011110000111100001111;
n = n & 00000000111111110000000011111111 + (n >> 8) & 00000000111111110000000011111111;
n = n & 00000000000000001111111111111111 + (n >> 16) & 00000000000000001111111111111111;
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;

n = n & 1 - (n >> 1) & 1 + (n >> 2) & 1;
return n==0;


First take the absolute value of n.
Then calculate the sum of digits in base 4: a base 4 number is divisible by 3 if the sum of its digits is divisible by 3. With a 32 bit integer we sum 16 digits, so we get at most a sum of 47 (*); which is contained in the last 6 bits of n. We can sum these as 3, base-4 digits again, and the result fits in 3 bits (**).
And then as final steps we checks divisibility by 3: add bit 1 and 3 and subtract bit 2, if this yield 0 we have a number divisible by 3.

(*) We could get 48 only if all bits were 1s, but that can only be for n=-1 and we take the absolute value before summing the base-4 digits.
(**) If we could get a sum of 48 at (*), we might spill into the 4th bit, but luckily that's avoided.

PS, those bitmasks should probably not be written in binary, because C might mistake them for octal instead; but for clarity's sake I think writing it as bitmasks makes sense.


@towr
Please elaborate it more, I am not able to get it. :'(
Title: Re: A puzzler
Post by towr on Nov 27th, 2007, 12:53pm

on 11/27/07 at 12:33:12, johny_cage wrote:
Please elaborate it more, I am not able to get it. :'(
I'm not sure what more to say.
You sum the digits of the number as represented in base 4 (in 4 steps)
If N is divisible by 3, then so must this (for the same reason it works in decimal 10i = 1 (mod 3), and likewise 4i = 1 (mod 3) )

Then you have at most a 3-digit number (in base 4), so sum those 3 together again, the result spans at most 3 bits.

And then test divisibility by 3; a binary number is divisible by 3, if alternately adding/subtracting the bits yields 0.
e.g.
2 = 10 -> -1 + 0 = -1
3 = 11 -> -1 + 1 = 0
9 = 1001 -> -1 + 0 + -0 + 1 = 0
Title: Re: A puzzler
Post by johny_cage on Nov 27th, 2007, 1:31pm
@towr
i appreciate your feedback.

My problem :
I am using your code, but it is not giving the output as expected. I think, I m not getting its usage, i used it as :


Code:
#include <iostream.h>

int check_towr(int n)
{
if (n < 0)  
  n = -n;
n = (n & 0x33333333) + ((n>>2) & 0x33333333);
n = (n & 0x0F0F0F0F) + ((n>>4) & 0x0F0F0F0F);
n = (n & 0x00FF00FF) + ((n>>8) & 0x00FF00FF);
n = (n & 0x0000FFFF) + ((n>>16)& 0x0000FFFF);
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;
n = n & 1 - (n >> 1) & 1 + (n >> 2) & 1;
return n;
}

void main ()
{
int num;
cout<<"Enter num  : ";
cin>>num;
cout<<"Answer by towr is : \n";
if (!check_towr(num))
cout<<"True\n";
else
cout<<"False\n";

}


Please correct my usage if it is wrong.
Title: Re: A puzzler
Post by johny_cage on Nov 27th, 2007, 1:43pm
hey towr
after observing the values quite several times, now i m getting it.... :)
but i am thinking that the following line might be having problem...


Quote:
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;
n = n & 1 - (n >> 1) & 1 + (n >> 2) & 1;


Moreover, can we do one thing, just sum up all the even bits and odd bits separately in one go. Then subtract them, if it is 0, then number is divisible by 3 else not. This way, same method of counting bits can be used here, and algorithm is no longer slower.

For odd bits case, i mean just AND the number by 0x33333333 first and then count the set bit as you told in this post earlier.

For even case, right shift the number by 1, and follow the same above written algorithm.
Then add them.

Hope, what i m saying is clear to you?
Title: Re: A puzzler
Post by towr on Nov 27th, 2007, 1:56pm

on 11/27/07 at 13:43:18, johny_cage wrote:
but i am thinking that the following line might be having problem...
What sort of problems should they give?

This problem is actually one of the rare occasions I actually tested my code, and it all worked fine for me then. [edit]Hmm, I can't seem to find my program, and I hardly ever throw something away, so maybe I'm being delusional again ;)[/edit]


Quote:
Moreover, can we do one thing, just sum up all the even bits and odd bits separately in one go. Then subtract them, if it is 0, then number is divisible by 3 else not.
No, you should check whether the result is divisible by 3, not just check whether it is 0. You might have 15 even bits set, and no odd bits; it'd still be divisible by 3, even though the difference is 15.
So you need to reduce things further


Quote:
Hope, what i m saying is clear to you?
Yup, I think so. I'm not sure it would be overall faster though. It seems to me you'd need more operations in total.
Title: Re: A puzzler
Post by towr on Nov 27th, 2007, 2:09pm
Note, changing n==0 to n invalidates the warranty ;)

[edit]Also, it seems those last two lines do need some extra parentheses; so you're right in your assertion something was amiss with them.
Of course, conceptually, everything worked brilliantly, just as it should. ;D[/edit]
Title: Re: A puzzler
Post by johny_cage on Nov 27th, 2007, 2:16pm

Code:
int check_towr(int n)
{

if (n < 0)  
  n = -n;
n = (n & 0x33333333) + ((n>>2) & 0x33333333);
n = (n & 0x0F0F0F0F) + ((n>>4) & 0x0F0F0F0F);
n = (n & 0x00FF00FF) + ((n>>8) & 0x00FF00FF);
n = (n & 0x0000FFFF) + ((n>>16)& 0x0000FFFF);
cout<<"\nNum : "<<n;
n = n & 3 + (n >> 2) & 3 + (n >> 4) & 3;
n = n & 1 - (n >> 1) & 1 + (n >> 2) & 1;
cout<<"\nNum : "<<n<<"\n";
return n;
}


Now for input, 17, it is showing output as :

Answer by towr is :
Num : 2
Num : 0
True

Please explain, where i am missing something... :'(
Title: Re: A puzzler
Post by towr on Nov 27th, 2007, 2:19pm

on 11/27/07 at 14:16:04, johny_cage wrote:
Please explain, where i am missing something... :'(
C++ doesn't seem to get its priorities straight (i.e. the way I want it to)
But using
n = (n & 3) + ((n >> 2) & 3) + ((n >> 4) & 3);
n = (n & 1) - ((n >> 1) & 1) + ((n >> 2) & 1);
seems to do the trick (might be overkill on the parentheses, but better safe than sorry, apparently)
Title: Re: A puzzler
Post by johny_cage on Nov 27th, 2007, 2:24pm
Now, I am getting the answer. Hmmmm, so this was the problem who kill my 2 hrs, and also trouble you a lot with my replies.

Thanks for your kind support. :)
Title: Re: A puzzler
Post by SMQ on Nov 28th, 2007, 6:40am
Yeah, I trip over those occasionally too.  Bitwise operators are very low precedence in C and C-like languages (C++, Java, Perl, etc.).

In broad terms, from highest precedence to lowest:
 Member/Element access, e.g. [] . ->, and function calls
 Unary operators, e.g. ++ -- - !, and type casts
 Standard Arithmetic operators, e.g. * / % + -
 Shifts, e.g. << >>
 Comparison operators, e.g. == != <=
 Bitwise operators, e.g. & | ^
 Boolean operators, e.g. && ||
 The ternary operator ? :
 Assignments, e.g. = += >>=

So minimally, you need:
n = (n & 3) + (n >> 2 & 3) + (n >> 4 & 3);
n = (n & 1) - (n >> 1 & 1) + (n >> 2 & 1).

--SMQ


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board