Problems with bit-shifting in complicated expressions

Question

I've distilled an equation down to this:

speed = ( ( rear_wheel_speed_a + front_wheel_speed_a ) << 10 ) +
        ( ( rear_wheel_speed_b + front_wheel_speed_b ) << 2 );

but for some reason I'm getting unexpected results so I must be doing something wrong. This started out like this:

speed = ((((rear_wheel_speed_a * 256 + rear_wheel_speed_b) / 16) +
        ((front_wheel_speed_a * 256 + front_wheel_speed_b) / 16)) / 2) * 128;

That is the completely unsimplified version that does work. Are they not mathematically equivalents?

all values are signed 16 bit integers. An example data set is:

rear_wheel_speed_a = 0x03;
rear_wheel_speed_b = 0x6F; //<-- I originally swapped
front_wheel_speed_a = 0x02; //<-- these two values. Sorry!
front_wheel_speed_b = 0xE2;

That boils down to an answer of 6468. But in the first equation, my application behaves as though it is at least 3% smaller or larger. I say it like that because this is an embedded application where I have no way of confirming the outcome of the calculations other than to test if it is within a certain range of "normal". When I use the 2nd equation it falls within the parameters but with my "simplified" (bit shifted) equation it does not so I think I must be doing the shifts incorrectly (or I simplified wrong but I triple checked it).

Any insight is appreciated, thank you.

Answer 1

The problem is that you're getting an overflow. While the equation you've transformed is mathematically correct, some of your interim values are higher than the signed 16-bit ints you're storing them in.

To be specific, the problematic part is

( rear_wheel_speed_a + front_wheel_speed_a ) << 10

With your sample input, the resulting value is 0x1C800 - larger than even an unsigned 16-bit integer!

The original equation seems to already take this into account. Some of the values lose precision slightly when downshifting, but that's better than the integer overflowing. So I recommend using the original equation, but you can replace the multiply and divide with shifts, of course:

((((rear_wheel_speed_a << 8) + rear_wheel_speed_b) >> 4) + (((front_wheel_speed_a << 8) + front_wheel_speed_b) >> 4)) << 6;

Another note: Your input front_wheel_speed_b is already overflowing, unless it is supposed to be negative.

Answer 2

From the second formula, I assume you operating 2 16bit values separated into their 8bit part a and b:

rear_wheel_speed = 0x0302
front_wheel_speed = 0x6fe2

and the formula you using, can be simplified into speed=(front_speed+rear_speed)*4.

From your values, 0x6fe2*4 just can fit 16bit, so this value can be evaluated in 16-bit arithmetic. But the values look like their parts are arranged wrong, and I have a feeling that real values are 0x036f and 0x02e2 (or 0x03ea and 0x026f) - those values are close to each other, as should be expected from speed of two wheels.

Also it seems your formula is better, because it doesn't introduce loss of precision on divide operations. But keep in mind, that if you're using a good compiler (not always true for embedded applications) it usually converts divide/multiply to shifts itself when possible

Answer 3

What you want is the mean of rear_wheel_speed and front_wheel_speed, scaled to fit on 16 bits. Since they are 16-bit values, the sum is on 17 bits, so you have to shift the result to avoid overflow.

Your initial formula takes each speed on 12 bits (xxx/16), then the mean of the values, again on 12 bits, then multiplies by 128. This will require 19 bits: your initial formula will overflow for larger values.

To get the mean on 16 bits without overflow, I suggest the following (assuming the values are positive as you said in your comment):

rear_wheel_speed_h = (rear_wheel_speed_a << 7) | (rear_wheel_speed_b >> 1)
front_wheel_speed_h = (front_wheel_speed_a << 7) | (front_wheel_speed_b >> 1)
speed = rear_wheel_speed_h + front_wheel_speed_h

This will give a result on 16 bits without overflow. Each xxx_wheel_speed_h is on 15 bits.