Arithmetic shift divison question

[bitrex]

If I have the following function:

a = b * c/255

The following function is apparently equivalent using only shifts:

product = b * c;
a = (product + (product>>8) + 1)>>8;

I am having trouble following how this function works. Since an arithmetic right shift is division by a power of 2 right shift 8 would be division by 256...somehow (product + (product>>8) +1) is compensating for the difference between the two but I'm not sure why it's that and not just (product + 1). I'm too thickheaded to see it, any clarification would be appreciated!

 

[silverfrost]

I don't think your formula is correct. For example, if b was 0, then b*c/255 is zero but your replacement formula would not produce 0.

 

[rcgldr]

The algorithm fails at 65535 (255*257) and larger numbers.

The algorithm is based on the fact that in hexadecimal fixed point

1/ff = .010101010101 ...

or expressed as a power series:

p/255 = (p/256) + (p/256²) + (p/256³) + (p/256⁴) + (p/256⁵) + ...

 

[harborsparrow]

are b and c integers? this might work if integers are stored as two's complement.