Положительное целое число можно разбавить , вставив 0между двумя битами в его двоичное расширение. Это означает, что nчисло -бит имеет n-1разведения, которые не обязательно все различны.

Например, для 12(или 1100в двоичном виде) разведения

11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

В этом испытании мы собираемся взять сумму всех разведений, исключая исходное число. Ибо 12, принимая сумму 24, 24, 20результатов в 68, так 68должен быть вывод для 12.

Вызов

Учитывая положительное целое число в n > 1качестве входных данных, выведите / верните разводненную сумму, как описано выше.

Примеры

in    out
---   ---
2       4
3       5
7      24
12     68
333  5128
512  9216

правила

• Можно предположить, что ввод и вывод соответствуют целочисленному типу вашего языка.
• Ввод и вывод может быть дан в любом удобном формате .
• Допустимы либо полная программа, либо функция. Если функция, вы можете вернуть вывод, а не распечатать его.
• Стандартные лазейки запрещены.
• Это код-гольф, поэтому применяются все обычные правила игры в гольф, и выигрывает самый короткий код (в байтах).

Python 2 , 43 39 байт

f=lambda n,i=2:n/i and n*2-n%i+f(n,i*2)

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

Как?

Каждый вызов рекурсивной функции вычисляет одно разведение. Положение вставленного 0это log2(i). Функция повторяется до тех пор, пока не iстанет больше, чем nи вставка будет слева от числа. Если i>n, n/iоценивает 0, что является ложным значением в Python.

n*2сдвигает все двоичные числа на одну цифру влево n%iили n % 2**(position of insertion)вычисляет значение части, которую не следует сдвигать влево. Это значение вычитается из смещенного числа.

Пример (n = 7)

call       n/i          bin(n)  n*2     n%i   dilution       return value

f(7, i=2)  3 => truthy  0b111   0b1110  0b1   0b1101 = 13    13 + f(7, 2*2) = 13 + 11 = 24
f(7, i=4)  1 => truthy  0b111   0b1110  0b11  0b1011 = 11    11 + f(7, 4*2) = 11 + 0 = 11
f(7, i=8)  0 => falsy                                        0

Желе , 11 байт

BJṖ2*ɓdḅḤ}S

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

Как это работает

BJṖ2*ɓdḅḤ}S  Main link. Argument: n (integer)

B            Binary; convert n to base 2. This yields a digit array A.
 J           Indices; yield [1, ..., len(A)].
  Ṗ          Pop; remove the last element, yielding [1, 2, ..., len(A)-1].
   2*        Elevate 2 to these powers, yielding [2, 4, ..., 2**(len(A)-1)].
             Let's call the result B.
     ɓ       Begin a new, dyadic chain, with left argument n and right argument B.
      d      Divmod; yield [n/b, n%b], for each b in B.
        Ḥ}   Unhalve right; yield 2b for each b in B, i.e., [4, 8, ..., 2**len(A)].
       ḅ     Unbase; convert each [n/b, n%b] from base 2b to integer, yielding
             (2b)(n/b) + (n%b).
          S  Take the sum.

MATL , 13 байт

tZl:W&\5ME*+s

Попробуйте это в MATL Online! Или проверьте все тестовые случаи .

объяснение

Рассмотрим ввод 12в качестве примера.

t     % Implicit input. Duplicate
      % STACK: 12, 12
Zl    % Binary logarithm
      % STACK: 12, 3.584962500721156
:     % Range (rounds down)
      % STACK: 12, [1 2 3]
W     % Power with base 2, element-wise
      % STACK: 12, [2 4 8]
&\    % 2-output modulus, element-wise: pushes remainders and quotients
      % STACK: [0 0 4], [6 3 1]
5M    % Push array of powers of 2, again
      % STACK: [0 0 4], [6 3 1], [2 4 8]
E     % Multiply by 2
      % STACK: [0 0 4], [6 3 1], [4 8 16]
*     % Multiply, element-wise
      % STACK: [0 0 4], [24 24 16]
+     % Add, element-wise
      % STACK: [24 24 20]
s     % Sum of array. Implicit display
      % STACK: 68

C,  58  56 байт

Спасибо @Dennis за сохранение двух байтов!

s,k;f(n){for(s=0,k=2;k<=n;k*=2)s+=n/k*k*2+n%k;return s;}

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

C (gcc) , 50 байтов

s,k;f(n){for(s=0,k=2;k<=n;)s+=n%k+n/k*(k+=k);k=s;}

Возврат по k=s;неопределенному поведению, но работает с gcc, когда оптимизации отключены. Кроме того, n%k+n/k*(k+=k)имеет неопределенное поведение , но, похоже, хорошо работает с gcc.

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

Желе , 9 8 байт

BḊḄÐƤạḤS

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

B                        to binary          42 -> 1 0 1 0 1 0
 Ḋ                       drop first                 0 1 0 1 0
  ḄÐƤ                    each suffix to decimal   10 10 2 2 0
      Ḥ                  double the input                  84
     ạ                   absolute difference   74 74 82 82 84
       S                 add them up                      396

