Implementing logical negation with only bitwise operators (except !)

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

Before I continue, this is a homework question, I've been stu开发者_开发技巧ck 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

Assuming a 32 bit unsigned int:

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

should do the trick

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;
}

The following code copies any 1 bit to all positions. This maps all non-zeroes to 0xFFFFFFFF == -1, while leaving 0 at 0. Then it adds 1, mapping -1 to 0 and 0 to 1.

x = x | x << 1  | x >> 1
x = x | x << 2  | x >> 2
x = x | x << 4  | x >> 4
x = x | x << 8  | x >> 8
x = x | x << 16 | x >> 16

x = x + 1

For 32 bit signed integer x

// Set the bottom bit if any bit set.
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;

x ^= 1;   // Toggle the bottom bit - now 0 if any bit set.
x &= 1;   // Clear the unwanted bits to leave 0 or 1.

Assuming e.g. an 8-bit unsigned type:

~(((x >> 0) & 1)
| ((x >> 1) & 1) 
| ((x >> 2) & 1)
...
| ((x >> 7) & 1)) & 1

You can just do ~x & 1 because it yields 1 for 0 and 0 for everything else