title: Is it possible to implement bitwise operators using integer arithmetic?
body: <p>I am facing a rather peculiar problem. I am working on a compiler for an architecture that doesn't support bitwise operations. However, it handles signed 16-bit integer arithmetics and I was wondering if it would be possible to implement bitwise operations using only: </p>
  
  <ul>
  <li><strong>Addition</strong> (<em>c = a + b</em>)</li>
  <li><strong>Subtraction</strong> (<em>c = a - b</em>)</li>
  <li><strong>Division</strong> (<em>c = a / b</em>)</li>
  <li><strong>Multiplication</strong> (<em>c = a</em> * <em>b</em>)</li>
  <li><strong>Modulus</strong> (<em>c = a % b</em>)</li>
  <li><strong>Minimum</strong> (<em>c = min(a, b)</em>)</li>
  <li><strong>Maximum</strong> (<em>c = max(a, b)</em>)</li>
  <li><strong>Comparisons</strong> (<em>c = (a &lt; b), c = (a == b), c = (a &lt;= b), et.c.</em>)</li>
  <li><strong>Jumps</strong> (<em>goto, for, et.c.</em>)</li>
  </ul>
  
  <p>The bitwise operations I want to be able to support are:</p>
  
  <ul>
  <li><strong>Or</strong> (<em>c = a | b</em>)</li>
  <li><strong>And</strong> (<em>c = a &amp; b</em>)</li>
  <li><strong>Xor</strong> (<em>c = a ^ b</em>)</li>
  <li><strong>Left Shift</strong> (<em>c = a &lt;&lt; b</em>)</li>
  <li><strong>Right Shift</strong> (<em>c = a >> b</em>) </li>
  <li>(All integers are signed so this is a problem)</li>
  <li><strong>Signed Shift</strong> (<em>c = a >>> b</em>)</li>
  <li><strong>One's Complement</strong> (<em>a = ~b</em>)</li>
  <li>(Already found a solution, see below)</li>
  </ul>
  
  <p>Normally the problem is the other way around; how to achieve arithmetic optimizations using bitwise hacks. However not in this case.</p>
  
  <p>Writable memory is <strong>very scarce</strong> on this architecture, hence the need for bitwise operations. The bitwise functions themselves should not use a lot of temporary variables. However, constant read-only data &amp; instruction memory is abundant. A side note here also is that jumps and branches are not expensive and all data is readily cached. Jumps cost half the cycles as arithmetic (including load/store) instructions do. On other words, all of the above supported functions cost twice the cycles of a single jump.</p>
  
  <hr>
  
  <h2>Some thoughts that might help:</h2>
  
  <p>I figured out that you can do <strong>one's complement</strong> (negate bits) with the following code:</p>
  
  
  
  <pre class="lang-c prettyprint-override"><code>// Bitwise one's complement
  b = ~a;
  // Arithmetic one's complement
  b = -1 - a;
  </code></pre>
  
  <p>I also remember the old shift hack when dividing with a power of two so the <strong>bitwise shift</strong> can be expressed as:</p>
  
  <pre class="lang-c prettyprint-override"><code>// Bitwise left shift
  b = a &lt;&lt; 4;
  // Arithmetic left shift
  b = a * 16; // 2^4 = 16
  
  // Signed right shift
  b = a &gt;&gt;&gt; 4;
  // Arithmetic right shift
  b = a / 16;
  </code></pre>
  
  <p>For the rest of the bitwise operations I am slightly clueless. I wish the architects of this architecture would have supplied bit-operations.</p>
  
  <p>I would also like to know if there is a fast/easy way of computing the power of two (for shift operations) without using a memory data table. A naive solution would be to jump into a field of multiplications:</p>
  
  <pre class="lang-c prettyprint-override"><code>b = 1;
  switch (a)
  {
    case 15: b = b * 2;
    case 14: b = b * 2;
    // ... exploting fallthrough (instruction memory is magnitudes larger)
    case 2: b = b * 2;
    case 1: b = b * 2;
  }
  </code></pre>
  
  <p>Or a Set &amp; Jump approach:</p>
  
  <pre class="lang-c prettyprint-override"><code>switch (a)
  {
    case 15: b = 32768; break;
    case 14: b = 16384; break;
    // ... exploiting the fact that a jump is faster than one additional mul
    //     at the cost of doubling the instruction memory footprint.
    case 2: b = 4; break;
    case 1: b = 2; break;
  }
  </code></pre>