c - 面试-位操作

Question

我被要求实现 invert(x,p,n) 返回 x 的 n 位开始于位置 p 反转(即 1 变为 0，反之亦然)，其他不变。

我的解决方案是:

unsigned invert(unsigned x, int p, int n)
{
       return (x ^ (((1 << (n + 1)) - 1) << (p - n + 1)));
}

我在网上找到了这个问题的解决方案:

unsigned invert(unsigned x, int p, int n)
{
    return x ^ ((~(~0<<n))<< p+1-n);
}

对我来说它看起来不正确 - 解决问题的正确有效方法是什么

Answer 1

好吧，你的实现显然是不正确的；考虑 p = 1, n = 2:

x ^ (((1 << (n + 1)) - 1) << (p - n + 1))
x ^ (((1 << 3) - 1) << 0)
x ^ ((8 - 1) << 0)
x ^ 7

这会反转 x 的三个低位，而不是两个。我们可以通过使用以下方法来解决这个问题:

return x ^ (1 << n) - 1 << p - n + 1;

(我也去掉了很多虚假的括号)。这仍然有一个极端情况的错误；如果调用者想要翻转除了一个位以外的所有位(即 n == sizeof x * CHAR_BIT - 1)。让我们假设 int 是 32 位并举个例子:

x ^ (1 << n) - 1 << p - n + 1;
x ^ (1 << 31) - 1 << p - 31 + 1;
    ^^^^^^^^^
    ruh-roh!

不幸的是，这会调用未定义的行为(C11，§6.5.7 第 4 段):

If E1 has a signed type and nonnegative value, and E1 × 2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.

您可以通过使常量 1 无符号来修复这个 ...

return x ^ (1U << n) - 1 << p - n + 1;

...但是当 n == sizeof x * CHAR_BIT 时，您仍然有未定义的行为(即，如果调用者想要翻转所有 位)(C11，§6.5.7 第 3 段):

If the value of the right operand ... is greater than or equal to the width of the promoted left operand, the behavior is undefined.

您在网上找到的解决方案以同样的方式存在未定义的行为。如果你真的想让所有的边缘案例都过分迂腐地正确，你需要按照这些思路做一些事情:

unsigned invert(unsigned x, int p, int n) {
    if (p < 0 || p >= sizeof x * CHAR_BIT) {
        /* flip out and kill people */
    }
    if (n < 0 || n > p + 1) {
        /*  (╯°□°）╯︵ ┻━┻) */
    }
    if (n == sizeof x * CHAR_BIT) return ~x;
    /* Having dealt with all the undefined cases,
       we can safely use your nice expression.
       But without all the parentheses.  Superfluous
       parentheses make hulk angry. */
    return x ^ (1U << n) - 1 << p - n + 1;
}

这是迂腐矫枉过正吗？是的。我会期望有人在面试情况下将其写成第一关吗？不，我希望他们能够明智地讨论这里涉及的危险吗？是的。