ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.
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.
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.
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.
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.
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)
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.
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.
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.
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.
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.