Обычно мы разбиваем число на двоичные числа, присваивая ему степени 2 с коэффициентом 0или 1для каждого члена:

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

Выбор 0и 1есть ... не очень бинарный. Мы выполним истинное двоичное расширение, расширяясь степенями 2, но с коэффициентом 1или -1вместо:

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

Теперь это выглядит бинарным.

Учитывая любое положительное число, должно быть тривиально видеть, что:

• Каждое нечетное число имеет бесконечно много истинных двоичных разложений
• Каждое четное число не имеет истинных двоичных разложений

Следовательно, для того, чтобы истинное двоичное разложение было правильно определено, мы требуем, чтобы разложение было наименьшим , то есть с самой короткой длиной.

При наличии любого положительного, нечетного целого числа nверните его истинное двоичное расширение от старшей к младшей (или в обратном порядке).

Правила:

• Как это Код-гольф, вы должны стремиться сделать это как можно быстрее. Встроенные разрешены.
• Любые выходные данные, которые могут представлять и перечислять коэффициенты, являются приемлемыми: массив, строка коэффициентов с разделителями и т.д ...
• Применяются стандартные лазейки для игры в гольф.
• Ваша программа должна работать для значений в пределах стандартного целочисленного размера вашего языка.

Тестовые случаи

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]

Japt , 6 байт

¤é r0J

Попробуйте онлайн!

Объяснение:

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

Pyth ,  12  11 байтов

|R_1.>jQ2 1

Попробуй это здесь!

Как?

| R_1.> JQ2 1 Полная программа.

      jQ2 Преобразование ввода в двоичный список.
     .> 1 Циклически поворачивайте список выше на 1 место справа.
| R_1 Заменить 0 на -1.
               Неявный вывод.

Прежде всего, мы замечаем, что задача состоит в том, чтобы просто «заменить 0s в двоичной записи на -1s и сдвинуть вправо на 1 место». - Это именно то, что мы должны сделать! Двоичное преобразование дает нам список 0s и 1s. Все , что мы должны сделать здесь , чтобы найти golfy способ преобразовать 0в -1. Побитовый оператор |(побитовое ИЛИ) - наш друг. Карта над двоичным представлением сдвинута на |и -1. Если текущее число есть 0, оно конвертируется в -1.

Perl 6

Строковая версия, 31 байт

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

Попробуйте онлайн!

Версия списка, 36 байт

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

Попробуйте онлайн!

JavaScript (ES6), 35 34 байта

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

Тестовый фрагмент

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 байта

Есть, конечно, лучший способ, но это то, что у меня есть ...

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

Попробуйте онлайн!

Объяснение : Это функция, которая принимает один аргумент ( ->$a). Сначала мы получаем необходимое количество коэффициентов ( $a.base(2).chars= количество символов в представлении базы 2), а затем делаем декартово произведение ( X) из этого числа пар (1,-1). ( [X]Значит: уменьшите следующий список с помощью X.) Таким образом, мы получаем список всех возможных комбинаций 1 и -1. Затем мы фильтруем ( grep) только те списки, которые кодируют данное число $a. Существует только один, поэтому мы получаем список из одного списка с коэффициентами.

Блок grep делает это: принимает свой аргумент как list ( @^a), переворачивает его и упаковывает в бесконечный список, 0,1,2,...используя оператор «сдвиг влево» +<. Застежка-молния прекращается, как только сокращается короткий список (это хорошо для нас!). Затем мы суммируем все результаты и сравниваем его с заданным числом. Нам пришлось использовать, .reverseпотому что ОП требует, чтобы коэффициенты были в порядке от наиболее значимого до наименее значимого.

Желе , 5 байт

Bṙ-o-

Попробуйте онлайн!

05AB1E , 6 5 байт

bÁ0®:

Попробуйте онлайн!

J 11 байт

1-~2*_1|.#:

Попробуйте онлайн!

Спасибо @JosiahWinslow за алгоритм.

Есть мысли о том, чтобы сделать конверсию короче? Мои мысли об использовании !.-fit (nvm, это просто меняет допуск конверсии).

Использование {-take длиннее на 1 символ.

_1 1{~_1|.#:

Java 8, 101 байт

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

Порт ответа @Oliver на Japt , с еще несколькими байтами ..;)

Определенно можно играть в гольф, используя математический подход вместо этого подхода String.

Объяснение:

Попробуй это здесь.

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 байт

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

Попробуйте онлайн!

Реализует алгоритм Оливера , но возвращает цифры в обратном порядке. Поскольку нам гарантировано, что nэто никогда не является четным, младший значащий бит (первый) всегда 1, поэтому мы удаляем его и добавляем 1конец до конца, чтобы имитировать вращение в R. Спасибо Шегги, за то, что он помог мне исправить математику .

Простое размещение rev( )вызовов функций в нижнем колонтитуле должно возвращать значения в том же порядке.

оригинальный ответ, 88 байт:

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

Анонимная функция; возвращает значения в обратном порядке с прикрепленными именами столбцов.

Попробуйте онлайн!

Объяснение:

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 байт

29-байтовый код, 1 байт для -pпереключения.

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

Попробуйте онлайн!

CJam, 12 байт

Порт моего ответа на Golfscript.

qi2b{_+(}%)\

Рубин , 44 37 33 32 байта

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

Попробуйте онлайн!

Golfscript, 14 13 14 байтов

-1 байт, потому что я забыл %существовать. +1 байт, потому что я также забыл, что ввод - это строка.

~2base{.+(}%)\