位操作，如果x！= 0，则返回0；否则，返回非零 [英] Bit manipulation, return 0 if x != 0, or nonzero otherwise

问题描述

我正在编写一个函数 is_zero ，如果 x！= 0 ，则应返回 0 ，否则返回非零.我不允许使用任何常量.例如，不允许 x == 0 .(也不允许==运算符)

I am writing a function is_zero that is supposed to return 0 if x != 0, or nonzero otherwise. I am not allowed to use any constants. For example, x == 0 is not allowed. (the == operator is not allowed either)

我唯一允许使用的运算符是 = ，〜， ^ ， * (取消引用)，& ， | ，<< ，>> 和 + .

The only operators I am allowed to use are =, ~, ^, * (dereferencing), &, |, <<, >> and +.

我现在编写函数的方式是，如果 x！= 0 ，它将返回 0 ，但即使在 x == 0 ，这是不应该的.我已经尝试了各种组合，但是考虑到约束条件，这个作业问题似乎是不可能的.我在这里发帖作为最后的努力.

The way I have the function written now is it will return 0 if x != 0, but it still returns 0 even when x == 0, which is it not supposed to do. I have attempted all sorts of combinations, but this homework question appears impossible given the constraints. I am posting here as a last ditch effort.

在 x == 0 的同时，我仍然可以返回 0 的任何人如何获取我的代码以返回 0 以外的内容当 x！= 0 ?

Can anybody how me how I can get my code to return something other than 0 when x == 0, while still returning 0 when x != 0?

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

推荐答案

事实证明，这里有一个通用的解决方案，它不取决于单词大小，甚至不取决于二进制补码算法.在这里:

It turns out there is a general solution, which does not depend on word size, or even on two's complement arithmetic. Here it is:

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

请注意，所有操作均以无符号方式完成，这是避免溢出问题以及强制向右填充至零填充所必需的.我将参数和返回值保留为带符号的整数，第一个和最后一个赋值只是更改了带符号/无符号的行为(最后的移位仅是为了避免溢出-请参阅下面的评论).

Note that everything is done in unsigned, which is necessary to avoid overflow issues, and also to force the right shift to zero-fill. I left the argument and return value as signed ints, with the first and last assignments simply changing the signed/unsigned behavior (the final shift is only present to avoid overflow - see the comment below).

该解决方案实际上非常简单.如已经指出的，恒定的生成是微不足道的.通过对其自身进行异或运算获得零.全1是其按位补码.一个是全1的异或，全1左移.

The solution is actually pretty straightforward. As has been noted, constant generation is trivial. Zero is obtained by xor-ing something with itself. All 1's is the bitwise complement of that. One is all 1's xor'd with all 1's shifted left one.

到目前为止，这一切都是微不足道的.棘手的部分是无论单词大小如何，它都能正常工作.为此，它构造一个值，如果x不为零，则其高阶位为0，如果x为零，则其值为1.然后，它使用在高位比特位置为单个1的常量对其进行掩盖，该常量由全1的异或与全1的右移1构成.移位保证为零填充(而不是符号扩展))，因为该值是无符号的.

So far this is all pretty trivial. The tricky part is to get it to work regardless of word size. To do this, it constructs a value whose high-order bit is 0 if x is non-zero, and 1 if x is zero. It then masks this with a constant which is a single 1 in the high-order bit position, which is constructed from all 1's xor'd with all 1's shifted right 1. The shift is guaranteed to zero-fill (rather than sign-extend) since the value is unsigned.

请注意， s 在高位位置为0或1.最终的返回值 r 将 s 右移一位，以避免在分配回有符号整数时发生溢出.保罗·汉金(Paul Hankin)提出了此解决方案.这样，最终的返回值要么为零，要么为零，然后为1，然后为全零.

Note that s is either zero or a one in the high-order bit position. The final return value, r, shifts s right by one in order to avoid overflow when assigning back to a signed integer. This fix was suggested by Paul Hankin. This makes the final return value either zero or else zero followed by one followed by all zeros.

如果要避免在函数的开始和结束之间在有符号和无符号之间进行隐式转换，可以使用联合对值进行别名:

If you want to avoid the implicit conversions between signed and unsigned at the beginning and end of the function, you can use a union to alias the values:

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 的最后移位，并且返回值要么为零，要么为1，后跟全零.请注意，C90标准不允许混合代码和声明，因此，如果这是一个问题，则必须将声明与赋值分开，但最终结果将是相同的.

In this case, the final shift of s is unnecessary, and the return value is either zero or else one followed by all zeros. Note that the C90 standard doesn't allow mixed code and declarations, so if that's an issue, you would have to separate the declarations from the assignments, but the net result would be the same.

这篇关于位操作，如果x！= 0，则返回0；否则，返回非零的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！