8

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?

Eric
  • 95,302
  • 53
  • 242
  • 374
  • Short of a lookup table, I think the answer is: no. Whether implicitly or explicitly, you need to unpack the bits in the input word. – Oliver Charlesworth Jan 14 '13 at 00:19
  • 2
    @Nate It's just one way to write a binary number and mark it as such (similar to people usually using `0x0000` for hexadecimal numbers. – Mario Jan 14 '13 at 00:22
  • 1
    @Nate: that's a binary literal, which I believe c++ supports. – Eric Jan 14 '13 at 00:23
  • It's pretty easy using bit shifting and or, but that requires a loop. – Peter Wooster Jan 14 '13 at 00:24
  • 1
    @Mario oh ok thanks I'm not familiar with that my bad. – Nate-Wilkins Jan 14 '13 at 00:28
  • @Eric: Look up table (8 bit -> 16 bit) probably best all round solution. If working on low level code / hardware, I've seen people hardwire I/O ports out to in to achieve this kind of thing. – Component 10 Jan 14 '13 at 00:36
  • What you're after is bit wise interleaving. In this particular case, you want to interleave a byte into itself, which will produce the result you want. Just mentioning this since there are question on SO already on how to interleave bits. – Nikos C. Jan 14 '13 at 00:41
  • Some architectures (including Intel's x86 in a few months) have instructions that make it almost trivial. – Marc Glisse Jan 14 '13 at 01:08
  • 1
    Write your program in [INTERCAL](http://en.wikipedia.org/wiki/INTERCAL) and use the INTERLEAVE operator. – Adam Rosenfield Jan 14 '13 at 02:28
  • @MarcGlisse: so, like always, write a trivial implementation behind a function; then optimize when you need and can (LUTs/bitwise/builtin). – Matthieu M. Jan 14 '13 at 07:58

4 Answers4

9

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);
Quonux
  • 2,975
  • 1
  • 24
  • 32
paddy
  • 60,864
  • 6
  • 61
  • 103
  • I forgot to answer the second part of your question, regarding triplicate etc... I believe the same thing applies but using different magic numbers in `B`. There's an existing question about 3-value Morton Numbers on SO that might help: http://stackoverflow.com/questions/1024754/how-to-compute-a-3d-morton-number-interleave-the-bits-of-3-ints – paddy Jan 14 '13 at 04:47
  • This was the kind of solution I suspected existed. Thanks! – Eric Jan 14 '13 at 08:37
1

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.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
  • I don't think you need to use an if inside the loop, it should be possible with just logical shifts and or, at least it would in Assembler. – Peter Wooster Jan 14 '13 at 00:26
  • I wrote it so that's reasonably readable. If you want speed, use that function to generate a table. [I don't expect a modern compiler, at least gcc and MS to generate a branch anyways]. – Mats Petersson Jan 14 '13 at 00:44
  • 3
    `x >> 1` is a dangling statement. What did you mean for it to do? – David G Jan 14 '13 at 00:47
  • Fixed.. Thanks for spotting [and the missing space!] – Mats Petersson Jan 14 '13 at 00:48
  • Readable and clever don't need to go together. I agree the table solution is faster, but seriously ugly. Something done with bit manipulation only would appeal to the Assembler geeks. – Peter Wooster Jan 14 '13 at 00:52
  • I was trying to think of if there was some clever way to multiply the number, and it wouldn't surprise me if there is a way somewhere on the interweb. But usually when I need something like this, I either can make a table, or it's not so speed critical that you need cleverness. SOme sort of multiplication should do the trick, but I couldn't think of it for the moment. – Mats Petersson Jan 14 '13 at 00:54
  • How does this work? Sorry I'm bad when it comes to bits but can you please explain so I can understand?? I know the if statement means "if `x` is odd" but the rest I do not get. :) – template boy Jan 14 '13 at 00:57
  • @templateboy - remember that `3` decimal is `11` binary. Now, assume `bit` contains the offset of the current double-bits, so if `x` is odd, then `y = y | (0b11 << bit)`. For each new bit of `x`, increase the offset by 2, shift `x` by 1 position to the right, discarding the last lsb, and repeat the calculation until the last non-zero bit of `x`. HTH. – ysap Jan 14 '13 at 02:02
  • @MatsPetersson Yep, I located and adapted some clever code from the web. It's basically multiplication, but combined with a series of masks. See the code in my answer =) – paddy Jan 14 '13 at 02:26
  • @ysap Thanks got it. One more question: why are we using the number 3? Whats so special about it? – David G Jan 14 '13 at 23:51
  • 3 is the same as 11 in binary - if there is a 1 in the input binary, we want 11 in the output binary. Same if you wanted 3 bits, you'd use 7, if you want four bits, you'd use 15, etc [and of course `bits += 3` and `bits += 4` respectively. – Mats Petersson Jan 14 '13 at 23:54
  • @MatsPetersson - "I wrote it so that's reasonably readable." I don't think adding a redundant check improves readability - it simply makes the program longer. IMO it'd be a bit simpler and clearer without the if. – Desty Jul 23 '13 at 12:14
  • @Desty: That depends on the experience of the reader. For someone familiar with binary encoding and decoding, sure. For the average programmer, it's (a little) easier to get this way. – Mats Petersson Jul 23 '13 at 12:19
0

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.

Mihai
  • 121
  • 3
0

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...

ysap
  • 7,723
  • 7
  • 59
  • 122