Generate a pair of integers from a non-negative one

CJam, 24 22 21 bytes

My brain has trouble understanding the math other solutions are using. But my brain definitely understands binary, so here's a soultion based on bit manipulation!

li4b2fmd2/z{)(\2b^}%p

Try it online.

Explanation

This approach treats the input as two interleaved binary values, one for each output number. All but the least significant bit of each encode a magnitude, and the least significant bit signals whether or not to take the bitwise complement of this magnitude. In this implementation, the odd-positioned bits correspond to the first output number (and the even-positioned bits correspond to the second) and an LSB of 0 signals to take the complement.

For example, given an input of 73, uninterleaving its binary representation of 1001001b produces 0 1|0 (odd-positioned bits) and 1 0 0|1 (even-positioned bits). The first value has a magnitude of 01b = 1 and should be complemented for a final value of ~1 = -2, and the second value has a magnitude of 100b = 4 and should not be complemented.

Informal demonstration of correctness

I made a testing program that places each input from zero to a user-specified number minus one in its output location on a 2D grid. You can try it online as well. Here's an output of this program showing how the algorithm maps 0-99:

      -8 -7 -6 -5 -4 -3 -2 -1  0  1  2  3  4  5  6  7  8

-8                      92 84 86 94                     
-7                      88 80 82 90                     
-6                      76 68 70 78                     
-5                   96 72 64 66 74 98                  
-4                60 52 28 20 22 30 54 62               
-3                56 48 24 16 18 26 50 58               
-2                44 36 12  4  6 14 38 46               
-1                40 32  8  0  2 10 34 42               
 0                41 33  9  1  3 11 35 43               
 1                45 37 13  5  7 15 39 47               
 2                57 49 25 17 19 27 51 59               
 3                61 53 29 21 23 31 55 63               
 4                   97 73 65 67 75 99                  
 5                      77 69 71 79                     
 6                      89 81 83 91                     
 7                      93 85 87 95                     
 8                                                      

The fill pattern looks a bit weird, but it is in fact bijective! With each successive power of 4, it fills a square with double the previous side length. For example, here's how the algorithm maps 0-15:

      -2 -1  0  1  2

-2    12  4  6 14   
-1     8  0  2 10   
 0     9  1  3 11   
 1    13  5  7 15   
 2                  

This makes up the 4x4 square in the middle of the 8x8 square of 0-63:

      -4 -3 -2 -1  0  1  2  3  4

-4    60 52 28 20 22 30 54 62   
-3    56 48 24 16 18 26 50 58   
-2    44 36 12  4  6 14 38 46   
-1    40 32  8  0  2 10 34 42   
 0    41 33  9  1  3 11 35 43   
 1    45 37 13  5  7 15 39 47   
 2    57 49 25 17 19 27 51 59   
 3    61 53 29 21 23 31 55 63   
 4                              

Which makes up the 8x8 square in the middle of the 16x16 square of 0-255:

         -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   5   6   7   8

 -8     252 244 220 212 124 116  92  84  86  94 118 126 214 222 246 254    
 -7     248 240 216 208 120 112  88  80  82  90 114 122 210 218 242 250    
 -6     236 228 204 196 108 100  76  68  70  78 102 110 198 206 230 238    
 -5     232 224 200 192 104  96  72  64  66  74  98 106 194 202 226 234    
 -4     188 180 156 148  60  52  28  20  22  30  54  62 150 158 182 190    
 -3     184 176 152 144  56  48  24  16  18  26  50  58 146 154 178 186    
 -2     172 164 140 132  44  36  12   4   6  14  38  46 134 142 166 174    
 -1     168 160 136 128  40  32   8   0   2  10  34  42 130 138 162 170    
  0     169 161 137 129  41  33   9   1   3  11  35  43 131 139 163 171    
  1     173 165 141 133  45  37  13   5   7  15  39  47 135 143 167 175    
  2     185 177 153 145  57  49  25  17  19  27  51  59 147 155 179 187    
  3     189 181 157 149  61  53  29  21  23  31  55  63 151 159 183 191    
  4     233 225 201 193 105  97  73  65  67  75  99 107 195 203 227 235    
  5     237 229 205 197 109 101  77  69  71  79 103 111 199 207 231 239    
  6     249 241 217 209 121 113  89  81  83  91 115 123 211 219 243 251    
  7     253 245 221 213 125 117  93  85  87  95 119 127 215 223 247 255    
  8                                                                        

Pyth, 15

u,-HyeGhGjQ2,ZZ

Try it online.

u             reduce
                lambda G,H:    [implicit]
  ,-HyeGhG         (H-2*G[-1],G[0])
  jQ2           base(input(),2)
  ,ZZ           (0,0)
              print result     [implicit]

A Python translation:

g=lambda Z,n:(n-2*Z[1],Z[0])
print reduce(g,binlist(input()),(0,0))

or iteratively:

(x,y)=(0,0)
for b in binlist(input()):
    (x,y)=(b-2*y,x)
