9/09/2008

09-09-08 - 1

Int division takes you toward zero; shifting right takes you toward -infinity :
-1/4 == 0
-1>>2 == -1
-5/4 == -1
-5>>2 == -2

To divide an int by 2 and preserve exact average of a bunch of ints, you need to push the odd values up half the time and down half the time; this is :

( val + ((val>>1)&1) ) >> 1

One way to get rid of signs is to interleave the positive and negative halves of the lines : (0,1,2) -> (0,2,4) and (-1,-2,-3) -> (1,3,5)

if ( val >= 0 ) return val*2;
else return -val*2 - 1;
I wouldn't actually code from this directly, however, what you can do is first code the 0 or not-0 flag, then code the sign bit, which is just (val&1) , then code the magnitude :
if ( positive ) mag = val>>1;
else mag = (val+1)>>1;

To code a value with a Laplacian probability distribution ( P(x) = c * r^x ), simply using a Golomb code with W = average ; this code is :

top = value / W
bottom = value mod W = value - top * W
send top with unary
send bottom raw

No comments:

old rants