Normalmente, decompomos um número em dígitos binários atribuindo-o com potências de 2, com um coeficiente de 0ou 1para cada termo:

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

A escolha de 0e 1é ... não muito binária. Realizaremos a verdadeira expansão binária expandindo com potências de 2, mas com um coeficiente de 1ou -1:

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

Agora isso parece binário.

Dado qualquer número positivo, deve ser trivial ver que:

• Todo número ímpar tem infinitas expansões binárias verdadeiras
• Todo número par não possui expansões binárias verdadeiras

Portanto, para que uma verdadeira expansão binária seja bem definida, exigimos que a expansão seja mínima , ou seja, com o menor comprimento.

Dado qualquer número inteiro positivo e ímpar n, retorne sua verdadeira expansão binária, do dígito mais significativo para o dígito menos significativo (ou em ordem inversa).

Regras:

• Como esse é o código-golfe , você deve fazer isso na menor contagem de bytes possível. Builtins são permitidos.
• Qualquer saída que possa representar e listar os coeficientes é aceitável: uma matriz, uma sequência de coeficientes com separadores, etc ...
• Aplicam-se lacunas de golfe padrão.
• Seu programa deve funcionar para valores dentro do tamanho inteiro padrão do seu idioma.

Casos de teste

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]

Japonês , 6 bytes

¤é r0J

Experimente online!

Explicação:

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

Pitão ,  12  11 bytes

|R_1.>jQ2 1

Experimente aqui!

Como?

| R_1.> JQ2 1 Programa completo.

      jQ2 Converte a entrada em uma lista binária.
     .> 1 Gire ciclicamente a lista acima em 1 lugar à direita.
| R_1 Substitua 0 por -1.
               Saída implícita.

Primeiro, notamos que a tarefa é apenas "substituir os 0s na escrita binária por -1s e deslocar para a direita por 1 lugar". - É exatamente o que devemos fazer! A conversão binária dá-nos uma lista de 0s e 1s. Tudo o que deve fazer aqui é encontrar uma maneira golfy para converter 0para -1. O operador bit a bit |(OR bit a bit) é nosso amigo. O mapa sobre a representação binária mudou com |e -1. Se o número atual for 0, ele será convertido em -1.

Perl 6

Versão em cadeia, 31 bytes

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

Experimente online!

Versão da lista, 36 bytes

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

Experimente online!

JavaScript (ES6), 35 34 bytes

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

Snippet de teste

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

Perl 6 , 72 bytes

Certamente há uma maneira melhor, mas é isso que eu tenho ...

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

Experimente online!

Explicação : É uma função que recebe um argumento ( ->$a). Primeiro obtemos o número de coeficientes necessários ( $a.base(2).chars= número de caracteres na representação da base 2) e, em seguida, fazemos um produto cartesiano ( X) com muitos pares (1,-1). (O [X]meio: reduza a lista a seguir com X.) Portanto, obtemos uma lista de todas as combinações possíveis de 1s e -1s. Em seguida, filtramos ( grep) apenas as listas que codificam o número fornecido $a. Existe apenas um, então obtemos uma lista de uma lista com os coeficientes.

O bloco grep faz isso: pega seu argumento como uma lista ( @^a), o reverte e o fecha com uma lista infinita 0,1,2,...usando o operador "left bit shift" +<. O zíper pára assim que a lista mais curta se esgota (bom para nós!) Em seguida, somamos todos os resultados e comparamos com o número fornecido. Tivemos que usar .reverseporque o OP exige que os coeficientes estejam na ordem do mais significativo para o menos significativo.

Gelatina , 5 bytes

Bṙ-o-

Experimente online!

05AB1E , 6 5 bytes

bÁ0®:

Experimente online!

J, 11 bytes

1-~2*_1|.#:

Experimente online!

Obrigado a @JosiahWinslow pelo algoritmo.

Alguma idéia de como reduzir a conversão? Meu pensamento é usar !.-fit (nvm, isso apenas altera a tolerância da conversão).

O uso de {-take é maior em 1 caractere.

_1 1{~_1|.#:

Java 8, 101 bytes

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

Porto de @Oliver resposta Japt 's , com um pouco mais bytes ..;)

Definitivamente, você pode jogar golfe usando uma abordagem matemática em vez dessa abordagem de String.

Explicação:

Experimente aqui.

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

R , 90 88 46 bytes

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

Experimente online!

Implementa o algoritmo de Oliver , mas retorna os dígitos na ordem inversa. Como garantimos que isso nnunca é uniforme, o bit menos significativo (o primeiro) é sempre 1, por isso o removemos e anexamos um 1ao final para simular a rotação em R. Agradecemos a Shaggy por me ajudar a corrigir minha matemática .

Simplesmente colocar rev( )as chamadas de função no rodapé deve retornar os valores na mesma ordem.

resposta original, 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,]

Função anônima; retorna os valores na ordem inversa com os nomes das colunas anexados.

Experimente online!

Explicação:

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
}

Perl 5 , 30 bytes

Código de 29 bytes, 1 byte para o -pswitch.

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

Experimente online!

CJam, 12 bytes

Um porto da minha resposta Golfscript.

qi2b{_+(}%)\

Ruby , 44 37 33 32 bytes

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

Experimente online!

Golfscript, 14 13 14 bytes

-1 byte porque esqueci que %existia. 1 byte porque também esqueci que a entrada é uma string.

~2base{.+(}%)\