c - マイナービットをオンにする方法は？

Question

しましょaうunsigned int：

unsigned int a = 188; // 10111100

オンになっているマイナービットを取得する組み込み関数はありますか? 例: 1 番目と 2 番目のビットはゼロですが、3 番目のビットは1aであるため、返される必要があります。2

// 10111100
//      ^
//      |-- Minor bit turn on

私は GCC と C99 標準を使用しています。

Answer 1

これは組み込まれていませんが、機能します...

末尾のゼロ カウント (集約 MAGIC アルゴリズムから)

Least Significant 1 Bit and Population Count (Ones Count) アルゴリズムを考えると、それらを組み合わせて末尾のゼロ カウントを構築するのは簡単です (Joe Bowbeer が指摘したように)。

unsigned int
tzc(register int x)
{
    return(ones((x & -x) - 1));
}

32ビットの場合は次のとおりです。

unsigned int
ones32(register unsigned int x)
{
    /* 32-bit recursive reduction using SWAR...
   but first step is mapping 2-bit values
   into sum of 2 1-bit values in sneaky way
*/
    x -= ((x >> 1) & 0x55555555);
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
    x = (((x >> 4) + x) & 0x0f0f0f0f);
    x += (x >> 8);
    x += (x >> 16);
    return(x & 0x0000003f);
}

Answer 2

最大 64 ビットに適しています。

static signed char f(uint64_t x)
{
    static const signed char p[] = { -1, 0, 1, 39, 2, 15, 40, 23, 3, 12,
        16, 59, 41, 19, 24, 54, 4, 0, 13, 10, 17, 62, 60, 28, 42, 30, 20,
        51, 25, 44, 55, 47, 5, 32, 0, 38, 14, 22, 11, 58, 18, 53, 63, 9,
        61, 27, 29, 50, 43, 46, 31, 37, 21, 57, 52, 8, 26, 49, 45, 36, 56,
        7, 48, 35, 6, 34, 33, };

    return p[(x & -x) % 67];
}

0 から何を返せばよいのか不明なので、-1 を使用しました。それは明らかに変更できます。

Answer 3

控えめながら移植性の高いソリューションです。64 ビットの
場合、最大 16 ループ。unsignedN-bit で N 未満のシフトint。

int MinorBit(unsigned x) {
  if (x == 0) 
    return -1;  // special case, adjust as needed.
  int m = 0;
  // Search by char
  while ((x & ((1u << CHAR_BIT) - 1)) == 0) { 
    x >>= CHAR_BIT;
    m += CHAR_BIT;
  }
  // Search by bit
  while ((x & 1) == 0) { 
    x >>= 1;
    m++;
  }
  return m;
}

Answer 4

はい。GCC を使用しているため、組み込み関数の __builtin_ctz ファミリーを末尾ゼロ カウントに使用できます。

int __builtin_ctz (unsigned int x);

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.htmlから引用。

例えば、

2 == __builtin_ctz(188)

警告: 入力 0 の場合、結果は未定義です。したがって、その使用は保護する必要がある場合があります。

int safe_ctz(unsigned int x){
    return x ? __builtin_ctz(x) : 32;
}

このビルトインの利点は、x86 の BSF など、一部のターゲットでは GCC がこれを単一の命令に変換することです。