LinuxQuestions.org
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page

LinuxQuestions.org (/questions/)
-   Programming (https://www.linuxquestions.org/questions/programming-9/)
-   -   Binary Puzzle (https://www.linuxquestions.org/questions/programming-9/binary-puzzle-143398/)

aioss 02-07-2004 02:38 PM
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. ! ~ & ^ | + << >>

Hko 02-07-2004 04:16 PM
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>

aioss 02-07-2004 04:21 PM
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.

Hko 02-07-2004 04:40 PM
Yes, I understand, see my <edit> that I did at the same time as your post.

Hko 02-07-2004 04:50 PM
Are loops (for / while) allowed?

aioss 02-07-2004 04:58 PM
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.

kev82 02-07-2004 05:32 PM
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;
}

aioss 02-07-2004 05:49 PM
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.

Hko 02-07-2004 05:52 PM
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)

aioss 02-07-2004 06:01 PM
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.

Hko 02-07-2004 06:11 PM
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 :-) )

Hko 02-07-2004 06:22 PM
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);
}

wapcaplet 02-07-2004 06:34 PM
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 -, *, / ?

aioss 02-07-2004 06:35 PM
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.

wapcaplet 02-07-2004 06:52 PM
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".


All times are GMT -5. The time now is 08:07 PM.
Page 1 of 2 1 2
Show 50 post(s) from this thread on one page