如何判断32位整数能否适应16位短整型

Question

仅使用以下内容：

! ~ & ^ | + << >>

我需要找出一个有符号的 32 位整数是否能表示为一个 16 位的带符号整数（two's complement integer）。

我的第一个想法是将 MSB 的 16 位和 LSB 的 16 位分开，并使用掩码对最后的 16 位进行 AND 运算。如果结果不为零，它就无法被表示，并使用该数字检查 MSB 位。

需要编写的函数示例为：fitsInShort(33000) = 0（无法表示），fitsInShort(-32768) = 1（可以表示）。

- Vishal

Answer 1

如果一个32位数字在范围[-32768，+32767]内，则其前17位均相同。

以下是一种使用操作符判断3位数字是否全为零或全为1的差劲方法（假设不允许条件控制结构，因为它们需要隐式逻辑运算符）。

int allOnes3(int x)
{
    return ((x >> 0) & (x >> 1) & (x >> 2)) & 1;
}

int allTheSame3(int x)
{
    return allOnes3(x) | allOnes3(~x);
}

我会让你去扩展/改进这个概念。

- Oliver Charlesworth

Answer 2

bool fits16(int x)
{
    short y = x;
    return y == x;
}

开个玩笑，:) 下面是真正的答案，假设int是32位，short是16位，使用二进制补码表示：

编辑：请看最后一次编辑获取正确答案！

bool fits16(int x)
{
    /* Mask out the least significant word */
    int y = x & 0xffff0000;
    if (x & 0x00008000) {
        return y == 0xffff0000;
    } else {
        return y == 0;
    }
}

我相信没有if语句，这应该可以做到：

return (
    !(!(x & 0xffff0000) || !(x & 0x00008000)) ||
    !((x & 0xffff0000) || (x & 0x00008000))
);

编辑：Oli是正确的。我不知怎么想到他们是被允许的。这是最后一次尝试，附有解释：

我们需要x的17个最高有效位要么都是1，要么都是0。因此，让我们开始通过掩码屏蔽其他位：

int a = x & 0xffff8000; // we need a to be either 0xffff8000 or 0x00000000
int b = a + 0x00008000; // if a == 0xffff8000 then b is now 0x00000000
                        // if a == 0x00000000 then b is now 0x00008000
                        // in any other case b has a different value
int c = b & 0xffff7fff; // all zeroes if it fits, something else if it doesn't
return c;

更简洁地说：

return ((x & 0xffff8000) + 0x8000) & 0xffff7fff;

- cyco130

---

我也不能使用if语句。我需要一个全是0的东西来适配，以及另外一个不适配的东西，这样我就可以取反数字并得到0或1了。 - Vishal

刚刚编辑过。如果我没记错的话，!(!a || !b) == (a && b)。或者类似这样的东西... - cyco130

OP没有提到逻辑运算符(&&, ||)。 - Oliver Charlesworth

@Vishal：您已经接受了这个答案，但是您的问题中没有提到逻辑运算符（&&或||）。 - Oliver Charlesworth

因此，如果适合，则最后一个案例的答案为0，即否定（doesntFit16），并且它具有一个不必要的操作。我只会编写#define fits16(x) (!(((unsigned)(x)+0x8000U) & OxFFFF0000U))。 - aka.nice

Answer 3

如果不想使用强制类型转换、if语句，只使用你所要求的运算符，以下是一种解决方案：

#define fitsInShort(x) !(((((x) & 0xffff8000) >> 15) + 1) & 0x1fffe)

- Emil Romanus

---

聪明的回答。如果您能解释为什么它有效，那将有助于提问者 :) - qdot

我注意到被接受的答案者在被接受后采纳了我的想法并将其添加到他的答案中。如果不是因为他改进了它，这将是可耻的。位移是不必要的，可以用+0x8000和另一个掩码来替换。请参阅他关于为什么这样做的解释。基本思路是隔离应该是全部为0或全部为1的位，然后加上+1。如果数字合适，那么必须是(-1)+1或0+1，因此如果结果数字&0xfffe为0（忽略最后一位），则数字合适。 - Emil Romanus

Answer 4

short fitsInShort(int x)
{
    int positiveShortRange = (int) ((short) 0xffff / (short) 2);
    int negativeShortRange = (int) ((short) 0xffff / (short) 2) + 1;

    if(x > negativeShortRange && x < positiveShortRange)
        return (short) x;
    else
        return (short) 0;
}

- BlackBear

---

这个问题有一些人为的限制，规定了允许使用哪些操作。 - Oliver Charlesworth

@Oli Charlesworth：我们的解决方案是相同的，但你在时间上赢了我。你的解决方案还检查了 x > -32768 && x < 32767。 - BlackBear

Answer 5

if (!(integer_32 & 0x8000000))
{
   /* if +ve number */
  if (integer_32 & 0xffff8000)
    /* cannot fit */
  else 
    /* can fit */
}
else if (integer_32 & 0x80000000)
{
  /* if -ve number */
  if ( ~((integer_32 & 0xffff8000) | 0x00007fff))
    /* cannot fit */
  else
    /* can fit */
}

首先，通过检查有符号位来检查正数。如果是正数，则检查位15到位31是否为0，如果为0，则无法适应short，否则可以。

如果位15到31全部设置（2的补码表示方法），则负数在范围内。

因此，第二个if是一个负数，然后屏蔽掉位15到31，剩余的低位（0到14）被设置。如果这是0xffffffff，那么只有一的补码将是0，这表示位15到31全部设置，因此它可以适应（else部分），否则它不能适应（if条件）。

- phoxis

---

不处理负数。 - Oliver Charlesworth