如何在没有 * 或 - 运算符的情况下否定 C 中的正整数？

Question

你好，我正在尝试为我的实验室编写一个函数，它要求我使用受限运算符对正数取反。允许的运算符是：! ~ & ^ | + << 和 >>.

我最初的方法是使用加法将 x 加倍：x + x 然后从 x 中减去它以获得相反的值，但由于运算符限制而被阻碍。我是 C 的新手，正在努力学习，如果有人能向我提供执行此操作背后的想法，我将不胜感激。

Answer 1

这可能不是您的导师希望看到的，但它确实有效，与 ~ 运算符不同，它不依赖于实现（sign-magnitude、1-补码或 2-补），不会引起 UB。我 post 这个解决方案，因为它满足要求，但又丑又慢，因为我认为这个任务很愚蠢（这个任务导致的功能只能在使用 2-complement 的系统上工作，我敢打赌讲师会提出一个仅适用于 2-补码系统的解决方案）。

#include <limits.h>

//Returns the negative value of n,
//n has to be positive. Negative values of n cause UB.
int makeNegative(int n)
{
    int i=INT_MIN;
    while(i+n) //continue till i+n is 0, no need for the < operator
    {
        i++;
    }
    return i;
}

如果您希望代码在 n 为负时不会导致 UB，您可以检查 n:

的负值

#include <limits.h>

int isNegative(int n)
{
    int i=INT_MIN;
    while(i)
    {
        i++;
        if(n==INT_MAX) //when n reaches INT_MAX, it was positive
        {              //we need to check for it before increment
          return 0;    //increment a int of value INT_MAX would cause UB 
        }
        n++;
        if(!n) //n is 0 means n was negative before
        {
          return 1;
        }
    }
    return 0;
}

//Returns the negative value of n i n is positive
//returns n in any other case
int makeNegative(int n)
{
    if(isNegative(n))
    {
        return n;
    }
    int i=INT_MIN;
    while(i+n) //continue till i+n is 0, no need for the < operator
    {
        i++;
    }
    return i;
}

2-补码系统

正如其他人已经指出的，这可能是您的导师希望看到的：n=(~n)+1;。这仅在您使用 2 补码时有效，它会导致 INT_MIN.

的 UB

假设我们将数字 1 存储在变量 n 中。现在我们要否定n。然后我们必须反转变量，意味着我们翻转每一位然后添加 +1。这是一个 int8_t.

的例子

Value | Bit pattern |
    1 |  0b00000001 | n is set to 1
   -2 |  0b11111110 | We inverted n
   -1 |  0b11111111 | We added 1 to n

2 补码系统的优点是，我们可以对一个值使用每个可能的位模式，并且我们可以对 signed 和 unsigned 变量使用相同的逻辑来进行大多数操作.对于无符号变量，0b11111111 的二进制值是 0xFF==255。 C 标准要求无符号整数环绕。如果我们将 0xFF 存储在 uint8_t 变量中并添加 1，结果将无法存储在 uint8_t 中并返回到 0。意味着 0b11111111+1==0 .正如我们之前看到的，我们可以将值 -1 作为位模式 0b11111111 存储在 int8_t 中。在这里我们也得到 0b11111111+1==0 => -1+1==0.

2-补码系统的一个特点是负值比正值多一个。 INT8_MIN<-INT8_MAX。 INT8_MIN 有位模式 0b10000000，如果我们反转它，我们得到位模式 0b01111111==INT8_MAX。当我们现在添加 1 时，我们会发生溢出，并且溢出会导致带符号变量出现 UB*。因此，当 n 被签名时，语句 n=(~n)+1; 可能会导致 UB。 n=-n、n=n*-1 和 n=n/-1 也是如此，因为当 n 具有我们无法取反的最低可能值时，它们都会失败。

*当您告诉编译器对有符号变量使用环绕时，（-fwrapv 在 gcc 上），它会再次导致 INT8_MIN。

Answer 2

以下是您可能会产生的经典解决方案：

int negate_positive_number(int n) {
    return ~n + 1;
}

此代码的问题在于它仅适用于 2 的补码系统。这不是一个真正的问题，因为您今天可能不会遇到其他架构。

然而 C 标准支持其他有符号整数的表示：

sign/magnitude 其中负值设置了相同的值位但设置了符号位，
ones 的补码，其中负值的所有位都与正值的表示相反。

在这两个历史怪事中，0 有 2 种可能的表示形式，其中之一可能是陷阱值。

这是适用于所有 3 种架构的原始解决方案：2 的补码系统，sign/magnitude 和 1 的补码系统：有点晦涩但更便携：

#include <limits.h>

int negate_positive_number(int n) {
    return (n ^ INT_MIN ^ INT_MAX) + (1 & (INT_MIN + INT_MAX));
}

它使用 +、^ 和 & 以及 <limits.h> 中的定义，可能禁止。我假设也允许使用括号。

Answer 3

2补

int minus(int x)
{
    return ~x + 1;
}

测试：

https://godbolt.org/z/c89GWT

如何在没有 * 或 - 运算符的情况下否定 C 中的正整数？

How to negate a positive integer in C without * or - operators?

c

integer

operation

bit

bitwise-operators

2-补码系统