使用少于5个按位运算符实现"逻辑非"

Question

作为我的CS课程的一部分,我最近完成了非常受欢迎的"数据实验室"作业.在这些分配中,您应该使用尽可能少的操作在C中实现简单的二进制操作.

对于那些不熟悉"数据实验室"的人,可以快速了解规则:

• 您不能调用函数,强制转换或使用控制结构(例如,如果)
• 您可以分配没有运营商成本的变量,但只允许使用int)
• 您使用的运营商越少越好
• 您可以假设sizeof(int)== 32
• 负数用2的补码表示

任务是通过仅使用以下运算符来实现一个不称为'bang'的逻辑(其中bang(x)返回!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(logicalNeg专栏)

澄清:这不是关于如何解决问题,而是如何用较少的操作来解决问题.

Answer 1

只是轻微作弊:

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

是我能想到的只有3个操作的唯一方法.假设32位int和64位长...