title: How to explain this program calculating 3/4*x using bit operation?
body: <p>For a given value of <code>int</code> type, calculating 3/4*x using the most basic bit operations(i.e. no <code>while</code>/<code>for</code> or other C control logic. Also suppose <code>sizeof(int) = 4 (Byte)</code>. And the hard point is to truncate towards 0 and avoiding overflow.</p>
  
  <p>What I have tried:</p>
  
  <p>Suppose expressing <code>x</code> as its binary form:
  <code>x = [b_31 b_30 ... b_2 b_1 b_0]</code><br>
  Then <code>3/4*x = x/2 + x/4 = ([b_31 ... b_1 0] + b_0) &gt;&gt; 1 + ([b_31 ... b_2 0 0] + b_1 b_0) &gt;&gt; 2</code><br>
  Then using <code>x&gt;&gt;1 + x&gt;&gt;2</code> we can get <code>[b_31 ... b_1 0]&gt;&gt;1 + [b_31 ... b_2 0 0]&gt;&gt;2</code> without precision lost or overflow problem, leaving only <code>[b_0 0] + [b_1 b_0]&gt;&gt; 2</code> to deal with. But I got stuck here for I had no idea how to implement truncating towards zero.   </p>
  
  <p>Comparing to the following sample program, I found two variables <code>x_mask</code> and <code>bias</code> used. I guess they are used to solve the truncate problem since for a negative number <code>bias</code> will always be <code>11</code> and for a positive number <code>00</code>. Can anyone help explain the logic here?</p>
  
  <pre><code>int threefourths(int x) {
       int xl2 = x &amp; 0x3;
       int xl1 = (x&amp;1) &lt;&lt; 1;
       int x_mask = x &gt;&gt; ((sizeof(int)&lt;&lt;3)-1);
       int bias = x_mask &amp; 3;
       int incr = (xl2+xl1+bias) &gt;&gt; 2;
       int s2 = x &gt;&gt; 2;
       int s1 = x &gt;&gt; 1;
       return s1 + s2 + incr;
       }
  </code></pre>