title: Fast inner product of ternary vectors
body: <p>Consider two vectors, <strong>A</strong> and <strong>B</strong>, of size <em>n</em>, 7 &lt;= <em>n</em> &lt;= 23. Both <strong>A</strong> and <strong>B</strong> consists of -1s, 0s and 1s only.</p>
  
  <p>I need a fast algorithm which computes the inner product of <strong>A</strong> and <strong>B</strong>.</p>
  
  <p>So far I've thought of storing the signs and values in separate <code>uint32_t</code>s using the following encoding:</p>
  
  <ul>
  <li>sign 0, value 0 → 0</li>
  <li>sign 0, value 1 → 1</li>
  <li>sign 1, value 1 → -1.</li>
  </ul>
  
  <p>The C++ implementation I've thought of looks like the following:</p>
  
  <pre><code>struct ternary_vector {
      uint32_t sign, value;
  };
  
  int inner_product(const ternary_vector &amp; a, const ternary_vector &amp; b) {
      uint32_t psign = a.sign ^ b.sign;
      uint32_t pvalue = a.value &amp; b.value;
      psign &amp;= pvalue;
      pvalue ^= psign;
      return __builtin_popcount(pvalue) - __builtin_popcount(psign);
  }
  </code></pre>
  
  <p>This works reasonably well, but I'm not sure whether it is possible to do it better. Any comment on the matter is highly appreciated.</p>