"rounding" with integers

Question

I'm trying to get rid of floats in my functions.

I have one function that operates on a 16 bit integer value which is an upscaled 8 bit value. Then a downscaled 8 bit is sent to the output.

I'm sure I'm not explaining it well. Something like this:

int8 spot_value = 21;  //arbitrary. just need a starting point
int16 running_value;

running_value = spot_value << 8;  //multiply by 256 which is 5376
running_value += 154;  //my upscaled value is now 5530
spot_value = running_value >> 8;  //downscale again

if we were working with floats my downscaled value would be 21.6 which I could round easily to 22 and convert to an int8. But as-is it will truncate to 21 which I don't want.

Is there a way to "round" the integer up if it would have been appropriate to do so had it been a float but without converting anything to a float (even temporarily)?

It is probably a lot simpler than I'm making it out to be.

Answer 1

You should just check if you're above or equal to 0.5 above the running_value. I.e:

int16 round = (running_value >> 7) & 1; // =1 if decimal part >= 0.5, =0 otherwise.
spot_value = running_value >> 8 + round;  //downscale again

Answer 2

You could add 1/2 to the value. In your scaled system that's 128.

int8 spot_value = 21;  //arbitrary. just need a starting point
int16 running_value;

running_value = spot_value << 8;  //multiply by 256 which is 5376
running_value += 154;  //my upscaled value is now 5530
spot_value = running_value + 128;  //add an additional 1/2 for rounding
spot_value = spot_value >> 8;  //downscale again

or...

scale_shift = 8;
scale = 1 << scale_shift
round = scale >> 1;

int8 spot_value = 21;  //arbitrary. just need a starting point
int16 running_value;

running_value = spot_value << scale_shift;  //multiply by 256 which is 5376
running_value += 154;  //my upscaled value is now 5530
spot_value = (running_value + round) >> scale_shift;  //downscale again

or a bit trick based on Dav's answer...

running_value = spot_value << scale_shift;  //multiply by 256 which is 5376
running_value += 154;  //my upscaled value is now 5530
spot_value = (running_value >> 8) + ((running_value >> 7) & 1)

.

Answer 3

Simply add something to the value before you downscale it. That is, when downshifting by 8, add 128 and it will result in a rounded value.

For the general case, when scaling down by N bits, add 1 << (N-1) before downscaling to get a rounded value.

Answer 4

running_value = spot_value << 8;  //multiply by 256 which is 5376
running_value += 154;  //my upscaled value is now 5530
if(spot_value & (1 << 7)) {
    spot_value = (running_value >> 8) + 1;  //downscale again, but add 1 since the top bit of removed was set, i.e. ">= 1/2"
} else {
    spot_value = running_value >> 8; //downscale normally
}

Answer 5

One thing I have been burned by

int8 spot_value = 21;  //arbitrary. just need a starting point
int16 running_value;

running_value = spot_value << 8;  //multiply by 256 which is 5376

You are doing a leftshift by 8 on the 8-bit variable spot_value. You are putting the value in a 16-bit variable, so it should work fine. However, if you port the code to a new micro, or switch compilers, or change optimizations, or refactor the code to an inline, etc you could inadvertently shift out your entire value.

Basically, it comes down to not trusting the compiler. On an embedded system, you don't have the robustness of gcc. I usually use an accumulator convention to compensate for this:

int8 spot_value = 21;  //arbitrary. just need a starting point
int16 running_value;

running_value = spot_value;  //load accumulator for multiply
running_value <<= 8;         //multiply accumulator (which is 21) by 256

The same principle applies for multiplication and division, especially when change bit widths.

Answer 6

Note that is is only right-shifting of signed integers that is undefined. Left shift is defined. There are three likely behaviours:

1) the compiler will use 'sign-extension' and fill the vacated MSBs with the value of the original MSB (the behaviour you need for the code given to work).

2) Fill vacated bits with zero

3) Fill vacated bits with one

It is possible I suppose but unlikely that the vacated bits are random. Personally I have never observed behaviour other than (1), but the possibility is there, and should be considered if portability and robustness is desired.

As already commented, using * and / is a solution. I have observed the generated code of a number of compilers and invariably a multiply or divide by a literal constant power-of-two will be implemented by a shift operation if on the architecture it is more efficient; even without explicitly setting an optimisation option.