И наоборот B¹ƤṖ+BḄS: получить префиксы, отбросить последний, добавить их к вводу и суммировать.

J , 20 15 14 байтов

+/@}:@:+[\&.#:

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

15 байт

1#.-,+:-#.\.@#:

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

     +:             Input×2
       -            Subtract
        #.\.@#:     The list of binary suffixes of input (in decimal)
   -,               Append negative input
1#.                 Add them up

Japt , 12 11 байт

¢¬£¢iYTÃÅxÍ

Попытайся

объяснение

                 :Implicit input of integer U
¢                :Convert to base-2 string
 ¬               :Split to an array of individual characters/digits
  £    Ã         :Map over the elements, with Y being the current 0-based index
   ¢             :  Convert U to a base-2 string
    iYT          :  Insert a 0 in that string at index Y
        Å        :Slice off the first element of the array
          Í      :Convert each element to a base-10 integer
         x       :Reduce by addition

JavaScript (ES6), 41 40 байт

Сохранено 1 байт благодаря Mr.Xcoder

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

Контрольные примеры

f=(n,k=1)=>k<n&&(n&k)+2*(n&~k)+f(n,k-~k)

console.log(f(2  )) //    4
console.log(f(3  )) //    5
console.log(f(7  )) //   24
console.log(f(12 )) //   68
console.log(f(333)) // 5128
console.log(f(512)) // 9216

Сетчатка , 53 50 47 байт

.+
*
+`(_+)\1
$1O
O_
_
L$`\B
$`O$'
+%`\B
¶$`¶
_

Попробуйте онлайн! Ссылка включает в себя тестовые случаи. Редактировать: 3 байта сохранены благодаря @MartinEnder. Объяснение:

.+
*
+`(_+)\1
$1O
O_
_

Преобразуйте из десятичного в двоичное, но используйте O, чтобы представить 0, поскольку это не цифра, и _, чтобы представить 1, поскольку это символ повторения по умолчанию в Retina 1.

L$`\B
$`O$'

Вставьте O между каждой парой цифр и соберите результаты в виде списка.

+%`\B
¶$`¶

Преобразовать из двоичного в унарный. (Это преобразование дает дополнительные Os, но нам все равно.)

_

Суммируйте и преобразуйте в десятичную.

Pyth , 13 байт

smiXd.BQZ2Ssl

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

объяснение

smiXd.BQZ2Ssl | Полная программа.

           sl | Основание-2 логарифм ввода, с точностью до целого числа.
          S | Создайте целочисленный диапазон [1 ... логарифм по этажам].
 м | И отобразить функцию над ним.
------------ + - + ----------------------------------- ------------------
  iXd.BQZ2 | Функция для отображения (использует переменную d).
     .BQ | В двоичном представлении ввода ...
   XZ | ... вставить ноль ...
    д | ... по индексу d.
  я 2 | И преобразовать результат из базы 2 в целое число.
------------ + - + ----------------------------------- ------------------
с | Подведите итоговый список.

Желе , 10 байт

BµLḤ_J’×µḄ

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

Не самый короткий в настоящее время, но это может быть, если есть способ обойти Bµ µḄ...

объяснение

BµLḤ_J’×µḄ    Main link. Argument: n (integer)
B             Binary; convert n to an binary of binary digits. Call this A.
 µ            Start a new monadic link with argument A.
  L           Length; yield len(A). We'll call this l.
   Ḥ          Unhalve; yield l * 2.
     J        Length range; yield [1, 2, ..., l].
    _         Subtract; yield [l*2 - 1, l*2 - 2, ..., l].
      ’       Decrement; subtract one from each item.
       ×      Multiply each item by the corresponding item in A. Call this B.
        µ     Start a new monadic link with argument B.
         Ḅ    Unbinary; convert from a binary array to a decimal.

По сути, это работает путем умножения каждой двоичной цифры на магическое число. Я не могу объяснить это без визуализации, поэтому вот двоичное число, с которым мы будем работать:

1111

Как объясняет задача, он выводит нам сумму этих двоичных чисел:

10111  = 2^4 + 2^2 + 2^1 + 2^0
11011  = 2^4 + 2^3 + 2^1 + 2^0
11101  = 2^4 + 2^3 + 2^2 + 2^0

Однако на самом деле нам не нужно вставлять нули: «небинарный» атом Jelly будет принимать числа, отличные от just 0и 1. Когда мы позволяем себе использовать 2, этот шаблон становится проще:

2111   = 2*2^3 + 1*2^2 + 1*2^1 + 1*2^0
2211   = 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0
2221   = 2*2^3 + 2*2^2 + 2*2^1 + 1*2^0

Когда мы суммируем цифры в каждом столбце, мы получаем

6543   = 6*2^3 + 5*2^2 + 4*2^1 + 3*2^0 = 48 + 20 + 8 + 3 = 79.

Уловка, которую использует этот ответ, состоит в том, чтобы сгенерировать этот образец и умножить каждую цифру на соответствующую цифру в оригинале, чтобы отменить необходимые столбцы. 12, например, будет представлен как

 1100
×6543
=6500  = 6*2^3 + 5*2^2 + 0*2^1 + 0*2^0 = 48 + 20 + 0 + 0 = 68.

Java 8, 55 байт

n->{int r=0,i=2;for(;i<=n;r+=n%i+n/i*(i*=2));return r;}

Порт Steadybox 'C ответ , и гольф 3 байта в процессе.

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

Шелуха , 13 12 байт

-1 байт благодаря @Mr. Xcoder!

ṁḋ§z·+Θḣotṫḋ

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

объяснение

ṁḋ§z·+Θḣ(tṫ)ḋ  -- example input: 6
            ḋ  -- convert to binary: [1,1,0]
  §            -- fork argument
        (tṫ)   -- | tail of tails: [[1,0],[0]]
       ḣ       -- | heads: [[1],[1,1],[1,1,0]]
   z           -- and zipWith the following (example with [1,0] [1])
    · Θ        -- | prepend 0 to second argument: [0,1]
     +         -- | concatenate: [1,0,0,1]
               -- : [[1,0,1,0],[1,1,0,0]]
ṁ              -- map the following (example with [1,0,1,0]) and sum
 ḋ             -- | convert from binary: 10
               -- : 22

05AB1E , 14 байтов

.²LoDŠ‰ø`r·*+O

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

Пип , 21 18 байт

2*a-a%2**_MS1,#TBa

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

объяснение

Позвоните по нашему номеру a. Для каждого двоичного индекса, iв который мы хотим вставить ноль, мы можем вычислить биты слева от точки вставки как a // 2**i(где //целочисленное деление и **возведение в степень), биты справа от точки вставки как a % 2**iи, следовательно, разбавленное целое число как 2 * (a // 2**i) * 2**i + (a % 2**i). Но (a // 2**i) * 2**iравно a - (a % 2**i), и поэтому мы можем перестроиться на более короткую формулу: 2 * (a - a % 2**i) + a % 2**i= 2 * a - a % 2**i.

2*a-a%2**_MS1,#TBa
                       a is 1st command-line argument (implicit)
               TBa     Convert a to binary
              #        Length of the binary expansion
            1,         Range from 1 up to (but not including) that number
          MS           Map this function to the range and sum the results:
2*a-a%2**_              The above formula, where _ is the argument of the function
                       The final result is autoprinted

R , 141 48 байт

function(n,l=2^(1:log2(n)))sum(n%%l+(n%/%l*2*l))

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

Либо я делаю что-то действительно неправильное, либо R просто ужасен в битовых манипуляциях. Портировать подход Луиса Мендо легко, правильно и гольф.

Но если вы действительно хотите обойтись с битовыми операциями, MickyT предлагает следующий 105 байт:

function(i)sum(sapply(1:max(which(b<-intToBits(i)>0)),function(x)packBits(head(append(b,F,x),-1),"i")))-i

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

Python 3, 92 80 78 байт

def b(x):x=f'{x:b}';return sum(int(x[:i]+'0'+x[i:],2)for i in range(1,len(x)))

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

Благодаря Mr.XCoder и овс для -12 байт и -2 байт соответственно.

Пакет, 92 77 байтов

@set/an=2,t=0
:l
@if %1 geq %n% set/at+=%1*2-(%1%%n),n*=2&goto l
@echo %t%

Изменить: переключился на ту же формулу, что и все остальные.

Желе , 14 байт

BLḊṬœṗ¥€Bj€0ḄS

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

Perl 5 , 36 + 1 ( -p) = 37 байт

$\+=$_*2-($_&$.-1)while($.*=2)<=$_}{

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

Атташе , 57 байт

Sum##UnBin=>{Join[Join=>_,"0"]}=>SplitAt#1&`:@{#_-1}##Bin

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

Я думал, что подойду к проблеме с помощью подхода не-битной манипуляции, так как такой подход непрактичен в Attache. Я должен исследовать некоторые части этого подхода для альтернатив.

объяснение

Вот расширенная версия:

Define[$joinByZero, {Join[Join=>_,"0"]}]

Define[$insertionPoints,
    SplitAt#1&`:@{#_-1}
]

Define[$f,
Sum##UnBin=>joinByZero=>insertionPoints##Bin
]

Это просто берет двоичное представление числа, разбивает его в определенных точках, вставляет туда нули, преобразует обратно в десятичную и суммирует их вместе.

J , 33 байта

1#.[:}:#.@(<\;@(,0;])"0<@}.\.)@#:

Скорее всего, есть много места для дальнейшего игры в гольф.

Как?

@#: преобразовать в двоичный файл и

<@}.\. - найти все, что нужно, сбросить первую цифру от каждого и поле

<\ - найти все префиксы и указать их

(,0;])"0 - к каждому префиксу добавьте 0, затем добавьте соответствующий обезглавленный суффикс

;@ никак (распаковывать)

1#.[:}:#.@ - преобразовать в десятичную, сокращенную и сумму

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