title: How to insert zeros between bits in a bitmap?
body: <p>I have some performance-heavy code that performs bit manipulations. It can be reduced to the following well-defined problem:</p>
  <p><strong>Given a 13-bit bitmap, construct a 26-bit bitmap that contains the original bits spaced at even positions.</strong></p>
  <p>To illustrate:</p>
  <pre><code>0000000000000000000abcdefghijklm (input, 32 bits)
  0000000a0b0c0d0e0f0g0h0i0j0k0l0m (output, 32 bits)
  </code></pre>
  <p>I currently have it implemented in the following way in C:</p>
  <pre><code>if (input &amp; (1 &lt;&lt; 12))
      output |= 1 &lt;&lt; 24;
  if (input &amp; (1 &lt;&lt; 11))
      output |= 1 &lt;&lt; 22;
  if (input &amp; (1 &lt;&lt; 10))
      output |= 1 &lt;&lt; 20;
  ...
  </code></pre>
  <p>My compiler (MS Visual Studio) turned this into the following:</p>
  <pre><code>test        eax,1000h
  jne         0064F5EC
  or          edx,1000000h
  ... (repeated 13 times with minor differences in constants)
  </code></pre>
  <p>I wonder whether I can make it any faster. I would like to have my code written in C, but switching to assembly language is possible.</p>
  <ul>
  <li>Can I use some MMX/SSE instructions to process all bits at once?</li>
  <li>Maybe I can use multiplication? (multiply by 0x11111111 or some other magical constant)</li>
  <li>Would it be better to use condition-set instruction (SETcc) instead of conditional-jump instruction? If yes, how can I make the compiler produce such code for me?</li>
  <li>Any other idea how to make it faster?</li>
  <li>Any idea how to do the inverse bitmap transformation (I have to implement it too, bit it's less critical)?</li>
  </ul>