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

    rcgldr

    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

    harborsparrow

    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 Discussions: Arithmetic shift divison question
  1. Array arithmetic in C? (Replies: 3)

  2. Java Arithmetic Stuff (Replies: 7)

Loading...