3

所以我想切换我的号码中最重要的位。这是一个例子：

x = 100101 then answer should be 00101

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

4

4 回答 4

6

作弊是将其抵押给编译器：大多数 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.

于 2012-09-21T15:44:34.463 回答
3

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

#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))
于 2012-09-21T16:01:37.410 回答
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;
}
于 2012-09-21T15:34:35.873 回答
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);
}
于 2012-09-21T18:43:55.637 回答