Index into array as if it is circular The problem:

Treat an array as if it is circular; out-of-bounds indices "wrap around" the array to become in-bounds.

Current solution:

// roudedArray.cpp
#include &lt;iostream&gt;

template &lt;typename T, int N&gt;
int wrapAroundArray(int i, T(&amp;ThisArray)[N])
{
  // "wrap" i around ThisArray, landing on a valid index
  while (i &lt; 0) { i += N; }
  while (i &gt;= N) { i -= N; }
  return i;
}

std::string words[] = { "this", "and", "that" };

int main()
{
  for (int i = -9; i &lt; 10; i++)
  {
    int adj = wrapAroundArray(i, words);
    std::cout &lt;&lt; "i: " &lt;&lt; i;
    std::cout &lt;&lt; ", adjusted index: " &lt;&lt; adj;
    std::cout &lt;&lt; ", word: " &lt;&lt; words[adj] &lt;&lt; std::endl;
  }
}


Output (compile with g++ roundedArray.cpp):


i: -9, adjusted index: 0, word: this
i: -8, adjusted index: 1, word: and
i: -7, adjusted index: 2, word: that
i: -6, adjusted index: 0, word: this
i: -5, adjusted index: 1, word: and
i: -4, adjusted index: 2, word: that
i: -3, adjusted index: 0, word: this
i: -2, adjusted index: 1, word: and
i: -1, adjusted index: 2, word: that
i: 0, adjusted index: 0, word: this
i: 1, adjusted index: 1, word: and
i: 2, adjusted index: 2, word: that
i: 3, adjusted index: 0, word: this
i: 4, adjusted index: 1, word: and
i: 5, adjusted index: 2, word: that
i: 6, adjusted index: 0, word: this
i: 7, adjusted index: 1, word: and
i: 8, adjusted index: 2, word: that
i: 9, adjusted index: 0, word: this



I'd prefer an arithmetic (constant-time) solution that produces the same results. Any suggestions?
The arithmetic solution to this is relatively simple as we're talking modulo here:

return i % N;


This should produce the same results for your adjusted index.

When I ran a few calculations on the modulo operator through WolframAlpha, I got the following results:

for \$F(x) = x \mod 3\$

\$ 5 \mapsto 2 \$
\$ 4 \mapsto 1 \$
\$ 3 \mapsto 0 \$
\$ 2 \mapsto 2 \$
\$ 1 \mapsto 1 \$
\$ 0 \mapsto 0 \$
\$-1 \mapsto 2 \$
\$-2 \mapsto 1 \$
\$-3 \mapsto 0 \$  

The pattern we see here is exactly what you describe.

@Schism pointed out that this behavior is only that of "mathematical modulo". It seems that some implementations are unfriendly in that regard. We can thus assume that we need to actually do the switching of negative numbers ourselves.

This leads to the following implementation:

if (i &lt; 0) {
   //assuming the behavior described by Schism (-1 % 3 = -1)
   i = N + (i % N);
} else {
   i = i % n;
}


Unfortunately this is still implementation-dependent, so now we need to eliminate the sign in our modulo calculations to have the same behavior, regardless of implementation:

bool wasNegative = false;
if (i &lt; 0) {
    wasNegative = true;
    i = -i; //there's definitely a bithack for this.
}
int offset = i % N;
return (wasNegative) ? (N - offset) : (offset);