使用少于 5 个按位运算符实现 "logical not"

Question

作为我的 CS 类 的一部分，我最近完成了非常受欢迎的 "Data Lab" 作业。在这些作业中，您应该使用尽可能少的操作在 C 中实现简单的二进制操作。

对于那些不熟悉 "Data Lab" 规则的快速概述：

• 您不得调用函数、转换或使用控制结构（例如 if）
• 您可以在没有运算符成本的情况下分配变量，但只允许使用 int）
• 运算符越少越好
• 你可以假设 sizeof(int) == 32
• 负数用 2 的补码表示

任务是通过仅使用以下运算符来实现逻辑不调用 'bang'（其中 bang(x) returns !x）：~ & ^ | + << >>

函数原型定义为

int bang(int x)

我能找到的最佳实现（使用 5 个运算符）如下：

return ((x | (~x +1)) >> 31) + 1

然而，似乎有一种方法可以用更少的操作员来实现这一点，因为我从一些德国大学找到了一个结果网站[1]，其中两个人显然找到了一个少于 5 个操作员的解决方案。但我似乎无法弄清楚他们是如何做到这一点的。

[1] http://rtsys.informatik.uni-kiel.de/~rt-teach/ss09/v-sysinf2/dlcontest.html（逻辑负列）

澄清一下：这里不是说如何解决问题，而是如何用更少的操作解决问题。

Answer 1

为什么不只是:-

int bang(int x)
{
    return 1 >> x;
}

Answer 2

只是轻微作弊：

int bang(int x) {
    return ((x ^ 0xffffffffU) + 1UL) >> 32;
}

是我能想到的唯一方法，只需 3 次操作即可完成。假设一个 32 位 int 和 64 位 long...

Answer 3

如果您冒昧地假设 int 加法溢出是明确定义的并包装（而不是未定义的行为），那么有一个包含四个运算符的解决方案：

((a | (a + 0x7fffffff)) >> 31) + 1

我认为您假设溢出被定义为换行，否则您的函数 ((x | (~x + 1)) >> 31) + 1 对于 x=INT_MIN.

具有未定义的行为