9
\$\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]
\$\endgroup\$
  • 1
    \$\begingroup\$ Apparently not 1, but 2 people have downvoted this question in just 10 minutes. Care to explain what to improve? :) \$\endgroup\$ – Voile Aug 31 '17 at 15:26
  • 4
    \$\begingroup\$ Simple algorithm: Convert to base 2, replace 0's with -1's, put the LSD at the front. \$\endgroup\$ – Josiah Winslow Aug 31 '17 at 15:42
  • 2
    \$\begingroup\$ Is "simple" a criteria for giving downvotes? Then lots of questions would already have minus votes. I don't think this question is that simple. Also, there are different ways to do it in different languages, so it's not one same thing that can be blindly applied to any language. \$\endgroup\$ – Voile Aug 31 '17 at 15:46
  • 13
    \$\begingroup\$ If you looked carefully, the original author of that is also me :) \$\endgroup\$ – Voile Aug 31 '17 at 16:11
  • 1
    \$\begingroup\$ @Mego There is no root of things to reference from. I came up with the question and cross-post it to two places at the same time. How'd you expect one to "reference" something in this case? It is not well-defined. Not everything is sequential like a tree as you might think. \$\endgroup\$ – Voile Sep 1 '17 at 6:35

14 Answers 14

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Ah, the rotation; that's why it wasn't working for me. \$\endgroup\$ – Shaggy Aug 31 '17 at 15:26
  • 2
    \$\begingroup\$ Rotate??? dagnabbit. \$\endgroup\$ – Giuseppe Aug 31 '17 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.

\$\endgroup\$
  • \$\begingroup\$ I don't think there's a better way. ;) \$\endgroup\$ – Josiah Winslow Aug 31 '17 at 16:18
  • \$\begingroup\$ @JosiahWinslow I do... Trying to find it \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 16:19
  • \$\begingroup\$ Hm? The algorithm seems optimal, maybe that's because I don't know Pyth. \$\endgroup\$ – Josiah Winslow Aug 31 '17 at 16:20
  • \$\begingroup\$ @JosiahWinslow Found the better way. Syntactical better way, not algorithmic better way. \$\endgroup\$ – Mr. Xcoder Aug 31 '17 at 16:29
  • \$\begingroup\$ @Mr.Xcoder And now there really isn't any at least to me. \$\endgroup\$ – Erik the Outgolfer Aug 31 '17 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!

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

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

\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes

Bṙ-o-

Try it online!

\$\endgroup\$
1
\$\begingroup\$

05AB1E, 6 5 bytes

bÁ0®:

Try it online!

\$\endgroup\$
  • \$\begingroup\$ D< can be ® (® is default -1). \$\endgroup\$ – Erik the Outgolfer Aug 31 '17 at 16:41
  • \$\begingroup\$ @EriktheOutgolfer Thanks! Didn't realize that. \$\endgroup\$ – Okx Aug 31 '17 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|.#:
\$\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
\$\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
}
\$\endgroup\$
  • \$\begingroup\$ I wouldn't consider that output to be valid; suggest asking the challenge author for confirmation. \$\endgroup\$ – Shaggy Aug 31 '17 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\$ – Giuseppe Aug 31 '17 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\$ – Shaggy Sep 1 '17 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\$ – Giuseppe Sep 1 '17 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!

\$\endgroup\$
0
\$\begingroup\$

CJam, 12 bytes

A port of my Golfscript answer.

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

Ruby, 44 37 33 32 bytes

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

Try it online!

\$\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{.+(}%)\
\$\endgroup\$
  • 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\$ – Peter Taylor Aug 31 '17 at 18:18
  • \$\begingroup\$ Um...what? I meant, the number is being pushed as an integer, instead of a string containing a number. \$\endgroup\$ – Josiah Winslow Sep 1 '17 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\$ – Peter Taylor Sep 1 '17 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\$ – Josiah Winslow Sep 1 '17 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\$ – Peter Taylor Sep 1 '17 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.