Rounded division by power of 2

Question

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:

Rounded division by 2^p may be carried out by adding an offset and right-shifting by p bit positions

Now, I get the bit about the right shift, but what offset are they talking about?

Here's my sample code:

def scale(x, power2=16):
    if x < 0:
        return -((-x) >> power2)
    else:
        return x >> 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()

I'm checking for negative input as bit shifting a negative integer appears to be implementation-dependent.

My output:

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

What is the offset that is mentioned in the textbook, and how can I use it to get rid of this error?

Answer 1

The shift will truncate. The shift is a binary operator operating. I'm using square brackets to denote the base here:

196605[10] = 101111111111111111[2]
101111111111111111[2] >> 16[10] = 10[2] = 2[10]

To perform correct rounding you need to add half of your divisor before doing the shift.

101111111111111111[2] + 1000000000000000[2] >> 16[10] = 110111111111111111[2] >> 16[10] = 11[2] = 3[10]

Answer 2

Shifting by p gives division by 2^p rounded down (truncated).

If you want to divide by 2^p but round to closest integer, do:

shift-right by (p-1)
add 1
shift-right 1

In your code:

def scale(x, power2=16):
    if x < 0:
        return -((((-x) >> (power2-1)) + 1) >> 1)
    else:
        return ((x >> (power2-1)) + 1) >> 1