Bit Manipulation- Understanding Rounding Toward Zero Bias When Multiplying A Negative By a Fraction

Question

I have a a bit manipulation method which multiplies a number toward five eighths and if there is a remainder rounds toward 0. The method works, and I understand almost all of it. When I was reviewing it, however, I realized I'm not certain how anding 7 (00000111) accounts for rounding error, in which it would round toward a more negative number instead of 0, and I need to understand why that line works. As far as I can see, shifting multiplyByFive 31 bits to the right will just check the sign of the variable and yield all ones if negative, so anding it with 7 will either yield all zeroes if positive, or y in binary if negative. If my understanding is correct, why does adding that to multiplyFiveEighths and dividing the sum by 8 round a negative number down, without error.

int multFiveEights(int x) {

break it down into multiplying by 5 and then dividing by 8 shifting it two to the left multiplies it by four, plus x makes it by 5

int multiplyByFive = (x << 2) + x;

if the result is negative, and 2^3 - 1 = 7 before right shift

int addNumber = 7 & (multiplyByFive >> 31);

11111111 (if you right shift by 31 when negative you get all 1s)

will return all 0s if positive and 1 in the LSB if negative

adding 7 to multiplyByFive accounts for error

if its negative it will try to round down which goes toward the more negative number, so anding it with 7 accounts for this error/ tests for a remainder

int fiveEigths = (multiplyByFive + addNumber) >> 3;
return fiveEigths;

If x is positive, then do you understand why x/8 rounds down but (x+7)/8 rounds up? — user253751

samgak samgak · Accepted Answer · 2017-02-09T03:26:48

addNumber is going to be 7 when multiplyByFive is negative and 0 when it is positive (I assume you understand this part).

So, the logic is to add 7 to multiplyByFive before right shifting by 3, but only when it is negative.

To understand why this works, consider the difference between rounding down and rounding up in terms of the lower 3 bits.

When the lower 3 bits are zero, then rounding up and rounding down won't produce any difference, because no rounding needs to occur because the number is a multiple of 8 and so dividing by 8 (which is what the right shift by 3 does) produces an integer result.

When the lower 3 bits are anything else, then the final result rounding down will be one less than if you had rounded up.

By adding 7, you will increase the final result by 1, by clocking over the 4th bit in each case except for when the lower 3 bits are zero. If they are all 0, adding 7 will set the lower 3 bits to 1 but won't affect the 4th, leaving the shifted result unchanged.

Bit Manipulation- Understanding Rounding Toward Zero Bias When Multiplying A Negative By a Fraction

2 Answers