title: Efficient tiny boolean matrix multiplication
body: <p>I have some unsigned 16 bit integer <code>s</code> which I'd like to map to an unsigned 32 bit integer <code>r</code> in such a way that each flipped bit in <code>s</code> flips at most one (given) bit in <code>r</code> -- simply a mapping between <code>0..16</code> and <code>0..32</code> that is. So we can see this as a matrix equation</p>
  
  <pre><code>Ps = r
  </code></pre>
  
  <p>where P is a <code>32 x 16</code> boolean matrix, <code>s</code> is a <code>16 x 1</code> boolean vector and <code>r</code> is <code>32 x 1</code> boolean vector. I have a gut feeling there exists some super simple hack that I'm missing. Important note: the target machine is a 16 bit mcu!</p>
  
  <p>Here's the best I can do:</p>
  
  <pre><code>static u16 P[32] = someArrayOrWhatever();
  
  u32 FsiPermutationHack(u16 s) {
      u32 r;
      for (u16 i = 0; i &lt; 32; i++)
      {
              r |= ((u32)((P[i] &amp; s) &gt; 0) &lt;&lt; i);
      }
      return r;
  }
  </code></pre>
  
  <p>The rationale is this: the i:th bit of <code>r</code> is 1 if and only if <code>(P[i] &amp; s) != 0x0000</code>. I am too stupid to disassemble stuff, but I am guessing this would be like ~100 instructions IF we didn't have to do that stupid <code>u32</code> cast. But then again, perhaps the compiler auto-splits the loop in two for us in which case it's looking pretty good for us. </p>
  
  <p>Apologies for the tangent, just thought I'd share my attempted solution -- do you have a better one?</p>