11
\$\begingroup\$

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 , 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]
Improve this question
\$\endgroup\$
11
  • \$\begingroup\$ Related but quite different. \$\endgroup\$ Commented Aug 31, 2017 at 14:57
  • 4
    \$\begingroup\$ Simple algorithm: Convert to base 2, replace 0's with -1's, put the LSD at the front. \$\endgroup\$ Commented Aug 31, 2017 at 15:42
  • \$\begingroup\$ Voile: I wasn't explaining the downvotes, I was just outlining an algorithm for people who have base-conversion commands in their language. \$\endgroup\$ Commented Aug 31, 2017 at 16:15
  • \$\begingroup\$ 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.) \$\endgroup\$ Commented Aug 31, 2017 at 19:48
  • \$\begingroup\$ Does the output need to include separators? Is 111-1-1 a valid output for 25? \$\endgroup\$ Commented Aug 31, 2017 at 22:50

14 Answers 14

Reset to default
7
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Ah, the rotation; that's why it wasn't working for me. \$\endgroup\$ Commented Aug 31, 2017 at 15:26
  • 2
    \$\begingroup\$ Rotate??? dagnabbit. \$\endgroup\$ Commented Aug 31, 2017 at 15:30
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ I don't think there's a better way. ;) \$\endgroup\$ Commented Aug 31, 2017 at 16:18
  • \$\begingroup\$ @JosiahWinslow I do... Trying to find it \$\endgroup\$ Commented Aug 31, 2017 at 16:19
  • \$\begingroup\$ Hm? The algorithm seems optimal, maybe that's because I don't know Pyth. \$\endgroup\$ Commented Aug 31, 2017 at 16:20
  • \$\begingroup\$ @JosiahWinslow Found the better way. Syntactical better way, not algorithmic better way. \$\endgroup\$ Commented Aug 31, 2017 at 16:29
  • \$\begingroup\$ @Mr.Xcoder And now there really isn't any at least to me. \$\endgroup\$ Commented Aug 31, 2017 at 16:49
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes

Bṙ-o-

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 5 bytes

bÁ0®:

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ D< can be ® (® is default -1). \$\endgroup\$ Commented Aug 31, 2017 at 16:41
  • \$\begingroup\$ @EriktheOutgolfer Thanks! Didn't realize that. \$\endgroup\$ Commented Aug 31, 2017 at 16:50
1
\$\begingroup\$

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|.#:
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby, 44 37 33 32 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
}
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ I wouldn't consider that output to be valid; suggest asking the challenge author for confirmation. \$\endgroup\$ Commented Aug 31, 2017 at 22:45
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Aug 31, 2017 at 23:01
  • 1
    \$\begingroup\$ 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]. \$\endgroup\$ Commented Sep 1, 2017 at 7:33
  • 1
    \$\begingroup\$ @Shaggy ah, you're right, I just did the math wrong! should be 2*bits - 1 instead of 1-2*bits. Thank you. \$\endgroup\$ Commented Sep 1, 2017 at 12:59
1
\$\begingroup\$

Perl 5, 30 bytes

29 bytes code, 1 byte for -p switch.

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

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

CJam, 12 bytes

A port of my Golfscript answer.

qi2b{_+(}%)\
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Golfscript, 14 13 14 bytes

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

~2base{.+(}%)\
Improve this answer
\$\endgroup\$
6
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 31, 2017 at 18:18
  • \$\begingroup\$ Um...what? I meant, the number is being pushed as an integer, instead of a string containing a number. \$\endgroup\$ Commented Sep 1, 2017 at 16:19
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 1, 2017 at 18:06
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Sep 1, 2017 at 20:53
  • \$\begingroup\$ 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 ~. \$\endgroup\$ Commented Sep 1, 2017 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.