仅使用按位运算符实现逻辑否定(除了!)

Question

~ & ^ | + << >> 是我可以使用的唯一操作

在我继续之前,这是一个功课问题,我已经坚持了很长时间.

我原来的方法:我认为!x可以用两个补码完成,并用它的加法逆做一些事情.我知道xor可能在这里,但我真的不知道如何处理这个问题.

为了记录:我也不能使用条件,循环==等,只能使用上面提到的函数(按位).

例如:

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

Answer 1

假设一个32位无符号int:

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

应该做的伎俩

Answer 2

假设x已签名，则对于任何非零的数字都需要返回0，而对于零则需要返回1。

在大多数实现中，有符号整数的右移通常是算术移位（例如，将符号位复制过来）。因此，右移x31并取反31。这两个数之一将为负数，因此右移31将为0xFFFFFFFF（当然，如果x = 0，则右移将产生0x0，这就是您想要的）。您不知道x或其负数是否为负数，因此只需将它们“或”在一起即可得到所需的结果。接下来加1和你的好。

实施：

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

Answer 3

假设例如 8 位无符号类型：

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