Implementing logical negation with only bitwise operators (except !)

Question

~ & ^ | + << >> are the only operations I can use

Before I continue, this is a homework question, I've been stuck on this for a really long time.

My original approach: I thought that !x could be done with two's complement and doing something with it's additive inverse. I know that an xor is probably in here but I'm really at a loss how to approach this.

For the record: I also cannot use conditionals, loops, ==, etc, only the functions (bitwise) I mentioned above.

For example:

!0 = 1
!1 = 0
!anything besides 0 = 0

Answer 1

Assuming a 32 bit unsigned int:

(((x>>1) | (x&1)) + ~0U) >> 31

should do the trick

Answer 2

Assuming x is signed, need to return 0 for any number not zero, and 1 for zero.

A right shift on a signed integer usually is an arithmetical shift in most implementations (e.g. the sign bit is copied over). Therefore right shift x by 31 and its negation by 31. One of those two will be a negative number and so right shifted by 31 will be 0xFFFFFFFF (of course if x = 0 then the right shift will produce 0x0 which is what you want). You don't know if x or its negation is the negative number so just 'or' them together and you will get what you want. Next add 1 and your good.

implementation:

int bang(int x) {
    return ((x >> 31) | ((~x + 1) >> 31)) + 1;
}