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]

• Giuseppe: Related but quite different.
• Josiah Winslow: Simple algorithm: Convert to base 2, replace 0's with -1's, put the LSD at the front.
• Josiah Winslow: Voile: I wasn't explaining the downvotes, I was just outlining an algorithm for people who have base-conversion commands in their language.
• Peter Cordes: Since you're so keen on being truly binary, can we return the value as packed bits with the usual place-value but the new interpretation of the two states? i.e. electrically it's just high or low voltage (or whatever), and it's not my fault if standard debuggers print 0 instead of -1 for the low-voltage state. The caller receiving the bits knows what they mean. (It's still a non-trivial bit-manipulation exercise, since a rotate right only works if it has 32 significant bits. e.g. a 5-bit number needs a rotate width of 5.)
• Oliver: Does the output need to include separators? Is 111-1-1 a valid output for 25?

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

• Shaggy: Ah, the rotation; that's why it wasn't working for me.
• Giuseppe: Rotate??? dagnabbit.

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.

• Josiah Winslow: I don't think there's a better way. ;)
• Mr. Xcoder: @JosiahWinslow I do... Trying to find it
• Josiah Winslow: Hm? The algorithm seems optimal, maybe that's because I don't know Pyth.
• Mr. Xcoder: @JosiahWinslow Found the better way. Syntactical better way, not algorithmic better way.
• Erik the Outgolfer: @Mr.Xcoder And now there really isn't any at least to me.

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!

• Erik the Outgolfer: D< can be ® (® is default -1).
• Okx: @EriktheOutgolfer Thanks! Didn't realize that.

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
}

• Shaggy: I wouldn't consider that output to be valid; suggest asking the challenge author for confirmation.
• Giuseppe: @Shaggy reversed order is explicitly allowed: from the most significant digit to the least significant digit (or in reversed order). hence this should be perfectly acceptable.
• Shaggy: Reversed order, not reversed signs. Meaning valid output for 25, for example, would be [1,1,1,-1,-1] or [-1,-1,1,1,1].
• Giuseppe: @Shaggy ah, you're right, I just did the math wrong! should be 2*bits - 1 instead of 1-2*bits. Thank you.

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{.+(}%)\

• Peter Taylor: If you're going to assume that the input comes as an integer, you should wrap the code in {} to make it a block. Full programs can only get input as strings.
• Josiah Winslow: Um...what? I meant, the number is being pushed as an integer, instead of a string containing a number.
• Peter Taylor: In that case your answer is not a full program, and so must be a "function", or in the case of GolfScript a block. Therefore it's {2base{.+(}%\} for 15 bytes. Similarly your CJam answer.
• Josiah Winslow: This is a full program. Input in Golfscript are implicitly pushed onto the stack at the beginning of the program, and input in CJam is specified before execution and accessed with the q command.
• Peter Taylor: I do have some familiarity with GolfScript. (And CJam). If you want to claim that it's a full program you need to prefix it with ~.