Eric - 8 months ago 36

C++ Question

Say I have the binary number

`0b00110101`

Is there a set of trivial arithmetic operations that will produce

`0b0000111100110011`

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

Answer

Have a look at this document:

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