[Question]
  [
Let's create a simple, [surjective](https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection) mapping from positive integers to [Gaussian integers](https://en.wikipedia.org/wiki/Gaussian_integer), which are [complex numbers](https://en.wikipedia.org/wiki/Complex_number) where the real and imaginary parts are integers.
Given a positive integer, for example `4538`, express it in binary with no leading `0`'s:
```
4538 base 10 = 1000110111010 base 2
```
Remove any trailing `0`'s:
```
100011011101
```
Replace any runs of one or more `0`'s with a single `+`:
```
1+11+111+1
```
Replace all `1`'s with [`i`](https://en.wikipedia.org/wiki/Imaginary_unit)'s:
```
i+ii+iii+i
```
Evaluate the resulting complex expression and output the simplified Gaussian integer:
```
i+ii+iii+i = i+i*i+i*i*i+i = 2i+i^2+i^3 = 2i+(-1)+(-i) = -1+i
```
The output can be expressed in a traditional mathematical way, or given as two separate integers for the real and complex parts. For the `4538` example, any of these would be fine:
```
-1+i
i-1
-1+1i
(-1, 1)
-1 1
-1\n1
```
For inputs like `29`, mathy formatted outputs such as `0`, `0i`, or `0+0i` are all fine.
Using `j` (or something else) instead of `i` is fine if that is more natural for your language.
The shortest code in bytes wins.
  
[Answer]
# [MATL](http://github.com/lmendo/MATL), 7 bytes
```
BJ*Y'^s
```
[Try it online!](http://matl.tryitonline.net/#code=QkoqWSdecw&input=NDUzOA)
### How it works
Consider input `4538` for example.
```
B     % Implicit input. Convert to binary
      % STACK: [1 0 0 0 1 1 0 1 1 1 0 1 0]
J*    % Multiply by 1i
      % STACK: [1i 0 0 0 1i 1i 0 1i 1i 1i 0 1i 0]
Y'    % Run-length encoding
      % STACK: [1i 0 1i 0 1i 0 1i 0], [1 3 2 1 3 1 1 1]
^     % Power, element-wise
      % STACK: [1i 0 -1 0 -1i 0 1i 0]
s     % Sum of array. Implicit display
      % STACK: -1+1i
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 8 bytes
```
BŒgaıP€S
```
[Try it online!](https://tio.run/nexus/jelly#@@90dFJ64pGNAY@a1gT////fxNTYAgA "Jelly – TIO Nexus")
### How it works
```
BŒgaıP€S  Main link. Argument: n (integer)
B         Convert to binary.
          If n = 4538, this yields [1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0].
 Œg       Group equal elements.
          This yields [[1], [0, 0, 0], [1, 1], [0], [1, 1, 1], [0], [1], [0]].
   aı     Logical AND with the imaginary unit.
          This yields [[ı], [0, 0, 0], [ı, ı], [0], [ı, ı, ı], [0], [ı], [0]].
     P€   Product each.
          This yields [ı, 0, -1, 0, -ı, 0, ı, 0].
       S  Sum.
          This yields -1+ı.
```
[Answer]
## Python 2, 53 bytes
```
f=lambda n,k=0:(n and f(n/2,n%2*(k or 1)*1j))+~n%2*k
```
Been trying to golf this and it seems golfable but I'm out of ideas atm...
[Answer]
# Mathematica, ~~44~~ 38 bytes
```
Tr[1##&@@@Split[I*#~IntegerDigits~2]]&
```
# Explanation
```
#~IntegerDigits~2
```
Convert the input into base 2. (`4538` becomes `{1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0}`)
```
I*
```
Multiply by `I` (`{1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0}` becomes `{I, 0, 0, 0, I, I, 0, I, I, I, 0, I, 0}`)
```
Split
```
Split by runs (`{I, 0, 0, 0, I, I, 0, I, I, I, 0, I, 0}` becomes `{{I}, {0, 0, 0}, {I, I}, {0}, {I, I, I}, {0}, {I}, {0}}`)
```
1##&@@@ ...
```
Find the product at level 2. (`{{I}, {0, 0, 0}, {I, I}, {0}, {I, I, I}, {0}, {I}, {0}}` becomes `{I, 0, -1, 0, -I, 0, I, 0}`)
```
Tr
```
Sum the result. (`{I, 0, -1, 0, -I, 0, I, 0}` becomes `-1 + I`)
[Answer]
# [Python 2](https://docs.python.org/2/), ~~77~~ ~~76~~ 71 bytes
```
p=r=0
for n in bin(input()*2):t=n=='1';r-=p*~-t;p=p*t*1jor t*1j
print r
```
*Thanks to @ZacharyT for golfing off 1 byte!*
[Try it online!](https://tio.run/nexus/python2#@19gW2RrwJWWX6SQp5CZp5CUmaeRmVdQWqKhqWWkaVVim2drq26obl2ka1ugVadbYl0ApEu0DLOAGkAUV0FRZl6JQtH//yamxhYA "Python 2 – TIO Nexus")
[Answer]
# JavaScript (ES6), ~~67~~ 64 bytes
```
f=(n,q=0,a=[0,0])=>q|n?f(n/2,n&1?q+1:q&&0*(a[q&1]+=1-(q&2)),a):a
```
```
<input oninput="O.innerHTML=f(this.value)" type="number" step=1 min=0 value="4538">
<pre id=O></pre>
```
Outputs as a 2-element array.
### Explanation
Since JavaScript doesn't have imaginary numbers, we have to keep track of the real and imaginary parts in separate variables. The easiest way to do this is in a single array, with the real part first. **i** is represented as **[0,1]**, **i2** (or **-1**) as **[-1,0]**, **i3** (or **-i**) as **[0,-1]**, and **i4** (or **1**) as **[1,0]**.
First, we repeatedly divide the number by 2, collecting each run of ones in its binary representation. Each run of **n** ones corresponds to **in**. This corresponds to adding **1 - (n & 2)** to the item at index **n & 1** in the two-item array. So that's we do.
I should probably add more explanation, but I can't think of what else needs explaining. Feel free to comment with any questions you might have.
[Answer]
# Python, ~~199~~ ~~129~~ ~~124~~ ~~116~~ ~~94~~ ~~90~~ ~~71~~ ~~63~~ 61 bytes
```
print sum(1j**len(s)for s in bin(input())[2:].split('0')if s)
```
Input is just the number itself.  
Output is in the format `(a+bj)`, where `j` is the imaginary unit. `0j` will be output instead of `(0+0j)`
First convert to binary. Truncate the `'0b'` off. Kill the trailing zeros. Split using a block of zero(s) as a delimiter. Map each block to `1j ** len`. Then, take the sum of the entire thing.
**-70 bytes** by not converting to pluses.  
*-5 bytes* regex is shorter.  
*-8 bytes* by getting rid of the two unnecessary variables that were only being called once.  
*-22 bytes* by using complex numbers instead of my weird thing. Thanks to @Dennis' answer for informing me of complex numbers!  
*-4 bytes* by realizing that `map` is just a fancy way of doing list comprehensions, except longer.  
*-19 bytes* by switching to a slightly arcane method of avoiding errors with `j ** 0` and avoiding regex. Inspired by @Griffin's comment. Thanks! :)  
*-8 bytes* by moving the `if` part to the end.  
*-2 bytes* Thanks to @Griffin for saving 2 bytes by removing the square brackets to make it a generator expression instead!
[Answer]
# MATLAB, 58 bytes
```
@(x)eval([strrep(strrep(dec2bin(x),48,43),49,'i*1'),'.0'])
dec2bin(x) % converts the decimal value to a binary string of 1s and 0s.
strrep(dec2bin(x),48,43) % Substitutes ASCII character 48 with 43 (0s become +)
strrep(___,49,'i*1')     % Substitutes ASCII character 49 with 'i*1'
                         % 1s become 'i*1' (this is the gem)
eval([___,'.0']          % Appends .0 in the end and evaluates the expression.   
```
Let's use `285` to illustrate the process:
```
temp1 = dec2bin(285)
      = 100011101
temp2 = strrep(temp1,48,43)
      = 1+++111+1
```
Luckily `1+++1` behaves just as `1+1` in MATLAB, so the above evaluates to: `1+111+1`.
```
temp3 = strrep(temp2,49,'i*1')
      = i*1+++i*1i*1i*1+i*1
```
Now this `strrep`-call is the real gem! By inserting `i*1` for `1` we get something really nice. If there's only one `1`, we simply get `i*1` which is `i`. If there are more than one then `i*1` gets repeated and concatenated into a sequence: `i*1i*1i*1i*1`. Since `i==1i` in MATLAB and `1i*1==i` this is simply: `i*i*i*i`.
```
temp4 = [temp3,'.0']
      = i*1+++i*1i*1i*1+i*1.0
```
Appending `.0` seems unnecessary here, but it's needed if the last character of `temp3` is a `+`. We can't append just a zero, since that would give `i*10` in the case above and therefore the wrong result.
And finally:
```
eval(temp4)
0.0000 + 1.0000i
```
This doesn't work in Octave for several reasons. `strrep` can't take ASCII-values as input, it needs the actual characters (`'0'` instead of `48`). Also, `+++` doesn't evaluate to just `+` in Octave, as that would break the increment/decrement shortcuts `x++` and `x--`.
[Answer]
# Pyth - 15 bytes
Frustratingly long.
```
s^L.j)hMe#r8jQ2
```
[Test Suite](http://pyth.herokuapp.com/?code=s%5EL.j%29hMe%23r8jQ2&test_suite=1&test_suite_input=4538%0A29&debug=0).
[Answer]
# Mathematica, 84 bytes
```
ToExpression[#~IntegerString~2~StringTrim~"0"~StringReplace~{"0"..->"+","1"->"I "}]&
```
Anonymous function. Takes a number as input and returns a complex number as output.
[Answer]
# Mathematica, 75 bytes
```
ToExpression[#~IntegerString~2~StringReplace~{"1"->"I ","0"..->"+"}<>"-0"]&
```
Independently came up with almost the same solution that LegionMammal978 posted 23 minutes ago! Replacing `1` with `I`  (which is Mathematica's internal symbol for the square root of -1) works because spaces are treated as multiplication of neighboring expressions. The place I saved on the other solution, namely by avoiding the need for `StringTrim`, is by always appending `-0`: if the binary number ends in `1`, then this expression ends in `...I-0` which doesn't affect its value; while if the binary number ends in '0', then this expression ends in `...+-0` which is parsed as "add negative 0" and thus gets rid of the trailing plus sign.
[Answer]
# Matlab, 99 Bytes
```
function c=z(b)
c=0;b=strsplit(dec2bin(b),'0');for j=1:numel(b)-isempty(b{end});c=c+i^nnz(b{j});end
```
Test cases:
```
z(656) = 3i
z(172) = -1 + 2i
z(707) = -2 + i
z(32)  = i
z(277) = 4i
```
[Answer]
# Haskell, ~~102~~ ~~91~~ ~~89~~ 87 bytes
```
0%a=a
n%c@[a,b]|odd n=div n 2%[-b,a]|d<-div n 2=zipWith(+)c$d%[mod d 2,0]
(%[0,0]).(*2)
```
Repeatedly divides by two and checks the bit. Keeps an accumulator of `i^(number of odds)` where `a+b*i` is encoded as `[a,b]` and `*i` is `[a,b]↦[-b,a]` (rotation by 90 degrees). The initial `(*2)` is to avoid a lookup for the first bit.
Usage (thanks to @OwenMorgan for the examples):
```
(%[0,0]).(*2)<$>[656,172,707,32,277]
[[0,3],[-1,2],[-2,1],[0,1],[0,4]]
```
[Answer]
# Java, 172 bytes
```
l->{int i=0,j=i;for(String x:l.toString(2).split("0")){int a=x.length();j+=a&1>0?(a&3>2?(a-3)/-4+1:(a-3)/4+1):0;i+=a&1<1?(a&3>1?(a-3)/4+1:(a-3)/-4+1):0;}return i+"|"j+"i";}
```
[Answer]
# Clojure, 183 bytes
```
#(loop[x(clojure.string/split(Integer/toString % 2)#"0+")y[0 0]a 0](if(= a(count x))y(recur x(let[z([[1 0][0 1][-1 0][0 -1]](mod(count(x a))4))][(+(y 0)(z 0))(+(y 1)(z 1))])(inc a))))
```
Am I allowed to do this?
Use the function like so:
```
(#(...) {num}) -> (Wrap the # function in brackets first!)
```
[Answer]
# [Actually](http://github.com/Mego/Seriously), 35 bytes
```
├'0' aÆô' @s"j+"j'jo`"1j*1"'1τ(Æ`Y≡
```
[Try it online!](https://tio.run/nexus/actually#@/9oyhx1A3WFxMNth7eoKzgUK2VpK2WpZ@UnKBlmaRkqqRueb9E43JYQ@ahz4f//JqbGFgA "Actually – TIO Nexus")
Explanation:
```
├'0' aÆô' @s"j+"j'jo`"1j*1"'1τ(Æ`Y≡
├                                    binary representation of input
 '0' aÆ                              replace 0s with spaces
       ô                             trim leading and trailing spaces
        ' @s                         split on spaces
            "j+"j                    join with "j+"
                 'jo                 append "j"
                    `"1j*1"'1τ(Æ`Y   do until the string stops changing (fixed-point combinator):
                     "1j*1"'1τ(Æ       replace "11" with "1j*1"
                                  ≡  evaluate the resulting string to simplify it
```
Roughly equivalent Python 3 code:
```
a='j+'.join(bin(eval(input()))[2:].replace('0',' ').strip().split())+'j'
b=0
while a!=b:b,a=a,a.replace("11","1j*1")
print(eval(a))
```
[Try it online!](https://tio.run/nexus/python3#PY3NCgIhFEb3PsXk5npnRMZ@IAZ8kmhxDaErYmJOPb5NBC0@zuYcvk4O4gQmPjgrvy28KCnOZW0KES/75WpqKIluQcEMGgZA82yVi9pYEn@1CSII72bxvnMKA@2cX7wmR5r@sbRWamnjaCWKUjm33xUh9n48Hc4f "Python 3 – TIO Nexus")
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), 10 bytes
This isn't better than Dennis's Jelly answer, but I wanted to try my hand at a Jelly answer anyway. Golfing suggestions welcome! [Try it online!](http://jelly.tryitonline.net/#code=QsWScm0y4bmq4oKsxLEqUw&input=&args=NDUzOA)
```
BŒrm2Ṫ€ı*S
```
**Ungolfing**
```
BŒrm2Ṫ€ı*S   Main link. Argument: n (integer)
B            Convert n to binary.
 Œr          Run-length encode the binary list.
   m2        Every 2nd element of the run_length encoding, getting only the runs of 1s.
     Ṫ€      Tail each, getting only the lengths of the runs.
       ı*    The imaginary unit raised to the power of each run (as * is vectorized).
         S   Sum it all into one complex number.
```
[Answer]
# [Actually](https://github.com/Mego/Seriously), 15 bytes
Golfing suggestions welcome! [Try it online!](https://tio.run/nexus/actually#AR4A4f//4pScJzBAc2Bg4paRYGzDr@KBv2BNzqP//zQ1Mzg "Actually – TIO Nexus")
```
├'0@s``░`lïⁿ`MΣ
```
**Ungolfing:**
```
         Implicit input n.
├        Convert n to binary.
'0@s     Split by '0's.
``░      Filter out non-truthy values.
`...`M   Map over the filtered result, a list of runs of '1's.
  l        Yield the length of the run of '1's.
  ïⁿ       Yield the imaginary unit to the power of that length.
Σ        Sum all of this into one complex number.
```
[Answer]
# Axiom, ~~140, 131, 118~~ 108 bytes
```
b(x)==(s:=0;repeat(x=0=>break;r:=x rem 2;repeat(x rem 2=1=>(r:=r*%i;x:=x quo 2);break);s:=s+r;x:=x quo 2);s)
```
%i is the imaginary costant.Ungolfed
```
sb(x:NNI):Complex INT==
  r:Complex INT;s:Complex INT:=0
  repeat
    x=0=>break
    r:=x rem 2
    repeat
       x rem 2=1=>(r:=r*%i;x:=x quo 2)
       break
    s:=s+r
    x:=x quo 2
  s
```
results
```
(3) -> b 4538
   The type of the local variable r has changed in the computation.
   We will attempt to interpret the code.
   (3)  - 1 + %i
                                                    Type: Complex Integer
(4) -> b 29
   (4)  0
                                                    Type: Complex Integer
(5) -> sb 299898979798233333333333333339188888888888888888222
   Compiling function sb with type NonNegativeInteger -> Complex Integer
   (5)  - 7 + 12%i
                                                    Type: Complex Integer
(6) -> b 299898979798233333333333333339188888888888888888222
   (6)  - 7 + 12%i
                                                    Type: Complex Integer
```
[Answer]
# [Perl 6](https://perl6.org), ~~40~~ 46 bytes
I came up with this fairly quickly
```
*.base(2).comb(/1+/).map(i***.chars).sum
```
Unfortunately it is currently inaccurate in the [Rakudo](http://rakudo.org) implementation on [MoarVM](http://moarvm.org).  
`say i ** 3; # -1.83697019872103e-16-1i`
So I had to do the next best thing:
```
*.base(2).comb(/1+/).map({[*] i xx.chars}).sum
```
## Expanded:
```
*\             # Whatever lambda
.base(2)       # convert to a Str representation in base 2
.comb(/ 1+ /)  # get a list of substrings of one or more ｢1｣s
.map({         # for each of those
  [*]            # reduce using ｢&infix:<**>｣
    i xx .chars    # ｢i｣ list repeated by the count of the characters matched
}).sum          # sum it all up
```
## Test:
```
.say for (4538, 29).map:
    *.base(2).comb(/1+/).map({[*] i xx.chars}).sum
# -1+1i
# 0+0i
```
[Answer]
# PHP, 87 bytes
```
for($n=$argv[1];$n|$i;$n>>=1)$n&1?$i++:($i?$i=0*${$i&1}+=1-($i&2):0);echo"(${0},${1})";
```
Almost the same as ETHproductions´ solution; only iterative instead of recursive.  
Takes input from command line, sets variables `${0}` and `${1}`.
[Answer]
# TI-Basic (TI-84 Plus CE), 70 bytes
```
Prompt X
0→S
0→N
While X
If remainder(X,2
Then
N+1→N
int(X/2→X
Else
S+i^Nnot(not(N→S
X/2→X
0→N
End
End
S+i^Nnot(not(N
```
There's no builtin to convert to a binary string, (nor is there to parse a string), so this program manually divides by 2, incrementing N each time it sees a 1 and adding i^N to S (N>0) and resetting N if it sees a zero.
[Answer]
# [Java](http://openjdk.java.net/), 100 bytes
```
int[]f(int n){int c=2,r[]=new int[2];for(;n>0;r[c&1]+=n%4==1?(c&2)-1:0,n/=2)c=n%2<1?2:c+1;return r;}
```
[Try it online!](https://tio.run/nexus/java-openjdk#pY9BbsIwEEXX5RTegGxBXWxAbXFd1AN0xTLywrgJMgpONJ5QoShnT51yBK@eNF/z/kzbnWrviKttjOTb@tCPPmBhKppAAusnOC1XUBgdyl8ypdKoqgGqwudaQeEWwix1mG@1FgfqFpI9i/16FV60ZC7N5Yc4yL1bCgUldhAIqGFsH70RLSbcGv9DrqmdHhF8OBfGwjmyfvZ0vEcsr7zpkLcpwTrQi71Z3qGv@ReAvUeOzWOLTvdNP1DGKyoYYypHsMkVvOYKxC7XIN9zDdvd5u3fMcyG8Q8 "Java (OpenJDK 8) – TIO Nexus")
[Answer]
# [R](https://www.r-project.org/), 54 bytes
```
function(n,x=rle(n%/%2^(0:log2(n))%%2))sum(1i^x$l*x$v)
```
[Try it online!](https://tio.run/##K/qfpmCj@z@tNC@5JDM/TyNPp8K2KCdVI09VX9UoTsPAKic/3UgjT1NTVdVIU7O4NFfDMDOuQiVHq0KlTPN/moaJqbGFJleahpGl5n8A "R – Try It Online")
`n%/%2^(0:log2(n))%%2` computes a vector of the binary digits. Using the run-length encoding, we use R's `complex` type to compute the appropriate sum, multiplying by the `x$values` to remove zeros.
Returns a `complex` vector of one element.
[Answer]
# [APL(Dyalog Extended)](https://github.com/abrudz/dyalog-apl-extended), 13 bytes [SBCS](https://github.com/abrudz/SBCS)
```
+/×/¨0j1×⊆⍨⊤⎕
```
[Try it on APLgolf!](https://razetime.github.io/APLgolf/?h=AwA&c=09Y/PF3/0AqDLMPD0x91tT3qXfGoa8mjvqkA&f=AwA&i=S@MyMTW2AAA&r=tio&l=apl-dyalog-extended&m=tradfn&n=f)
A tradfn submission which takes a decimal number.
]