确定32位整数的符号

Question

仅使用以下符号：

! ~ & ^ | + << >>

不使用循环

我需要确定32位整数的符号，并且需要返回1表示正数，0表示0和-1表示负数。

有什么想法吗？我最初考虑将31个位移，然后查看该符号，但显然这种方法行不通，现在我有点卡住了。

- Peter

---

我只能判断它是否为负数。如果是0，则该数字可能全为零，也可能为正数，但我将这些位移开了。 - Peter

@Oli：它不具备可移植性，因为对负值进行右移位的结果是实现定义的，并且没有要求它*既0填充又符号填充。话虽如此，在实践中它会起作用，因为几乎所有的实现都会执行其中之一。 - Steve Jessop

请注意，!和+都不是位运算符。 - Oliver Charlesworth

@Steve：我想你可以先转换为无符号类型。不过我不知道这是否符合任意限制条件。 - Oliver Charlesworth

你可以执行例如 if (!x) return 0; 这样的操作吗？ - Tom Zych

Answer 1

如果允许条件语句（而不是if语句）和减法，最简单且更清晰的解决方案（在我看来）是:

int sign = (v > 0) - (v < 0);

不使用减法（并假设int是32位）：

#include <stdio.h>
#include <assert.h>
#include <limits.h>

int process(int v) {
    int is_negative = (unsigned int)v >> 31; // or sizeof(int) * CHAR_BIT - 1
    int is_zero = !v;
    int is_positive = !is_negative & !is_zero;
    int sign = (is_positive + ~is_negative) + 1;
    return sign;
}

int main() {
    assert(process(0) == 0);
    printf("passed the zero test\n");
    for (int v = INT_MIN; v < 0; v++) {
        assert(process(v) == -1);
    }
    printf("passed all negative tests\n");
    for (int v = 1; v < INT_MAX; v++) {
        assert(process(v) == +1);
    }
    printf("passed all positive tests\n");
    return 0;
}

以下是结果：

$ gcc -o test test.c -Wall -Wextra -O3 -std=c99 && ./test && echo $#
passed zero test
passed all negative tests
passed all positive tests
0

- jweyrich

---

问题指定不使用循环。全大写。 - Carey Gregory

@Carey：在投票之前，请先理解代码。请注意，循环只是为了提供输入值（v）以测试算法。 - jweyrich

我理解这段代码。如果你的解决方案只涉及位运算符，就像问题所要求的那样，我不会提到它。 - Carey Gregory

@Carey：我将它拆分成一个单独的函数，以使其更加清晰。希望这可以帮到你。 - jweyrich

请展示给我那个需求（仅使用位运算符）。我在问题中没有看到它。到目前为止，您提出了两个不同的论点，但都是无效的。 - jweyrich

@Carey：没关系，不要介意 :) - jweyrich

Answer 2

试试这个：

(x >> 31) | (((0 - x) >> 31) & 1)

这个怎么样：

(x >> 31) | (((~x + 1) >> 31) & 1)

编辑2：

针对评论中提出的问题（或者更确切地说是挑剔）...

这些解决方案需要满足以下假设条件才能有效：

1. x的类型为32位有符号整数。
2. 在这个系统上，有符号的32位整数是二进制补码。 （右移是算术操作）
3. 算术溢出时会发生环绕。
4. 对于第一个解决方案，文字字面量0与x相同类型。

- Mysticial

---

这是否依赖于 >> 当左操作数为负数时的特定行为？ - Oliver Charlesworth

“-” 不在允许的运算符列表中，对吗？ - Jens Gustedt

如果我们没有二进制补码，那么这个问题几乎是无解的，不是吗？我的意思是，我们必须对“负数”做出一些假设，对吧？ - Kevin

这是错误的。对于负数x，x>>31的结果在实现中是有定义的，不能保证它的值是什么。在符合C标准的实现中，所有负数x的值可能为0。但我认为这是问题的缺陷——我强烈怀疑（a）期望的答案使用了一个不可移植的>>运算符，以及（b）实际提问的问题没有解决方案。所以不要点踩。 - Steve Jessop

@Mystica：有符号整数溢出是未定义行为，应始终视为有害。说实话，我不知道他们现在在学校里教什么，当年我们读的是标准。是的，我很暴躁和老，甚至没有借口说，在我的年代，那时候甚至没有标准;-) - Steve Jessop

