6

I need to divide number of 256 and round it to closer value, for example, if input 255 I want to get 1, not 0. Now I'm using 

int x = 150;
int z = MulDiv(x, 1, 256);

But I think it is not optimal way to reach my goal, can someone advice better way.

ST3
  • 8,826
  • 3
  • 68
  • 92

4 Answers4

7

Use this:

unsigned int x = 150;
unsigned int z = (x + 128) >> 8;

128 is middle value, so it after adding this your rounding works, and 256=2^8 so you can use bit shift operation instead of division.

NOTE: this way works for only positive values.

If you need this for positive and negative values you will need this:

int x = -150;
int z = (x >= 0 ? (x + 128) : (x - 128)) / 256;

NOTE: bit-shifting for signed values has some specific and not always can be trusted so you cannot use this: int z = (x < 0) ? (x - 128) / 256 : (x + 128) >> 8;

ST3
  • 8,826
  • 3
  • 68
  • 92
  • "you cannot use bit-shifting for signed values because it leads to undefined behavior." - that's false. What invokes UB is: 1. left-shifting into the sign bit, 2. left-shifting a negative value. You can, however: 1. left-shift and right-shift any signed (but positive) integer, 2. right-shift a negative integer (although that has an implementation-defined result). See [this question](http://stackoverflow.com/questions/3784996/why-does-left-shift-operation-invoke-undefined-behaviour-when-the-left-side-oper) and the accepted answer for more information. –  Sep 14 '13 at 14:40
  • @H2CO3 I meant that `int z = (x < 0) ? (x - 128) / 256 : (x + 128) >> 8;` is invalid code. – ST3 Sep 14 '13 at 14:42
  • @userXXX But that's not precise. "shifting a signed integer is UB" is false. So are "left-shifting a signed integer" and "shifting a negative integer". What is UB is "left-shifting a negative integer". –  Sep 14 '13 at 14:43
  • Why do you use shift instead of division? If you want to divide by 256, just use `/ 256`. Don't worry about perfomance - even in the rare cases when such differences matter, the compiler will implement division using a shift anyway. – ugoren Oct 08 '13 at 07:14
  • @ugoren it is very likely that compiler will optimize this division into shifting, however some older compilers that are sometimes used for some old projects may not include all optimizations, so it is better to help compiler. But in this case I agree that there is nothing bad to use division. – ST3 Oct 08 '13 at 09:39
4

This will work for both positive and negative integers (and zero too):

int eps = x < 0 ? -128 : 128
int y = (x + eps) / 256;

The obligatory -pedantic and f[oo|ai]lsafe version:

if (x < INT_MIN + 128 || x > INT_MAX - 128) {
    fputs("nasal demons!\n", stderr);
    abort();
}

int eps = x < 0 ? -128 : 128;
int y = (x + eps) / 256;
  • It isn't perfect, it could cause overflowing in the case of x + 128 > INT_MAX... you're slacking man! – Richard J. Ross III Sep 14 '13 at 18:04
  • Why abort for certain values of x when you could still calculate them? 1 + (x - 128) / 256 works just fine when x > INT_MAX - 128. Similarly, -1 + (x + 128) / 256 works when x < INT_MIN + 128. – fintelia Sep 14 '13 at 18:33
1

For correct rounding to nearest of signed values you can do this:

y = (x >= 0 ? (x + 128) : (x - 128)) / 256;
Paul R
  • 208,748
  • 37
  • 389
  • 560
0

To properly handle extremely large and small values you could use

int divideAndRound256(int x)
{    
    if(x > INT_MAX - 128)
        return (x - 128) / 256 + 1;
    else if(x < INT_MIN + 128)
        return (x + 128) / 256 - 1;
    else if(x < 0)
        return (x - 128) / 256;
    else
        return (x + 128) / 256;
}

Or for just unsigned values

unsigned int divideAndRound256(unsigned int x)
{    
    if(x > UINT_MAX - 128)
        return ((x - 128) >> 8) + 1;
    else
        return (x + 128) >> 8;
}
fintelia
  • 1,201
  • 6
  • 17