print (x,y)

where binlist converts a number to a list of digits like binlist(4) = [1,0,0].

So, how does this work? It interprets the binary digits of the number \$n\$ as two interleaved numbers in base negative two like in my Python solution.

The binary number $$n=\dots b_5 b_4 b_3 b_2 b_1 b_0 $$ corresponds to the pair $$ (x,y) = (b_0 - 2 b_2 + 4 b_4 - 8 b_6 + \cdots, b_1 - 2 b_3 + 4 b_5 - 8 b_7 + \cdots).$$

If we hadn't yet processed the last digit \$b_0\$ of \$n\$, we'd have all indices higher by $1$, $$n'=\dots b_5 b_4 b_3 b_2 b_1 $$ corresponding to the pair $$ (x',y') = (b_1 - 2 b_3 + 4 b_5 - 8 b_7 + \cdots, b_2 - 2 b_4 + 4 b_6 - 8 b_8 + \cdots).$$

We can then express the new values once \$b_0\$ is read in terms of the old values

$$(x,y) = (b_0 - 2y', x').$$

So, by repeatedly performing the transformation \$(x,y) \to (b - 2y, x)\$ on each successive bit \$b\$ of \$n\$, we build the point \$(x,y)\$ that comes from extracting its digits.


Python 2, 49

Edit: Improved to 49 by using better one-step recursion for base -2.

def f(n):x,y=n and f(n/2)or(0,0);return n%2-2*y,x

Here's a Pyth version using reduce.

Edit: Improved to 52 by switching to base -2 from balanced ternary.

Python 2, 52

h=lambda n:n and n%2-2*h(n/4)
lambda n:(h(n),h(n/2))

Python 2, 54

h=lambda n:n and-~n%3-1+3*h(n/9)
lambda n:(h(n),h(n/3))

This uses digit interleaving like Runer112's solution, but with balanced ternary rather than signed binary. Python doesn't have built-in base conversion, so the code implements it recursively.

The helper function h (with 3 in place of the 9) takes a natural number and converts it from ternary to balanced ternary with the digit substitutions

0 -> 0 
1 -> +1
2 -> -1

So, for example, 19, which is 201 in base, becomes (-1)(0)(+1) in balanced ternary, which is (-1)*3^2 +(0)*3^1+(+1)*3^0 = -8.

Balanced ternary suffices to encode every integer, and so gives a mapping from natural numbers to integers.

To map to pairs of integers, we interleave the digits in n. To do so, we have h look at every other digit by doing n/9 as the recursive step rather than n/3. Then, for one coordinate, we shift n by floor-dividing by 3.

Here are the first 81 outputs, which cover the region [-4,4]^2.

0 (0, 0)
1 (1, 0)
2 (-1, 0)
3 (0, 1)
4 (1, 1)
5 (-1, 1)
6 (0, -1)
7 (1, -1)
8 (-1, -1)
9 (3, 0)
10 (4, 0)
11 (2, 0)
12 (3, 1)
13 (4, 1)
14 (2, 1)
15 (3, -1)
16 (4, -1)
17 (2, -1)
18 (-3, 0)
19 (-2, 0)
20 (-4, 0)
21 (-3, 1)
22 (-2, 1)
23 (-4, 1)
24 (-3, -1)
25 (-2, -1)
26 (-4, -1)
27 (0, 3)
28 (1, 3)
29 (-1, 3)
30 (0, 4)
31 (1, 4)
32 (-1, 4)
33 (0, 2)
34 (1, 2)
35 (-1, 2)
36 (3, 3)
37 (4, 3)
38 (2, 3)
39 (3, 4)
40 (4, 4)
41 (2, 4)
42 (3, 2)
43 (4, 2)
44 (2, 2)
45 (-3, 3)
46 (-2, 3)
47 (-4, 3)
48 (-3, 4)
49 (-2, 4)
50 (-4, 4)
51 (-3, 2)
52 (-2, 2)
53 (-4, 2)
54 (0, -3)
55 (1, -3)
56 (-1, -3)
57 (0, -2)
58 (1, -2)
59 (-1, -2)
60 (0, -4)
61 (1, -4)
62 (-1, -4)
63 (3, -3)
64 (4, -3)
65 (2, -3)
66 (3, -2)
67 (4, -2)
68 (2, -2)
69 (3, -4)
70 (4, -4)
71 (2, -4)
72 (-3, -3)
73 (-2, -3)
74 (-4, -3)
75 (-3, -2)
76 (-2, -2)
77 (-4, -2)
78 (-3, -4)
79 (-2, -4)
80 (-4, -4)

An alternative coding with quarter-imaginary turned out longer, though it is very pretty.

Python 2, 63

h=lambda n:n and n%4+2j*h(n/4)
lambda n:(h(n).real,h(n).imag/2)

In a language with less clunky handling of complex conversion, this would probably be a better approach. If we could output complex numbers, we could do:

Python 2, 38

f=lambda n:n and n%2+n/2%2*1j-2*f(n/4)