title: Rounded division by power of 2
body: <p>I'm implementing a quantization algorithm from a textbook.  I'm at a point where things pretty much work, except I get off-by-one errors when rounding.  This is what the textbook has to say about that:</p>
  
  <blockquote>
    <p>Rounded division by <code>2^p</code> may be carried out by adding an offset and right-shifting by p bit positions</p>
  </blockquote>
  
  <p>Now, I get the bit about the right shift, but what offset are they talking about?</p>
  
  <p>Here's my sample code:</p>
  
  <pre><code>def scale(x, power2=16):
      if x &lt; 0:
          return -((-x) &gt;&gt; power2)
      else:
          return x &gt;&gt; power2
  def main():
      inp = [ 12595827, -330706, 196605, -387168, -274244, 377496, -241980, 
              -545272,  -196605, 24198,   196605,  193584, 104858, 424683,
              -40330,     41944 ]
      expect = [ 192, -5, 3, -6, -4, 5, -3, -8, -3, 0, 3, 3, 1, 6, 0, 0 ]
      actual = map(scale, inp)
      for i in range(len(expect)):
          if actual[i] == expect[i]:
              continue
          print 'inp: % 8d expected: % 3d actual: % 3d err: %d' % (inp[i], 
                  expect[i], actual[i], expect[i] - actual[i])
  if __name__ == '__main__':
      main()
  </code></pre>
  
  <p>I'm checking for negative input as bit shifting a negative integer appears to be implementation-dependent.</p>
  
  <p>My output:</p>
  
  <pre><code>inp:   196605 expected:   3 actual:   2 err: 1
  inp:  -387168 expected:  -6 actual:  -5 err: -1
  inp:  -196605 expected:  -3 actual:  -2 err: -1
  inp:   196605 expected:   3 actual:   2 err: 1
  inp:   193584 expected:   3 actual:   2 err: 1
  </code></pre>
  
  <p>What is the offset that is mentioned in the textbook, and how can I use it to get rid of this error?</p>