# Tough Bitwise Exercise

• 09-07-2005
Charmy
Tough Bitwise Exercise
I am just lost on this one, its got me baffled.

A function is passed a Signed 32 bit integer.
This function must return EXACTLY 1 or 0 (i.e. it returns int not bool)
You are allowed to use the following bitwise operations a maxium of 10 times.
Code:

` Legal ops: ~ & ^ | + << >>`
You can create as many Variables as needed, and can use the assignment operator as many times as needed.

You cannot use any conditional operators (if() ()?: while() for() etc...)

Detect if the given integer is non-zero or 0.

Essentially use only bitwise operations and return an integer that is either 1 or 0 to indicate if the passed integer is non zero or not.

Now i have personally had a very tough time with this one, and if anyone has any idea how to solve it, or an idea on how to do it, please share =).

Good luck :confused:

EDIT: The Biggest problem i am having is that with only 10 operations i can't find a (foolproof) way to check enough bits to ensure i won't miss one on the odd chance that said number falls on the single bit i don't check.

Thanks again for any info.
• 09-07-2005
valis
Can you use -, I see + so just double checking?

(value - 0x01010101) & ~value & 0x80808080) + 1 ; should work, I guess you could also set a negative and add that. That checks a single word for a 0, so do that shift right 16, do it again, and then or the two and return.

oh, I lied, keep searching :(
• 09-07-2005
curlious
Code:

```int mask(int & price) {     int free = 1024;     free = free & price;     free = free << 31;     return free }```
I cant think please don't ban me.
• 09-07-2005
Rashakil Fol
Hint: think divide and conquer.
• 09-07-2005
curlious
oh hell a hint, I guess you dont want to tell us :D

I wasn't thinking and I didn't see it was signed so this means it can be in twos compliment. lets see 11 = -3 ? and 011 = 3 correct.

Help me out am I way off.
• 09-07-2005
curlious
Ohh damit signed means positive, unsigned either or. I give just call me Newb as I try to learn.
• 09-07-2005
Rashakil Fol
Quote:

Originally Posted by valis
Can you use -, I see + so just double checking?

(value - 0x01010101) & ~value & 0x80808080) + 1 ; should work, I guess you could also set a negative and add that. That checks a single word for a 0, so do that shift right 16, do it again, and then or the two and return.

edit: my writing may have been cryptic so:
ret = (value - 0x01010101) & ~value & 0x80808080) + 1 ;
value >>= 16 ;
ret |= (value - 0x01010101) & ~value & 0x80808080) + 1;

8 bitwise operators in total.

I think the original question was worded so that only the listed operators are allowable. Above I see -, &, ~, &, +, >>, |, -, &, ~, &, and +, in that order from left to right. (Only = is allowed in the problem, so I treat |= and >>= as operators.) Subtraction is tolerable, but that's more than ten operators.

Also, your code does not seem to work for me, but I'm guessing where you want an open parenthesis placed.
• 09-08-2005
Charmy
Thanks for all the respones, - is a vaild operator sorry i forgot it. As for the code posted, it doesn't work for me either, i get a constant -2134252232 or somthing. Any all good thoughts up to this point, i will continue to work on it.
• 09-08-2005
valis
yeah, it worked at first (actually I must have only thought it worked), it came from a set of really useful bit manipulation sites I have bookmarked:
http://graphics.stanford.edu/~seander/bithacks.html
http://aggregate.org/MAGIC/

At the bottom of both sites they have more links, hope that helps :confused:

edit: I have no idea what I initially did because I can't reproduce it, but it would always result in 0 or -1 (that's what the + 1 was for)
• 09-08-2005
Charmy
well you can easily get that on Odd numbers.

return(value<<31)>>31;

This will return 0 on even and -1 on odd, but i need 0 on 0 and 1 on all all non zero numbers.

Thanks for the links i will check them out.