c++ - 整数のビットを「2倍にする」賢い方法はありますか？

Question

2進数を持っているとしましょう0b00110101。

0b0000111100110011最初の単語のすべてのビットが2回繰り返される、を生成する一連の簡単な算術演算はありますか？

ビット3、4、またはN回を繰り返すような些細な関数は存在しますか？

Answer 1

このドキュメントを見てください：

https://web.archive.org/web/20140629081102/http://www-graphics.stanford.edu/~seander/bithacks.html#InterleaveBMN

2 つの 16 ビット数のインターリーブについて説明しており、それを 32 ビット数に拡張するのはかなり簡単です (これにより 64 ビット数が作成されます)。パターンをもう 1 サイクル続けるだけです。このような：

static const unsigned long long B[] = {
    0x5555555555555555,
    0x3333333333333333,
    0x0F0F0F0F0F0F0F0F,
    0x00FF00FF00FF00FF,
    0x0000FFFF0000FFFF
};
static const unsigned int S[] = {1, 2, 4, 8, 16};

unsigned long long x; // x must initially fit inside 32 bits
unsigned long long z; // z gets the result of x interleaved with itself

x = (x | (x << S[4])) & B[4];
x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];

z = x | (x << 1);

Answer 2

私ならテーブルを作ります - それがおそらく一番早い方法です。

もちろん、これを行うことができます：

 int doublebits(int x)
 {
     int y = 0;
     int bit = 0;
     while(x)
     {
        if (x & 1)
            y |= 3 << bit;
        bit += 2;
        x >>= 1;
     }
     return y;
 }

8 ビットの数値の場合、最大で 8 回下にシフトし、8 回右にシフトして新しい数値を作成します。

Answer 3

さて、今回は正しいシーケンスを見つけたと思います：

http://oeis.org/search?q=3%2C12%2C15%2C48&sort="_language3%go=Search

彼らがそれを生成することを提案する1つの方法は再帰的です：

a（2n）= 4a（n）、a（2n + 1）= 4a（n）+3。

これは些細なことではありません。

Answer 4

ここを見ると、この手法にはLUTまたはループが必要なようです。y = xですから、計算前に設定する際に「わかりやすい方法」（リンク）を使用するのが最もエレガントな方法だと思います。

unsigned short x;   // Interleave bits of x and y, so that all of the
unsigned short y;   // bits of x are in the even positions and y in the odd;
unsigned int z = 0; // z gets the resulting Morton Number.

x = INPUT_PATTERN;
y = x;

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed...
{
  z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
}

はい、OPが求めるのは必ずしも「賢い」解決策ではないことを私は知っていますが、これまでの他の答えにはループ/再帰も含まれているので、試してみませんか...