按位检查数字是否为-1

Question

我必须创建一个函数来检查输入数字是否为-1。这是要求

isTmin - returns 1 if x is the minimum, two's complement number, and 0 otherwise 
Legal ops: ! ~ & ^ | +
Max ops: 10
Rating: 1

首先我尝试这个：

int isTmin(int x) {
  return !(x^(0x01<<31));
}

这个方法有效，但我不允许使用移位运算符。有什么想法如何在不使用移位运算符的情况下解决这个问题？

Answer 1

int isTmin(unsigned x) {
    return !x ^ !(x+x);
}

请注意，您需要在 C 中使用

unsigned

来获得二进制补码数学和正确的包装 -

int

其实现/未定义。

Answer 2

如果它唯一需要检查的是它是否为 0xffff ffff，那么：

return x^0xffffffff == 0

仅当 x 也是

0xffffffff

时，这才是正确的。

Answer 3

这个问题来自CS:APP的datalab。我必须指出，问题问的是

x

是否是最小值，二进制补数（

0x80000000

），而不是

-1

（

0xffffffffff

），并且还有额外的规则：

INTEGER CODING RULES:

  Replace the "return" statement in each function with one
  or more lines of C code that implements the function. Your code
  must conform to the following style:

  int Funct(arg1, arg2, ...) {
      /* brief description of how your implementation works */
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

  Each "Expr" is an expression using ONLY the following:
  1. Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
  2. Function arguments and local variables (no global variables).
  3. Unary integer operations ! ~
  4. Binary integer operations & ^ | + << >>

  Some of the problems restrict the set of allowed operators even further.
  Each "Expr" may consist of multiple operators. You are not restricted to
  one operator per line.

  You are expressly forbidden to:
  1. Use any control constructs such as if, do, while, for, switch, etc.
  2. Define or use any macros.
  3. Define any additional functions in this file.
  4. Call any functions.
  5. Use any other operations, such as &&, ||, -, or ?:
  6. Use any form of casting.
  7. Use any data type other than int.  This implies that you
     cannot use arrays, structs, or unions.


  You may assume that your machine:
  1. Uses 2s complement, 32-bit representations of integers.
  2. Performs right shifts arithmetically.
  3. Has unpredictable behavior when shifting if the shift amount
     is less than 0 or greater than 31.

EXAMPLES OF ACCEPTABLE CODING STYLE:
  /*
   * pow2plus1 - returns 2^x + 1, where 0 <= x <= 31
   */
  int pow2plus1(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     return (1 << x) + 1;
  }

  /*
   * pow2plus4 - returns 2^x + 4, where 0 <= x <= 31
   */
  int pow2plus4(int x) {
     /* exploit ability of shifts to compute powers of 2 */
     int result = (1 << x);
     result += 4;
     return result;
  }

可以解决该问题的可能表达式如下：

(!(x + x)) & (!!x)

让我解释一下这个表达式是如何构造的：

为了便于表示，我们将数字的原始 32 位表示简化为 4 位。这样，最小互补数以二进制表示为

1000

。

我们要判断给定的

x

是否为

1000

，如果是则返回1，否则返回0。

我们可以发现，只有两种情况下

x + x

会导致

0000

。

1. x

   =

   0000

2. x

   =

   1000

   （实际结果应该是

   10000

   ，但是由于溢出导致最高位丢失，所以结果是

   0000

   ）

所以，只要满足以下两个条件，

x

就是

1000

。

1. x != 0000

2. x + x == 0000

然后我们可以构造表达式

(!(x + x)) & (!!x)

。

但是，我无法像这样通过这个问题（在我的电脑中，使用 gcc 11.4.0）：

int isTmin(int x) {
  return (!(x + x)) & (!!x);
}

我检查了gcc生成的原始汇编代码，似乎如果直接使用上面的这个表达式，gcc会进行某种优化来使其：

movl $0, %eax

我不知道为什么会发生这种情况。有问题的表达式是

x + x

，当我将其标记为

volatile

时，它起作用了：

int isTmin(int x) {
  volatile int sum = x + x;
  return !sum & !!x;
}