CODEWITHSUNDEEP
c++mathbinary
Eric
Eric

Reputation: 97601

Is there a clever way to "double up" bits in an integer?

Say I have the binary number 0b00110101.

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

Does such a trivial function exist to repeat bits 3, 4, or N times?

Upvotes: 8

Views: 664

Answers (4)

paddy
paddy

Reputation: 63471

Have a look at this document:

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

It describes interleaving two 16-bit numbers, and it's fairly trivial to extend it to 32-bit numbers (this creating a 64-bit number). You just continue the pattern for one extra cycle. 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);

Upvotes: 9

ysap
ysap

Reputation: 8115

Looking here, it seems that the techniques either require LUTs or loops. So, I think the most elegant way will be to use the "Obvious way" (linked) while setting y = x prior to the calculation.

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 am aware it is not necessarily the "clever" solution that the OP asks for, but the other answers so far include loops/recursion as well, so why not give it a try...

Upvotes: 0

Mihai
Mihai

Reputation: 121

Ok, this time I believe to have found the correct sequence:

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

One way they suggest producing it is recursively:

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

which is anything but trivial.

Upvotes: 0

Mats Petersson
Mats Petersson

Reputation: 129374

I would make a table - it's PROBABLY the quickest 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'll do at most 8 shifts down, and 8 shifts to the right to make the new number.

Upvotes: 1

Related Questions