An algorithm to wrap/overflow number based on max value

Question

Anyone for a challenge? I am looking for an efficient algorithm to achieve a wrap/overflow behavior for a number fixed with max value.

Say, the max possible number value is defined as:

#define MAX_NUMBER_VALUE 100

And a function translate that takes a signed 32-bit or 64-bit integer value and "wraps it around" using that MAX_NUMBER_VALUE constant:

int_fast8_t translate(int_fast32_t value) {

  if (abs(value) > MAX_NUMBER_VALUE) {
    return ...; // This!
  }

  return value;
}

The expected input and output:

translate(55)   => 55
translate(100)  => 100
translate(101)  => -100
translate(102)  => -99
translate(200)  => -1
translate(202)  => 1
translate(300)  => 99
translate(-40)  => -40
translate(-100) => -100
translate(-101) => 100
translate(-102) => 99
translate(-200) => 1
translate(-201) => 0
...

The value "walks" around the number as if it was a round planet. This does look similar to how C/C++ handles int overflow conditions. I wonder if there is a fast and efficient way to achieve this kind of wrapping? Like with bit shifting or other bitwise operations?

You basically need to do a modulus over `MAX_NUMBER_VALUE*2 - 1`... — Mysticial, Jan 10 '13 at 15:34

score 5 · Answer 1 · answered Jan 10 '13 at 15:35

5

It sounds like you're just describing the % operator, with some careful treatment of negative numbers.

answered Jan 10 '13 at 15:35

Oliver Charlesworth

267,707
33
569
680

2

You should elaborate on this "careful treatment of negative numbers" - this is the important aspect of the question I believe. I doubt the answer will be very useful as is. – amit Jan 10 '13 at 15:46
Yes, I am well aware the modulus operator is most likely unavoidable here. Still, I wonder if there are any alternatives as with bit shifting. – Sim Jan 10 '13 at 15:54
@Sim: For arbitrary values of `MAX`, not really. You could always define a massive lookup table, but that probably wouldn't be faster due to terrible cache performance! – Oliver Charlesworth Jan 10 '13 at 15:55
@OliCharlesworth: Thanks. I am just curious how would I write the wrapping with bit shifting if my MAX_NUMBER_VALUE could be expressed as 2^n? – Sim Jan 10 '13 at 16:02
@Sim: Assuming 2's complement, then you should be able to just do `x &= (2*n-1); if (x >= n) x -= 2*n;`. – Oliver Charlesworth Jan 10 '13 at 16:43

score 2 · Accepted Answer · edited May 23 '17 at 12:04

2

int_fast8_t translate(int_fast32_t value) {
  return sgn(value)*( (abs(value)+MAX)%(2*MAX+1)-MAX )
}

should do it, assuming modular division is defined for the int_fast32_t type

edited to include handling of negative numbers but it looks a bit messier now. For a smart implementation of sgn(x) see this

edited May 23 '17 at 12:04

Community

1
1

answered Jan 10 '13 at 15:43

nrussell

358
1
7

Are you sure you want the range of the output to be the _closed_ interval [-MAX_NUMBER_VALUE, MAX_NUMBER_VALUE]? It would be more natural to use the semi-open interval [-MAX_NUMBER_VALUE, MAX_NUMBER_VALUE) or (-MAX_NUMBER_VALUE, MAX_NUMBER_VALUE] – nrussell Jan 10 '13 at 15:44
Thanks, but I don't think this will wrap for negative numbers, say -101: `(-101+100)%(2*100+1)-100 = -101`. – Sim Jan 10 '13 at 16:10
Of course, sorry. I should have paid attention to the previous comment about "careful handling of negative numbers" – nrussell Jan 10 '13 at 16:13
Either my math is wrong or it is still not wrapping for negative numbers: `-101 => -1*(101+100)%(2*100+1)-100 = -100`! :) – Sim Jan 10 '13 at 16:55

score 0 · Answer 3 · answered Jan 10 '13 at 16:39

0

As long as your input + MAX_VALUE is less than the max value of the integral type in question I think you can use this, not even requiring the initial abs check:

return ((input + MAX_VALUE) % (MAX_VALUE * 2 + 1)) - MAX_VALUE;

answered Jan 10 '13 at 16:39

Mark B

95,107
10
109
188

nrussell has suggested this before, however this does not wrap for negative numbers, say -101: `(-101+100)%(100*2+1)-100 = -101` – Sim Jan 10 '13 at 16:45

An algorithm to wrap/overflow number based on max value

3 Answers3