c++ - C/C++ で 2 進数の先頭のゼロを取り除く

Question

整数を指定して、そのバイナリ表現から先頭のゼロを削除するにはどうすればよいですか?

ビット単位の演算子を使用して、そのバイナリ表現を操作しています。整数がバイナリ表現で回文であるかどうかを確認しようとしています。さまざまな解決策があることは知っていますが、最初と最後のビット、2 番目と最後から 2 番目のビットなどを比較したかったのです。したがって、この int の先頭の 0 を削除する方法を考えていました。

Answer 1

BitScanForwardand (正確な名前はコンパイラによって異なります) を使用BitScanReverseして、どちらかの側からゼロを効率的にトリム (まあ、処理をスキップ) できます。

Answer 2

文字列の使用を気にせず、パフォーマンスが問題にならない場合は、次のようにすることができます。

    #include <bitset>
    #include <string>
    using namespace std;

    // your number
    int N;
    ...

    // convert to a 32 bit length binary string
    string bitstr = bitset<32>(N).to_string();

    // get the substring
    int index = 0;
    string strippedstr;
    for(unsigned int i = 0; i < bitstr.length(); ++i) {
        if(bitstr[i] == '1') {
            index = i;
            break;
        }
    }
    strippedstr = bitstr.substr(index);
   ...

Answer 3

数値の底 2 の対数を見つけることで、最初のビット セットを見つけることができます。

/* from Bit Twiddling Hacks */
static const unsigned int MultiplyDeBruijnBitPosition[32] = 
{
    0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
    8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

uint32_t pos = value;
pos |= pos >> 1;
pos |= pos >> 2;
pos |= pos >> 4;
pos |= pos >> 8;
pos |= pos >> 16;
pos = MultiplyDeBruijnBitPosition[(uint32_t)(pos * 0x07C4ACDDU) >> 27];

または、マスクが必要な場合は、次の 2 の累乗を見つけて適応させます。

/* adapted from Bit Twiddling Hacks */
uint32_t mask = value - 1;
mask |= mask >> 1;
mask |= mask >> 2;
mask |= mask >> 4;
mask |= mask >> 8;
mask |= mask >> 16;

Answer 4

整数のバイナリ表現が回文であるかどうかを確認する方法に投稿された回答は次のとおりです。

まず、この関数を使用してビットを逆にします。

/* flip n */
unsigned int flip(unsigned int n)
{
    int i, newInt = 0;
    for (i=0; i<WORDSIZE; ++i)
    {
        newInt += (n & 0x0001);
        newInt <<= 1;
        n >>= 1;
    }
    return newInt;
}

次に、末尾のゼロを削除します。

int flipped = flip(n);
/* shift to remove trailing zeroes */
while (!(flipped & 0x0001))
    flipped >>= 1;

int が回文であるかどうかを確認することについてのコメントに答えるには、ビットシフトされた反転バージョンを元のバージョンと比較してください。

return n == flipped;