LinuxQuestions.org
View the Most Wanted LQ Wiki articles.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
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

Reply
 
LinkBack Search this Thread
Old 02-07-2004, 06:58 PM   #16
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0

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.
 
Old 02-07-2004, 08:25 PM   #17
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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.
 
Old 02-07-2004, 08:31 PM   #18
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
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 08:32 PM.
 
Old 02-07-2004, 08:56 PM   #19
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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.
 
Old 02-07-2004, 09:09 PM   #20
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
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.
 
Old 02-07-2004, 10:06 PM   #21
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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.
 
Old 02-08-2004, 08:49 AM   #22
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep: Reputation: 108Reputation: 108
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 08:53 AM.
 
Old 02-08-2004, 10:06 AM   #23
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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.
 
Old 02-08-2004, 02:34 PM   #24
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
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.
 
Old 02-08-2004, 02:42 PM   #25
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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
 
Old 02-08-2004, 02:50 PM   #26
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
Nahh, don't worry about that. I'm glad to help.
 
  


Reply


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
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary Puzzle aioss Linux - Software 0 02-07-2004 01:44 PM
dhcpd puzzle sureshot! Linux - Networking 3 10-22-2003 05:54 AM
rpm puzzle jbmcmillan Linux - Software 3 10-16-2003 02:42 PM
A puzzle for you to figure out, I can't cpeppler Linux - Software 12 10-06-2003 12:37 PM
Multicasting puzzle tachyon273 Linux - Networking 0 03-14-2003 04:38 PM


All times are GMT -5. The time now is 12:34 AM.

Main Menu
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.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration