title: Is there any way to improve this C bitwise function mathematically?
body: <p>I was trying to find a function that fit the following formula:</p>
  
  <pre><code>f(0,0) = ( 0, 1)
  f(0,1) = ( 2, 3)
  f(0,2) = ( 4, 5)
  f(0,3) = ( 6, 7)
  f(0,4) = ( 8, 9)
  f(0,5) = (10,11)
  f(0,6) = (12,13)
  f(0,7) = (14,15)
  f(1,0) = ( 1, 2)
  f(1,1) = ( 1, 3)
  f(1,2) = ( 5, 6)
  f(1,3) = ( 5, 7)
  f(1,4) = ( 9,10)
  f(1,5) = ( 9,11)
  f(1,6) = (13,14)
  f(1,7) = (13,15)
  f(2,0) = ( 3, 4)
  f(2,1) = ( 3, 5)
  f(2,2) = ( 3, 6)
  f(2,3) = ( 3, 7)
  f(2,4) = (11,12)
  f(2,5) = (11,13)
  f(2,6) = (11,14)
  f(2,7) = (11,15)
  </code></pre>
  
  <p>I ended up with the following:</p>
  
  <pre><code>pair f(int a, int b){
      int k = (b &gt;&gt; a &lt;&lt; (a+1)) + (1&lt;&lt;a);
      pair p = {k - 1, k + (b%(1&lt;&lt;a))};
      return p;
  };
  </code></pre>
  
  <p>There is a problem, though: the modulus operator is not implemented on the architecture I'm aiming and is, thus, making the code slow. Is there any solution that doesn't use it?</p>
  
  <p>There is a snippet to quickly test the formula:</p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  typedef struct pair_ { int x; int y; } pair;
  
  pair f(int a, int b){
      int k = (b &gt;&gt; a &lt;&lt; (a+1)) + (1&lt;&lt;a);
      pair p = {k - 1, k + (b%(1&lt;&lt;a))};
      return p;
  };
  
  int main(){
      pair correct[4][16] = {{{0,1},{2,3},{4,5},{6,7},{8,9},{10,11},{12,13},{14,15},{16,17},{18,19},{20,21},{22,23},{24,25},{26,27},{28,29},{30,31}},{{1,2},{1,3},{5,6},{5,7},{9,10},{9,11},{13,14},{13,15},{17,18},{17,19},{21,22},{21,23},{25,26},{25,27},{29,30},{29,31}},{{3,4},{3,5},{3,6},{3,7},{11,12},{11,13},{11,14},{11,15},{19,20},{19,21},{19,22},{19,23},{27,28},{27,29},{27,30},{27,31}},{{7,8},{7,9},{7,10},{7,11},{7,12},{7,13},{7,14},{7,15},{23,24},{23,25},{23,26},{23,27},{23,28},{23,29},{23,30},{23,31}}};
  
      for (int i=0; i&lt;3; ++i)
          for (int j=0; j&lt;8; ++j)
              printf("f(%.2d,%.2d) = (%.2d,%.2d) | Correct: %d %d\n",
                  i,
                  j,
                  f(i,j).x,
                  f(i,j).y,
                  f(i,j).x == correct[i][j].x,
                  f(i,j).y == correct[i][j].y);
  
      return 0;
  };
  </code></pre>