Is there a smart way to double bits into an integer?

Question

Say I have a binary number 0b00110101 .

Is there a set of trivial arithmetic operations that will produce 0b0000111100110011 , where each bit of the first word is repeated twice?

Is there such a trivial function for repeating bits 3, 4, or N times?

Answer 1

Take a look at this document:

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

It describes the alternation of two 16-bit numbers, and it's pretty trivial to extend it to 32-bit numbers (this creates a 64-bit number). You just continue the pattern in one extra loop. Like this:

 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

I would make a table - this is probably the fastest way.

You could, of course, do this:

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

For an 8-bit number, you will make no more than 8 shifts, and 8 shifts to the right to make a new number.

Answer 3

Ok, this time I believe that I found the correct sequence:

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

One way to suggest recursion:

a (2n) = 4a (n), a (2n + 1) = 4a (n) + 3.

that nothing but trivial.

Answer 4

Looking here , it seems that for certain methods, LUTs or loops are required. So, I believe that the most elegant way would be to use the "Obvious Path" (related) when setting y = x before calculating.

 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); } 

Yes, I know that this is not necessarily the smart solution that the OP will request, but other answers still include loops / recursion, so why not give it a try ...