Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Arithmetic shift divison question

  1. Nov 27, 2009 #1
    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!
  2. jcsd
  3. Nov 29, 2009 #2
    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.
  4. Nov 29, 2009 #3


    User Avatar
    Homework Helper

    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/2562) + (p/2563) + (p/2564) + (p/2565) + ...
    Last edited: Nov 29, 2009
  5. Dec 2, 2009 #4


    User Avatar
    Gold Member

    are b and c integers? this might work if integers are stored as two's complement.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Threads - Arithmetic shift divison Date
C/++/# Is my code suffering from an arithmetic error? Feb 25, 2017
Insights Why Can't My Computer Do Simple Arithmetic? - Comments Jan 29, 2016
Arithmetic Issue in FORTRAN Oct 28, 2015
Arithmetic Issue in FORTRAN Oct 17, 2015
[Win32 API, C] Bit shifting Dec 24, 2014