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 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 



02072004, 06:58 PM

#16

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.



02072004, 08:25 PM

#17

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.



02072004, 08:31 PM

#18

Guru
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018
Rep:

To make my hint more explicit, say you have an 8bit 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 4bit binary number...
On the other hand, if you have an 8bit binary number with an even number of 1's in it...
Last edited by wapcaplet; 02072004 at 08:32 PM.



02072004, 08:56 PM

#19

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.



02072004, 09:09 PM

#20

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 8bit value.



02072004, 10:06 PM

#21

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.



02082004, 08:49 AM

#22

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 XORing 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 XORing integers without recursion.
Last edited by Hko; 02082004 at 08:53 AM.



02082004, 10:06 AM

#23

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.



02082004, 02:34 PM

#24

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 programmingrelated puzzles. Lots of other interesting riddles there too.



02082004, 02:42 PM

#25

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



02082004, 02:50 PM

#26

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 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 11:28 AM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

