Complex Binary Numbers

Question

Let's create a simple, surjective mapping from positive integers to Gaussian integers, which are complex numbers 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'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.

• Erik the Outgolfer: From the title I thought that the challenge would be about complex numbers in binary, e.g. 4+2j -> 100+10j...

Answer 1

MATL, 7 bytes

BJ*Y'^s

Try it online!

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

• Stewie Griffin: 7 bytes in MATL, and the best I can get is 58 in MATLAB... You've made a nice little language there! =)
• Magic Octopus Urn: @StewieGriffin easily the best in show when it comes to graphing or plotting, perhaps also for matrix arithmetic too from the awesome answers I've seen him post.

Answer 2

Jelly, 8 bytes

BŒgaıP€S

Try it online!

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 3

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...

• ETHproductions: That (k or 1) doesn't seem optimal, but the only other thing I can think of is (k+0**k)...
• Sp3000: @ETHproductions My thoughts exactly, but unfortunately 0**k doesn't work for complex k...

Answer 4

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)

• martin: minus 1 byte: Tr[Times@@@(I*Split@RealDigits[#,2][[1]])]&
• JungHwan Min: @martin Well, I used your idea of multiplying I first, but IntegerDigits ended up being shorter.
• martin: yes - much better :)

Answer 5

Python 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!

Answer 6

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], i² (or -1) as [-1,0], i³ (or -i) as [0,-1], and i⁴ (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 iⁿ. 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 7

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!

• Griffin: I got something quite similar so won't post separate answer, bit shorter though sum(1j**x.count('1')for x in bin(input()).split('0')if x)
• hyperneutrino: @Griffin Nice. I think it's different enough that you could post a separate answer, since it uses a different method of counting the 1 blocks and it doesn't use regex like mine does. Also, I don't want to steal the code from you since it's a lot better than my version. :)
• hyperneutrino: @Griffin I found another solution that's the same length as your solution except instead of counting 1s rather than length, it takes the 0x part off the front first. Thanks for the idea of moving the if to the end; I never would've known that works otherwise!
• Griffin: you don't need the list comprehension. Remove the square brackets to make it a generator expression
• hyperneutrino: @Griffin Oh. Okay, thanks! I'll remember that for future golfing

Answer 8

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--.

• Luis Mendo: Always +1 for using eval :-P Can't you use 1i instead of 1*i?
• Luis Mendo: Oh you're is using it differently. Very clever!
• Stewie Griffin: Thanks :-) I must admit, I was quite satisfied with the i*1 part...

Answer 9

Pyth - 15 bytes

Frustratingly long.

s^L.j)hMe#r8jQ2

Test Suite.

Answer 10

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.

• hyperneutrino: Wow, I'm surprised that Mathematica doesn't have a built-in for this!

Answer 11

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 12

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 13

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 14

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 15

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 16

Actually, 35 bytes

├'0' aÆô' @s"j+"j'jo`"1j*1"'1τ(Æ`Y≡

Try it online!

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!

• Sherlock9: Splitting on '0's with '0@s and using ``░ to trim any trailing empty strings should save you four bytes.

Answer 17

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!

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.

• user58988: In the link above The input 1 return 1j the input 2 return 1j.... Is that right?
• Sherlock9: @RosLuP Yes, that's right? Since we remove trailing 0's, 1 => 1 => 1j is equivalent to 2 => 10 => 1 => 1j.

Answer 18

Actually, 15 bytes

Golfing suggestions welcome! Try it online!

├'0@s``░`lïn`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.
 ïn Yield the imaginary unit to the power of that length.
Σ Sum all of this into one complex number.

Answer 19

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 20

Perl 6, (削除) 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 implementation on MoarVM.
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

• Brad Gilbert b2gills: Bug report filed

Answer 21

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 22

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 23

Java, 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!

Answer 24

R, 54 bytes

function(n,x=rle(n%/%2^(0:log2(n))%%2))sum(1i^x$l*x$v)

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 25

APL(Dyalog Extended), ^{(削除) (削除ここまで)}13 bytes ^SBCS

×ばつ/ ×ばつ⊆⍨⊤⎕

Try it on APLgolf!

A tradfn submission which takes a decimal number.