Author |
Topic: A puzzler (Read 6893 times) |
|
Sameer
Uberpuzzler
Pie = pi * e
Gender: 
Posts: 1261
|
 |
Re: A puzzler
« Reply #25 on: Jul 26th, 2007, 9:05am » |
 Quote  Modify
|
on Jul 23rd, 2007, 2:37am, 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!!  Anybody else want to add to this?
|
|
 IP Logged |
"Obvious" is the most dangerous word in mathematics.
--Bell, Eric Temple
Proof is an idol before which the mathematician tortures himself.
Sir Arthur Eddington, quoted in Bridges to Infinity
|
|
|
mad
Junior Member
Posts: 118
|
|
Re: A puzzler
« Reply #26 on: Jul 31st, 2007, 3:34pm » |
Quote Modify
|
With the stream of bits input from one end... find if it is divisible by 3..
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #27 on: Aug 1st, 2007, 12:50am » |
Quote Modify
|
on Jul 31st, 2007, 3:34pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
el_nino
Newbie
Posts: 4
|
|
Re: A puzzler
« Reply #28 on: Aug 2nd, 2007, 8:08pm » |
Quote Modify
|
if (n < 0)
n = -n;
n = n & 00110011001100110011001100110011 + (n >> 2) & 00110011001100110011001100110011;
n = n & 00001111000011110000111100001111 + (n >> 4) & 00001111000011110000111100001111;
n = n & 00000000111111110000000011111111 + (n >>  & 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
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #29 on: Aug 3rd, 2007, 12:43am » |
Quote Modify
|
on Aug 2nd, 2007, 8:08pm, 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).
|
| « Last Edit: Aug 3rd, 2007, 12:43am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
aileen529
Newbie
Gender: 
Posts: 4
|
|
Re: A puzzler
« Reply #30 on: Oct 2nd, 2007, 6:30pm » |
Quote Modify
|
on Jul 22nd, 2007, 7:04am, 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;
?
|
|
IP Logged |
|
|
|
saurabh.ngarg
Newbie
Gender:
Posts: 8
|
|
Re: A puzzler
« Reply #31 on: Oct 5th, 2007, 7:19pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
naveen
Newbie
Posts: 3
|
|
Re: A puzzler
« Reply #32 on: Oct 5th, 2007, 11:54pm » |
Quote Modify
|
on Jul 22nd, 2007, 7:04am, 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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #33 on: Oct 6th, 2007, 12:25pm » |
Quote Modify
|
on Oct 2nd, 2007, 6:30pm, aileen529 wrote:should it be
n = (n & 1) - (n & 2)>>1 + n >> 2;
? |
|
on Oct 5th, 2007, 11:54pm, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: A puzzler
« Reply #34 on: Nov 25th, 2007, 7:47am » |
Quote Modify
|
on Jul 22nd, 2007, 7:04am, 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....
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #35 on: Nov 25th, 2007, 8:15am » |
Quote Modify
|
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  0, so 3 does not divide 71 (in fact it has remainder 2)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: A puzzler
« Reply #36 on: Nov 27th, 2007, 12:33pm » |
Quote Modify
|
on Jul 22nd, 2007, 9:58am, 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. 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #37 on: Nov 27th, 2007, 12:53pm » |
Quote Modify
|
on Nov 27th, 2007, 12:33pm, 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
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: A puzzler
« Reply #38 on: Nov 27th, 2007, 1:31pm » |
Quote Modify
|
@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.
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: A puzzler
« Reply #39 on: Nov 27th, 2007, 1:43pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #40 on: Nov 27th, 2007, 1:56pm » |
Quote Modify
|
on Nov 27th, 2007, 1:43pm, 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.
|
| « Last Edit: Nov 27th, 2007, 2:04pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #41 on: Nov 27th, 2007, 2:09pm » |
Quote Modify
|
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.  [/edit]
|
| « Last Edit: Nov 27th, 2007, 2:17pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: A puzzler
« Reply #42 on: Nov 27th, 2007, 2:16pm » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: A puzzler
« Reply #43 on: Nov 27th, 2007, 2:19pm » |
Quote Modify
|
on Nov 27th, 2007, 2:16pm, 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)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: A puzzler
« Reply #44 on: Nov 27th, 2007, 2:24pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: A puzzler
« Reply #45 on: Nov 28th, 2007, 6:40am » |
Quote Modify
|
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
|
|
IP Logged |
--SMQ
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print