位操作，return 0 如果 x != 0，否则非零

Question

我正在编写一个函数 is_zero 如果 x != 0 则应该 return 0 否则非零。我不允许使用任何常量。例如，x == 0 是不允许的。（也不允许使用 == 运算符）

我唯一可以使用的运算符是 =、~、^、*（取消引用）、&、|、<<、>> 和 +.

我现在编写函数的方式是 return 0 如果 x != 0，但它仍然 returns 0 即使 x == 0，这是不应该做的。我尝试了各种组合，但考虑到限制，这个家庭作业问题似乎是不可能的。我在这里发帖作为最后的努力。

任何人都可以告诉我如何让我的代码在 x == 0 时 return 除了 0 之外的其他东西，而在 returning 0 时x != 0?

int is_zero(int x) {
    return (x ^ x);
}

Answer 1

如果您希望代码在不假设 int 的特定大小和表示形式的情况下工作，我认为不可能解决这个问题。但这适用于 32 位整数和二进制补码表示：

int is_zero(int x) {
    int zero = (x^x);
    int one = ~(~zero + ~zero);
    int five = one + one + one + one + one;
    int thirtyone = (one << five) + ~zero;
    return ~((x >> thirtyone) | ((~x + one) >> thirtyone));
}

它使用多个赋值来构造常量，但如果需要，代码可以折叠成一个表达式。

工作原理

(x >> thirtyone) 如果 x 为负则为 -1，否则为 0。同样，如果 x 为正，则 (~x + one) >> thirtyone 为 -1，否则为 0。

如果 x 为零，则这两个表达式的按位 or 为 0，否则为 -1。如果 x 为零，则按位 ~ 给出 -1，否则给出 0。

（差不多）字长独立解

它不是完全独立于字长的，但是可以扩展上面的解决方案以适用于 16、32 和 64 位整数（尽管仍然取决于二进制补码表示）。代码小心不要一次移动超过 15 位（否则如果 int 是 16 位，结果是未定义的行为）：

int is_zero(int x) {
    int zero = (x^x);
    int one = ~(~zero + ~zero);
    int four = one + one + one + one;
    int k15 = (one << four) + ~zero;
    return ~((x >> k15 >> k15 >> k15 >> k15 >> k15) |
             ((~x + one) >> k15 >> k15 >> k15 >> k15 >> k15));
}

Answer 2

请注意，这建立在@Paul Hankin 关于如何将 0 和 1 作为常量的回答的基础上。（如果你被允许使用“/”运算符，1 将更容易通过（x/x）获得。因此，一种理论上的方法可能是

按照@PaulHankin 的回答获取常量 0 和 1（很好，顺便说一句）
使用这些 "constants"，将 x 向左移动所有可能的位位置，对结果进行或运算（将原始中的任何“1”移动到任何可能的位位置，最后给出 -1（0xffff）。由于我们似乎不知道整数的大小，为了安全起见，请重复 64 次或 128 次（或 1000 次）甚至更多次，并涵盖所有合理的 int 大小。（该行可能会变成有点长...）增加太多班次不会有什么坏处。

x = x | x << one | x << one+one | x << one + one + one ....

如果移位大于实际字宽，这实际上可能以 UB 结束，但通过写入修复（感谢@PaulHankin 的评论）

x = x | x << one | x << one << one | x << one << one << one ....

如果 x 最初是 0，那么现在 x 中将有一个 0。如果它设置了任何位（即不同于 0），则您在最初设置的一组之上有任何位。
做同样的事情向右移动，你会得到 0xffff（或者任何你的字长）或者 0，然后
XOR 上面的结果与 -1（从 0 - 1 中作为常量获得）- 这将导致原始 0 为 -1，原始任何其他结果为 0，return，在最后.

我很确定我不想编写那个程序。它可能很容易超出编译器的任何合理行长度。

Answer 3

原来有一个通用的解决方案，它不依赖于字的大小，甚至不依赖于二进制补码算法。这是：

int is_zero(int x)
{
    unsigned    y   = x;
    unsigned    c0  = y^y;
    unsigned    c1  = ~(~c0 + ~c0);
    unsigned    c1h = ~c0 ^ (~c0 >> c1);
    unsigned    y2  = y + ~c0;
    unsigned    t1  = y ^ y2;
    unsigned    t2  = t1 & y2;
    unsigned    s   = t2 & c1h;
    int         r   = s >> c1;

    return r;
}

请注意，所有内容均以无符号形式完成，这是避免溢出问题所必需的，也是强制右移零填充的必要条件。我将参数和 return 值保留为带符号的整数，第一个和最后一个赋值只是改变了 signed/unsigned 行为（最后一个移位只是为了避免溢出——见下面的评论）。

解决方案实际上非常简单。如前所述，恒定生成是微不足道的。零是通过与自身进行异或运算获得的。全 1 是它的按位补码。一个是全 1 的异或，全 1 左移一个。

到目前为止，这一切都是微不足道的。棘手的部分是不管字的大小如何让它工作。为此，它构造一个值，如果 x 非零，则其高位为 0，如果 x 为零，则其高位为 1。然后它用一个常量屏蔽它，该常量是高位位置中的单个 1，它由所有 1 的异或运算和所有 1 的右移 1 构成。移位保证为零填充（而不是符号扩展) 因为该值是无符号的。

请注意，s 在高位位置为零或一。最后的 return 值 r 将 s 右移一位，以避免在分配回有符号整数时溢出。此修复由 Paul Hankin 建议。这使得最终的 return 值要么为零，要么为零，然后是一个，然后是全零。

如果你想避免函数开头和结尾的有符号和无符号之间的隐式转换，你可以使用联合来为值取别名：

int is_zero(int x)
{
    union {int s; unsigned u;} su;
    su.s = x;
    unsigned    y   = su.u;
    unsigned    c0  = y^y;
    unsigned    c1  = ~(~c0 + ~c0);
    unsigned    c1h = ~c0 ^ (~c0 >> c1);
    unsigned    y2  = y + ~c0;
    unsigned    t1  = y ^ y2;
    unsigned    t2  = t1 & y2;
    unsigned    s   = t2 & c1h;
    su.u = s;
    int         r = su.s;

    return r;
}

在这种情况下，s 的最终移位是不必要的，并且 return 值要么是零，要么是一个后跟全零。请注意，C90 标准不允许混合代码和声明，因此如果这是一个问题，您必须将声明与赋值分开，但最终结果是相同的。

Answer 4

@TomKarzes 回答的小优化：

int is_zero2(int x)
{
    unsigned y   = x;             // use (unsigned) x
    unsigned c0  = y ^ y;         // = 0
    unsigned c1  = ~(~c0 + ~c0);  // = 1
    unsigned c1h = ~(~c0 >> c1);  // = mask for sign bit
    unsigned t2  = ~(y | -y);     // mask for bits below (not including) lowest bit set
    unsigned s   = t2 & c1h;      // sign bit: 0 = (x != 0), 1 = (x == 0)
    int      r   = s >> c1;       // prevent overflow
    return r;
}

位操作，return 0 如果 x != 0，否则非零

Bit manipulation, return 0 if x != 0, or nonzero otherwise

c

bitwise-operators

工作原理

（差不多）字长独立解