如何切换最高位（MSB）是最佳方法？

Question

如何切换最高位（MSB）是最佳方法？

3

我想要切换我的数字的最高位。这里有一个例子：

x = 100101 then answer should be 00101

我有一台64位计算机，因此我不希望答案是100000..<51 0's>..100101。我想到的一种方法是计算我的数字中的位数，然后切换最高位，但是不确定如何计算。

- noMAD

1

切换设置的最后一位？MSB是另外一回事。 - user7116

1

如果没有设置任何位，那么结果应该是什么？ - Daniel Fischer

你想要切换最高有效位或将最高有效位清零吗？如果你想要将最高有效位清零，那么 x 的类型中有多少位？是16位、32位、64位还是其他的？ - Analog File

@sixlettervariables：好的，在这种情况下我该如何定义它呢？MSB将是从右侧开始的数字的第一个位。但问题是我不想考虑所有64位。 - noMAD

如果没有设置任何位，那么应该设置一位。 - noMAD

2

“*...从数字的右侧开始的第一个比特*”，你搞混了，对吧？我会说：…从左边开始。@noMAD” - alk

4个回答

3

@jleahy已经发布了一个在使用GCC时的好选择，我只会在这里留下一个通用的clz实现，它不使用任何编译器内置函数。然而，对于已经具有本地位数计数指令的CPU（例如x86），它不是最优选择。

#define __bit_msb_mask(n) (~(~0x0ul >> (n)))   /* n leftmost bits. */

/* Count leading zeroes. */
int clz(unsigned long x) {
    int nr = 0;
    int sh;

    assert(x);

    /* Hope that compiler optimizes out the sizeof check. */
    if (sizeof(x) == 8) {
        /* Suppress "shift count >= width of type" error in case
         * when sizeof(x) is NOT 8, i.e. when it is a dead code anyway. */
        sh = !(x & __bit_msb_mask(sizeof(x)*8/2)) << 5;
        nr += sh; x <<= sh;
    }

    sh = !(x & __bit_msb_mask(1 << 4)) << 4; nr += sh; x <<= sh;
    sh = !(x & __bit_msb_mask(1 << 3)) << 3; nr += sh; x <<= sh;
    sh = !(x & __bit_msb_mask(1 << 2)) << 2; nr += sh; x <<= sh;
    sh = !(x & __bit_msb_mask(1 << 1)) << 1; nr += sh; x <<= sh;
    sh = !(x & __bit_msb_mask(1 << 0)) << 0; nr += sh;

    return nr;
}

使用此函数，可以如下切换最高有效位（假设存在这样的位）：

x ^= 1ul << (sizeof(x)*8 - clz(x))

- Eldar Abusalimov

1

这里提供一种使用查找表的方法，假设 CHAR_BIT == 8：

uint32_t toggle_msb(uint32_t n)
{
    static unsigned char const lookup[] =
                         { 1, 0, 0, 1, 0, 1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7 };

    for (unsigned int i = 0; i != sizeof n; ++i)
    {
        // omit the last bit for big-endian machines: ---VVVVVVVVVVVVVVVVVV
        unsigned char * p
                 = reinterpret_cast<unsigned char *>(&n) + sizeof n - i - 1;

        if (*p / 16 != 0) { *p = *p % 16 + (lookup[*p / 16] * 16); return n; }
        if (*p % 16 != 0) { *p = 16 * (*p / 16) + lookup[*p % 16]; return n; }
    }

    return 1;
}

- Kerrek SB

你的查找超出了静态数组的范围，导致结果未定义... - Chris Dodd

@ChrisDodd：那是因为我本来想把它分成两个半字节。已修复！ - Kerrek SB

这个问题在于编译器无法对其进行优化。如果您不能使用内部函数，我更喜欢@EldarAbusalimov的方法。 - jleahy

@jleahy：是的，这个解决方案可能是这里提供的答案中最糟糕的一个。 - Kerrek SB

0

并且只需将所有内容放在一起，以GCC的一些示例代码：

#include <stdio.h>

#define clz(x)  __builtin_clz(x)

int main()
{
    int i = 411;    /* 110011011 */

    if( i != 0 )
        i ^= (1 << (sizeof(i)*8 - clz(i)-1));

    /* i is now 10011011 */
    printf("i = %d\n", i);
    return(0);
}

- Chimera

而且，为什么会被踩呢？难道完整的代码示例中展示别人所说的内容没有价值吗？ - Chimera

我会立即更改的显而易见的事情是使用CHAR_BIT而不是8，但我认为这并不严重到足以引起反对票。 - Jerry Coffin

我想也许是因为我拿了一条评论并加以扩展，所以被踩了？ - Chimera

我不知道。我没有看到很多东西可以真正证明在任何方向上投很多票的理由。 - Jerry Coffin

也许——除非做这件事的人发表评论，否则我怀疑任何人都无法真正猜测。 - Jerry Coffin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jleahy · Accepted Answer

作弊的方法是将其转交给编译器：大多数CPU都有执行此类工作的指令。

以下代码应该可以达到你想要的效果。

i ^ (1 << (sizeof i * CHAR_BIT - clz(i) - 1))

这将转换为CLZ指令，用于计算前导零位。

对于GCC，请参见：http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html 需要注意的一点是，如果i == 0，则会导致未定义行为。

您应该使用编译器的正确内置函数替换clz()。在GCC中，这是__builtin_clz；在Visual Studio C++中，这是_BitScanForward。