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.

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 :(

Code:

---

int mask(int & price)
{
    int free = 1024;
    free = free & price;
    free = free << 31;
    return free
}

---

I cant think please don't ban me.

Hint: think divide and conquer.

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.

Ohh damit signed means positive, unsigned either or. I give just call me Newb as I try to learn.

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.

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.

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)

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.