LinuxQuestions.org
Review your favorite Linux distribution.
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, 02:38 PM   #1
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Rep: Reputation: 0
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 04:01 PM.
 
Old 02-07-2004, 04:16 PM   #2
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

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

Original Poster
Rep: Reputation: 0
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.
 
Old 02-07-2004, 04:40 PM   #4
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep: Reputation: 108Reputation: 108
Yes, I understand, see my <edit> that I did at the same time as your post.
 
Old 02-07-2004, 04:50 PM   #5
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep: Reputation: 108Reputation: 108
Are loops (for / while) allowed?
 
Old 02-07-2004, 04:58 PM   #6
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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.
 
Old 02-07-2004, 05:32 PM   #7
kev82
Senior Member
 
Registered: Apr 2003
Location: Lancaster, England
Distribution: Debian Etch, OS X 10.4
Posts: 1,263

Rep: Reputation: 50
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))>>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;
}
 
Old 02-07-2004, 05:49 PM   #8
aioss
LQ Newbie
 
Registered: Oct 2003
Posts: 14

Original Poster
Rep: Reputation: 0
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.
 
Old 02-07-2004, 05:52 PM   #9
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

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

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

Rep: Reputation: 108Reputation: 108
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 06:20 PM.
 
Old 02-07-2004, 06:22 PM   #12
Hko
Senior Member
 
Registered: Aug 2002
Location: Groningen, The Netherlands
Distribution: ubuntu
Posts: 2,530

Rep: Reputation: 108Reputation: 108
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 06:34 PM.
 
Old 02-07-2004, 06:34 PM   #13
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

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

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

Rep: Reputation: 48
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 06:55 PM.
 
  


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 03:43 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