Welcome to the most active Linux Forum on the web.
 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, 03:38 PM #1 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Rep: Binary Puzzle Do any fo you techie's think you can solve this. I have about 4 hrs into it and still unsolved. No logical operators, i.e. if, else, == , ||, && , etc. ONLY binary ops as indicated in the snippit. * bitParity - returns 1 if x contains an odd number of 0's * Examples: bitParity(5) = 0, bitParity(7) = 1 * Legal ops: ! ~ & ^ | + << >> * Max ops: 20 * Rating: 4 */ int bitParity(int x) { return ; } One more. * sm2tc - Convert from sign-magnitude to two's complement * where the MSB is the sign bit * Example: sm2tc(0x80000005) = -5. * Legal ops: ! ~ & ^ | + << >> * Max ops: 15 * Rating: 4 */ int sm2tc(int x) { return ; } example I am using the examples give for a word size 16 (to keep it simple) 5= 0000 0000 0000 0101 this will return 0 because it has an even number of zeros. Where as 7 = 0000 0000 0000 0111 this will return 1 because it has an odd number of zeros. Now keep in mind no logic can be used, only bit leve ops. ! ~ & ^ | + << >> Last edited by aioss; 02-07-2004 at 05:01 PM.
02-07-2004, 05:16 PM   #2
Hko
Senior Member

Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep:
Quote:
 * Examples: bitParity(5) = 0, bitParity(7) = 1
I suppose bitParity(5) should be "1" as well....

<edit>
Oops! I was quite wrong here!
I answered to quickly, and stupidly!
</edit>

Last edited by Hko; 02-07-2004 at 05:21 PM.

 02-07-2004, 05:21 PM #3 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: No, if word size is 16 as I showed in my example "5= 0000 0000 0000 0101" and there is two 1's then that would leave you an even number (14 zeros) of zeros. So the retun value by the function would be a 0 because it does not have an odd number of zeros. Understand? I don't know the answer that is why I am asking for help.
 02-07-2004, 05:40 PM #4 Hko Senior Member   Registered: Aug 2002 Location: Groningen, The Netherlands Distribution: ubuntu Posts: 2,530 Rep: Yes, I understand, see my that I did at the same time as your post.
 02-07-2004, 05:50 PM #5 Hko Senior Member   Registered: Aug 2002 Location: Groningen, The Netherlands Distribution: ubuntu Posts: 2,530 Rep: Are loops (for / while) allowed?
 02-07-2004, 05:58 PM #6 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: Sorry, no loops or anything logical. I.E. for, while, if ,else, &&, ||, !=, etc. ONLY binary level operators (! ~ & ^ | + << >>) that is all. really dont need them anyhow, just neet to test for one case, cuz then i could say !num and that would essentially be my if/else statement. Don't confuse !num with !=num where the second is not allowed. != is a logical operation. ! is a binary. I hope someone smarter than me can help.
 02-07-2004, 06:32 PM #7 kev82 Senior Member   Registered: Apr 2003 Location: Lancaster, England Distribution: Debian Etch, OS X 10.4 Posts: 1,263 Rep: it assumes 32bit ints, i suppose your gonna tell me that another function is also cheating but i cant see how to keep it under 20 ops without using another function or a loop. Code: ```int a(unsigned int num, int bit) { return (num&(1<>bit; } int b(unsigned int x) { unsigned int count=0; x=~x; count += a(x, 0); count += a(x, 1); count += a(x, 2); count += a(x, 3); count += a(x, 4); count += a(x, 5); count += a(x, 6); count += a(x, 7); count += a(x, 8); count += a(x, 9); count += a(x, 10); count += a(x, 11); count += a(x, 12); count += a(x, 13); count += a(x, 14); count += a(x, 15); count += a(x, 16); count += a(x, 17); count += a(x, 18); count += a(x, 19); count += a(x, 20); count += a(x, 21); count += a(x, 22); count += a(x, 23); count += a(x, 24); count += a(x, 25); count += a(x, 26); count += a(x, 27); count += a(x, 28); count += a(x, 29); count += a(x, 30); count += a(x, 31); return count&1; }```
 02-07-2004, 06:49 PM #8 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: LOL, actually u can't call another function but I did forget to mention that you can use a constant of up int constant 255 (0000............0000 1111 1111). I sort of follow your logic, very creative and I think if I used it with a constant I could reduce the number of operations. Thank you very much.
 02-07-2004, 06:52 PM #9 Hko Senior Member   Registered: Aug 2002 Location: Groningen, The Netherlands Distribution: ubuntu Posts: 2,530 Rep: Sorry... aioss: Until you sent me an e-mail I assumed it was a "puzzle" like you said. Now I realize it actually is homework. I'm feeling stupid a second time in this thread, though a different way this time. I do like puzzles, but not doing somebodies homework. That's cheating from your part both ways:[list=1][*]to your school/college for getting higher grades by cheating.[*]to (ab)use the willingness to help of people here by calling your homework a "puzzle".[/list=1] kev82: No need for an seperate function. I suppose even assignment operator s like "+=" are not allowed. I solved it using only ( ) & ^ << in one big return statement, (aioss:here's some help to get you started anyway) Last edited by Hko; 02-07-2004 at 06:55 PM.
 02-07-2004, 07:01 PM #10 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: Im sorry if I made you feel that way. I was not trying to abuse the term puzzle, the program was called puzzles. Just as a habbit I called it that. I mention that a level 4 had been solved and all level 1,2, and 3's granting me an A on the hwk. I have an A in the class now. Cheating is not how I maintaing a GPA because when it comes time for an exam, they will know if you cheated or did it on your own. I should have stated for someone to make suggestions rather than solve it. I would prefer this. I think "+=" would be allowed. Once agian I am truly sorry to make you react the way you did, never my intention. But thanks for all you did.