Answer 3

为什么需要使用位运算符来实现这个功能？

int get_sign(int value)
{
    return (value < 0) ? -1 : (int)(value != 0);
}

如果您必须使用位运算符，那么您可以使用&运算符来检查负值，无需移位：

int get_sign(int value)
{
    return (value & 0x80000000) ? -1 : (int)(value != 0);
}

如果您想要切换：

int get_sign(int value)
{
    return ((value >> 31) & 1) ? -1 : (int)(value != 0);
}

- Remy Lebeau

Answer 4

有一个稍微复杂一些的方法，如下所示：

(~((x >> 31) & 1) + 1) | (((~x + 1) >> 31) & 1)

这应该解决了移位时填充1还是0的歧义问题。

具体来说，我们在任何出现以下结构的地方：

(z >> 31) & 1

当输入为负数时，结果为1，其他情况下结果为0。

任何出现以下内容的地方：

(~z + 1)

我们得到了负数(-z)。

因此，如果x是负数，第一半将产生结果0xFFFFFFFF(-1)，如果x是正数，则第二半将产生0x00000001(1)。将它们进行按位或运算，就会产生一个0x00000000(0)的结果，如果两者都不成立。

- tdk001

Answer 5

假设实现定义了算术右移：

(x>>31) | !!x

与Mystical的回答不同，这里没有未定义行为。

如果您还想支持将右移定义为算术移位的系统：

~!(x>>31)+1 | !!x

编辑：对不起，我在第二个版本中漏掉了一个！。应该是：

~!!(x>>31)+1 | !!x

这个版本仍然依赖于实现是二进制补码并具有算术或逻辑右移的情况，即如果实现定义的行为完全不同，则可能会出现问题。但是，如果将类型更改为无符号类型，则所有实现定义的行为都消失了，结果取决于x的“符号”（高位和零/非零状态），可以是-1U、0U或1U。

- R.. GitHub STOP HELPING ICE

---

目前为止，+1 是最优雅的解决方案，尽管它不是真正的解决方案，因为它仍然取决于架构提供的右移类型。难道不能将两者合并为一个唯一的解决方案吗？ - Jens Gustedt

在C99中，带有负值的有符号整数的右移行为是未指定的。顺便说一下，你的第二个示例缺少一些括号吗？ - jweyrich

@jweyrich：它不是未指定的，而是实现定义的。在实践中，我们知道我们关心的所有实现都是算术或逻辑右移（如果未指定，它们甚至不必保持一致，但它们必须定义结果，并且可以理解地他们似乎总是选择其中之一）。原则上，实现可以定义-1 >> 1 == 0，这就是为什么我认为无法在没有某些额外假设的情况下解决该问题的原因。当然，说明这些假设可能是作业的一部分。 - Steve Jessop

第二个表达式似乎对于 0 没有给出正确的答案。 - Steve Jessop

打字错误，或者至少我会把它作为我的逻辑错误的借口。 :-) 现在已经修复了。 - R.. GitHub STOP HELPING ICE

Answer 6

我不确定这是绝对理想的做法，但我认为它相当可移植，并且至少比你之前的方法要简单一些：

#define INT_BITS 32

int sign(int v) { 
    return (!!v) | -(int)((unsigned int)v >> (INT_BITS-1));
}

- Jerry Coffin

---

@Mysticial：有一个小问题：在这个问题上实际上不允许使用“-”，因此从技术上讲，它并不真正被允许作为这个问题的答案。 - Jerry Coffin

Answer 7

这个怎么样：

int getsign(int n)
{
  return (!!n) + (~((n >> 30) & 2) + 1);
}

..对于32位有符号整数，只使用2的补码。

!!n会在n非零时返回1。 ((n >> 30) & 2)会在高位（符号位）设置时返回2。按位取反和+1将其2的补码计算出来，得到-2或0。 加法计算为负值时返回-1（1 + -2），零时返回0（0 + 0），正值时返回+1（1 + 0）。

- Dmitri

Answer 8

Dimitri的想法可以简化为(!!x) - ((x >> 30) & 2)

再给出一个神秘的解决方案：

~!x & ((-((unsigned) x >> 31)) | !!x)

- Holger