The Binary Binary Expansion

Question

Normally, we decompose a number into binary digits by assigning it with powers of 2, with a coefficient of 0 or 1 for each term:

25 = 1*16 + 1*8 + 0*4 + 0*2 + 1*1

The choice of 0 and 1 is... not very binary. We shall perform the true binary expansion by expanding with powers of 2, but with a coefficient of 1 or -1 instead:

25 = 1*16 + 1*8 + 1*4 - 1*2 - 1*1

Now this looks binary.

Given any positive number, it should be trivial to see that:

• Every odd number has infinitely many true binary expansions
• Every even number has no true binary expansions

Hence, for a true binary expansion to be well-defined, we require the expansion to be the least, i.e with the shortest length.

---

Given any positive, odd integer n, return its true binary expansion, from the most significant digit to the least significant digit (or in reversed order).

Rules:

• As this is code-golf, you should aim to do this in the shortest byte count possible. Builtins are allowed.
• Any output that can represent and list the coefficients is acceptable: an array, a string of coefficients with separators, etc...
• Standard golfing loopholes apply.
• Your program should work for values within your language's standard integer size.

---

Test Cases

25 -> [1,1,1,-1,-1]
47 -> [1,1,-1,1,1,1]
1 -> [1]
3 -> [1,1]
1234567 -> [1,1,-1,-1,1,-1,1,1,-1,1,-1,1,1,-1,1,-1,-1,-1,-1,1,1]

Answer 1

Japt, 6 bytes

¤é r0J

Try it online!

Explanation:

¤é r0J  // Test input:                  25
¤       // Binary the input:            11001
 é      // Rotate 1 chars to the right: 11100
   r0J  // Replace 0s with -1:          111-1-1

Answer 2

Pyth,  12  11 bytes

|R_1.>jQ2 1

Try it here!

---

How?

|R_1.>jQ2 1   Full program.

      jQ2      Convert input to a binary list.
     .>   1    Cyclically rotate the list above by 1 place to the right.
|R_1           Substitute 0 with -1.
               Implicitly output.

First off, we notice that the task is just "substitute the 0s in the binary writing with -1s and shift to the right by 1 place." — That's exactly what we should do! The binary conversion gives us a list of 0s and 1s. All we should do here is to find a golfy way to convert 0 to -1. The bitwise operator | (bitwise OR) is our friend. The map over the binary representation shifted with | and -1. If the current number is 0, it gets converted to -1.

Answer 3

Perl 6

String version, 31 bytes

1~(*+>1).base(2).subst(0,-1,:g)

Try it online!

List version, 36 bytes

{map * *2-1,1,|($_+>1).base(2).comb}

Try it online!

Answer 4

JavaScript (ES6), 35 34 bytes

f=n=>n?[...f(n>>=1),!n|n%2||-1]:[]

Test snippet

let f=n=>n?[...f(n>>=1),!n|n%2||-1]:[];

[25, 47, 1, 3, 1234567].map(x => console.log(x + ":", JSON.stringify(f(x))))

Answer 5

Perl 6, 72 bytes

There is surely a better way, but this is what I have...

->$a {grep {$a==[+] @^a.reverse Z+< ^∞},[X] (1,-1)xx $a.base(2).chars}

Try it online!

Explanation: It's a function that takes one argument (->$a). We first get the number of coefficients needed ($a.base(2).chars = number of characters in base 2 representation), then make a Cartesian product (X) of that many pairs (1,-1). (The [X] means: reduce the following list with X.) So we get a list of all possible combinations of 1s and -1s. Then we filter (grep) only the lists which encode the given number $a. There is only one, so we get a list of one list with the coefficients.

The grep block does this: takes its argument as a list (@^a), reverses it and zips it with an infinite list 0,1,2,... using the "left bit shift" operator +<. Zipping stops as soon as the shorter list is depleted (good for us!) We then sum all the results and compare it with the given number. We had to use .reverse because the OP demands that the coefficients be in the order from most significant to least significant.

Answer 6

Jelly, 5 bytes

Bṙ-o-

Try it online!

Answer 7

05AB1E, 6 5 bytes

bÁ0®:

Try it online!

Answer 8

J, 11 bytes

1-~2*_1|.#:

Try it online!

Thanks to @JosiahWinslow for the algorithm.

Any thoughts on making the conversion shorter? My thoughts are to using !.-fit (nvm, it just changes the tolerance of the conversion).

Using {-take is longer by 1 character.

_1 1{~_1|.#:

Answer 9

Java 8, 101 bytes

n->{String s=n.toString(n,2);return(s.charAt(s.length()-1)+s.replaceAll(".$","")).replace("0","-1");}

Port of @Oliver's Japt answer, with a few more bytes.. ;)

Can definitely be golfed by using an mathematical approach instead of this String approach.

Explanation:

Try it here.

n->{                             // Method with Integer parameter and String return-type
  String s=n.toString(n,2);      //  Convert the Integer to a binary String
  return(s.charAt(s.length()-1)  //  Get the last character of the binary String
    +s.replaceAll(".$","")       //   + everything except the last character
   ).replace("0","-1");          //  Then replace all zeroes with -1, and return the result
}                                // End of method

Answer 10

Ruby, 44 37 33 32 bytes

->n{("1%b"%n).chop.gsub ?0,"-1"}

Try it online!

Answer 11

R, 90 88 46 bytes

function(n)c((n%/%2^(0:log2(n))%%2)[-1],1)*2-1

Try it online!

Implements Oliver's algorithm, but returns the digits in reverse order. Since we are guaranteed that n is never even, the least significant bit (the first) is always 1, so we remove it and append a 1 to the end to simulate rotation in R. Thanks to Shaggy for getting me to fix my math.

Simply putting rev( ) around the function calls in the footer should return the values in the same order.

original answer, 88 bytes:

function(n,b=2^(0:log2(n)))(m=t(t(expand.grid(rep(list(c(-1,1)),sum(b|1))))))[m%*%b==n,]

Anonymous function; returns the values in reverse order with column names attached.

Try it online!

Explanation:

function(n){
 b <- 2^(0:log2(n))         # powers of 2 less than n
 m <- expand.grid(rep(list(c(-1,1)),sum(b|1))) # all combinations of -1,1 at each position in b, as data frame
 m <- t(t(m))               # convert to matrix
 idx <- m%*%b==n            # rows where the matrix product is `n`
 m[idx,]                    # return those rows
}

Answer 12

Perl 5, 30 bytes

29 bytes code, 1 byte for -p switch.

$_=sprintf'1%b',$_/2;s/0/-1/g

Try it online!

Answer 13

CJam, 12 bytes

A port of my Golfscript answer.

qi2b{_+(}%)\

Answer 14

Golfscript, 14 13 14 bytes

-1 byte because I forgot % existed. +1 byte because I also forgot input is a string.

~2base{.+(}%)\