02-07-2004, 07:11 PM   #11
Hko
Senior Member

Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep:
Quote:
 Originally posted by aioss I mention that a level 4 had been solved and all level 1,2, and 3's granting me an A on the hwk. I have an A in the class now.
OK. It's true that you did mention that in your e-mail. I didn't realize what that meant. Sounds fair enough; If you already have got an A, solveing the rest is like puzzilng. Sorry 'bout that.
Quote:
 [...] when it comes time for an exam, they will know if you cheated or did it on your own.
True. But some people do try here anyways.
Quote:
 Once agian I am truly sorry to make you react the way you did, never my intention.
Accepted.
Sorry I reacted a bit harsh on you. (feeling stupid a third time :-) )

Last edited by Hko; 02-07-2004 at 07:20 PM.

 02-07-2004, 07:22 PM #12 Hko Senior Member   Registered: Aug 2002 Location: Groningen, The Netherlands Distribution: ubuntu Posts: 2,530 Rep: Well... The solution I found would not validate I guess, because it uses 3 ops per bit. So, for 16 bit int's I would need 48 operators. Code: ```/* assuming 4 bits for brevity */ int bitParity(int x) { return ((x & 1) >> 0) ^ ((x & 2) >> 1) ^ ((x & 4) >> 2) ^ ((x & 8) >> 3); }``` Last edited by Hko; 02-07-2004 at 07:34 PM.
 02-07-2004, 07:34 PM #13 wapcaplet Guru   Registered: Feb 2003 Location: Colorado Springs, CO Distribution: Gentoo Posts: 2,018 Rep: Since I know it's homework, I'll just give a hint (for the first problem): Think about what happens when you XOR two equal-length numerals together, in particular what happens depending on whether you have an odd or even number of "1" bits in total. Now think of a good way to divide a long numeral (like 32 bits) into smaller pieces so you don't have to perform 32 steps on it in order to get an answer. btw, I am not too clear on why "+" is allowed... it's not really a binary operation (not bitwise, I mean). If + is allowed, why not -, *, / ?
 02-07-2004, 07:35 PM #14 aioss LQ Newbie   Registered: Oct 2003 Posts: 14 Original Poster Rep: I had a theory but it is a few days old. I noticed from my truth tables that all unsigned ints will end in one of these 15 combinations 0000, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111, and I would only need to test agianst half of them for even or odd, and could shift the first four bits into a variable but this would require logic so once agian im stuck.
02-07-2004, 07:52 PM   #15
wapcaplet
Guru

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

Rep:
Quote:
 Originally posted by aioss I had a theory but it is a few days old. I noticed from my truth tables that all unsigned ints will end in one of these 15 combinations 0000, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Well, all binary numerals end in one of those 16 combinations (you left out 0001), since there are only 16 possible outcomes for 4 bits.

By the way, all you need to do with the second problem is convert all the rest of the bits into two's complement form if the sign bit is 1. Converting them to two's complement form is easy if "+" is allowed (and only marginally harder if it isn't allowed). All you gotta do is find a way to do that based on the sign bit without using an "if".

Last edited by wapcaplet; 02-07-2004 at 07:55 PM.

 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 01:50 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -
 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.