3

だから私は私の番号の最上位ビットを切り替えたいと思います。次に例を示します。

x = 100101 then answer should be 00101

私は64ビットマシンを使用しているため、答えが100000..<51 0's>..100101 1つになるとは思っていません。自分の数のビット数をカウントしてから、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を参照してください。

注意すべきことの1つは、。の場合、これにより未定義の動作が発生することです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 に答える