title: How to find x mod 15 without using any Arithmetic Operations?
body: <p>We are given a unsigned integer, suppose. And without using any arithmetic operators ie <code>+</code> <code>-</code> <code>/</code> <code>*</code> or <code>%</code>, we are to find <code>x mod 15</code>. We may use binary bit manipulations.</p>
  
  <p>As far as I could go, I got this based on 2 points.</p>
  
  <p><code>a = a mod 15 = a mod 16</code> for <code>a&lt;15</code></p>
  
  <p>Let <code>a = x mod 15</code>
  then <code>a = x - 15k</code> (for some non-negative <code>k</code>).</p>
  
  <p>ie <code>a = x - 16k + k</code>...</p>
  
  <p>ie <code>a mod 16 = ( x mod 16 + k mod 16 ) mod 16</code></p>
  
  <p>ie <code>a mod 15 = ( x mod 16 + k mod 16 ) mod 16</code></p>
  
  <p>ie <code>a = ( x mod 16 + k mod 16 ) mod 16</code></p>
  
  <p>OK. Now to implement this. A <code>mod16</code> operations is basically <code>&amp; OxF</code>. and <code>k</code> is basically <code>x&gt;&gt;4</code></p>
  
  <p>So <code>a = ( x &amp; OxF + (x&gt;&gt;4) &amp; OxF ) &amp; OxF</code>.</p>
  
  <p>It boils down to adding 2 4-bit numbers. Which can be done by bit expressions.</p>
  
  <p><code>sum[0] = a[0] ^ b[0]</code></p>
  
  <p><code>sum[1] = a[1] ^ b[1] ^ (a[0] &amp; b[0])</code></p>
  
  <p>...
  and so on</p>
  
  <p>This seems like cheating to me. I'm hoping for a more elegant solution</p>