0

我被要求实现invert(x,p,n)返回 x ，其中从位置 p 开始的 n 位倒置（即，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);
}

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

4

1 回答 1

4

好吧，您的实现显然不正确；考虑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 段）：

如果 E1 有带符号类型和非负值，并且 E1 × 2 E2在结果类型中是可表示的，那么这就是结果值；否则，行为未定义。

您可以通过使常量无符号来解决此问题...1

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

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

如果右操作数 ... 的值大于或等于提升的左操作数的宽度，则行为未定义。

您在网上找到的解决方案以同样的方式遭受未定义的行为。如果你真的想让所有的边缘情况都过分地正确，你需要按照以下方式做一些事情：

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;
}

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

于 2013-11-07T20:09:47.907 回答