Download your favorite Linux distribution at LQ ISO.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org Binary Puzzle
 User Name Remember Me? Password
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 02-07-2004, 07:58 PM #16 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: Well thanks for all the hints, and some of the code. Im going to work on this over the week, but few exams and another cpu program may not let me. wapcaplet, your tip came to me a while ago where I took a number an unsigned int x^~0 and then shifted the first four bits into a int i would have bit sequence of eihter all 0's , all 1's, one 1, or two 1's but that would need comparisons. Well ill keep plugging.
 02-07-2004, 09:25 PM #17 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: wapcaplet I did solve it I think, I just did not put into code yet. I use mostly shifting and addition to do it, and no XOR. I could not figure out a way using XOR. Although I know that when you XOR to a (~0) , the result will be either one 1 or two 1's, hence even or odd number of numbers I am not sure how this would aid me. I only see that shifting 28 left and back 28 and then XOR would give me a result of 4 bits with one 1 or two 1's, but not sure withoug addition to solve that. You guys, wapcaplet,, kev82 and Hko have been really helpfull, I appreciate the help rather than the answer. I hope I can depend you guys if I ever need help agian, and a thanks to any others I did not mention.
 02-07-2004, 09:31 PM #18 wapcaplet Guru   Registered: Feb 2003 Location: Colorado Springs, CO Distribution: Gentoo Posts: 2,018 Rep: To make my hint more explicit, say you have an 8-bit binary number with five 1's in it (odd number): 01011101. Code: ``` 0101 ^ 1101 = 1000 (Even or odd number of 1's left?)``` Now you have a 4-bit binary number... On the other hand, if you have an 8-bit binary number with an even number of 1's in it... Last edited by wapcaplet; 02-07-2004 at 09:32 PM.
 02-07-2004, 09:56 PM #19 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: I understand what would result but because I only pass one int into I would make a mask of 1's to XOR. mask = ~0; 1111 is actually mask; 0101 0011 1001 1100 (all these have even 1's) ^1111 ^1111 ^1111 ^1111 ---> is mask ------ ------ ------ ------- = 1010 1100 0110 0011 (result two 1's for any even) 1000 1110 1011 0111 0010 (all have odd number of 1's) ^1111 ^1111 ^1111 ^1111 ---> is mask = ------ ------- ------- ------- 0111 0001 1011 1000 (result is one 1, or three 1's for any odd) Lets not for get 0000 ^1111 =1111 (still an even number of 1's for any even (0 is even by definition)) Sum it up: two 1's or four 1's for even and; one 1, or three 1's for odd numbers. I cant use a count to check for the number of 1's or use inequalities (<, >, >=, <=) to check. I know my method is that I have not posted, but described earlier is slow but I do not see a more efficient way. I am sure you are leading me to it, I hope it comes. Thank you.
 02-07-2004, 10:09 PM #20 wapcaplet Guru   Registered: Feb 2003 Location: Colorado Springs, CO Distribution: Gentoo Posts: 2,018 Rep: All you've done by XORing it with all 1's is to negate it You may as well just use '~' on it. But you don't need to do either... look more closely at my last hint, especially at what I did with the incoming 8-bit value.
 02-07-2004, 11:06 PM #21 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: Ok, As steam comes of my head and I see the brain cells (or should i say, dumb cells) evaportate I think I came up with version 2 with your help wapcaplet. What I would do is to grab the last 4 bits of any word size, ours is 32 by shifing <<28 and >> 28. So now I have one of the 16 possible bit combos in some variable num. Next take this 4 bit sequence put this into 2 more variables that have split the 4 bit sequence into 2- 2 bit sequences. num = 0111 (off original) num1 = 0001 (last 2 bits off num by shifting) num2 = 0011 (first two bits off num by shifting) Now. unsigned int Y = num1 ^ num2 (0010) num3 = 0001 (last bit off Y by shifting) num4 = 0000 (first bit off Y by shifting) Now. Y = num3 ^ num4 (0001) return Y; Y now has and odd number of zeros which is what we wanted and works of all cases. Boy, Thank you so much, I really appreciate the pain. I would rather hurt and learn than not hurt and not learn. I hope if I come back here again you can be this helpful. I think this has as many steps as my other method but is esier to understand. Thank you so much.
 02-08-2004, 09:49 AM #22 Hko Senior Member   Registered: Aug 2002 Location: Groningen, The Netherlands Distribution: ubuntu Posts: 2,530 Rep: I think wapcaplet's solution is quite nice. If I got it right, the key to the solution is that XOR-ing 2 integers of the same length (in bits) results in an integer with the same parity as the two integers have together, but it has only half of the total number of bits you started with! I see a nice, short, soltution using recursion. Even though recursion is probably not allowed in the puzzle, you could very well use this feature of XOR-ing integers without recursion. Last edited by Hko; 02-08-2004 at 09:53 AM.
 02-08-2004, 11:06 AM #23 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: Yeah, I found a small hole in mine befor any of you mention it. 17 would produce the wrong answer, but to correct it and make even easier to code. I would just "divide and Conquer" the entire string of 32 bits with XOR. So will will XOR 16, then 8, then 4, then 2, and then 1 bit. That should cover all cases. Funny how XOR works. If you think about it, its even subtraction between to binary bits. Or should I say "difference in Positive value" seeing as how no negatives can come from that. Hko, no recursion. Boy that word just brings back memories of scheme.
 02-08-2004, 03:34 PM #24 wapcaplet Guru   Registered: Feb 2003 Location: Colorado Springs, CO Distribution: Gentoo Posts: 2,018 Rep: Yep, now you are getting what I was getting at The 1 bit you are left with at the end tells you whether an even or odd number of 1's existed originally (and thus, an even or odd number of 0's). XOR really is a form of subtraction (and you're exactly right that it's more like "difference in positive value - it's the absolute value of the result); in fact, if you think about it, when you implement an arithmetic operation in hardware, all you have to work with is AND, OR, XOR and stuff like that - a bunch of logic gates all hardwired together. Though, from what I've learned about computer logic, they almost never bother implementing subtraction - since it's the same as adding the two's complement. If you guys like puzzles like this, check out this site, which has a bunch of programming-related puzzles. Lots of other interesting riddles there too.
 02-08-2004, 03:42 PM #25 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: wapcaplet, Thank you. I will be sure to leave you postive comments, if I was a registered user, (maybe after my 3 exams, and 2 programs this week (one of which is puzzles aready done on paper)), I will register so I can donate. Im not a rich student, but I learned by being forced too by you. And I appreciate it. I really enjoy codeing and taking on challenges. Do you take paypal? Thanks a bunch. Cheers. Axioss
 02-08-2004, 03:50 PM #26 wapcaplet Guru   Registered: Feb 2003 Location: Colorado Springs, CO Distribution: Gentoo Posts: 2,018 Rep: Nahh, don't worry about that. I'm glad to help.

 Thread Tools Search this Thread Search this Thread: Advanced Search

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post aioss Linux - Software 0 02-07-2004 02:44 PM sureshot! Linux - Networking 3 10-22-2003 06:54 AM jbmcmillan Linux - Software 3 10-16-2003 03:42 PM cpeppler Linux - Software 12 10-06-2003 01:37 PM tachyon273 Linux - Networking 0 03-14-2003 05:38 PM

All times are GMT -5. The time now is 09:52 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -
 Advertisement
 My LQ
 Write for LQ LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
 Syndicate Latest Threads   LQ News Twitter: @linuxquestions identi.ca: @linuxquestions Facebook: linuxquestions Google+: linuxquestions