Um número inteiro positivo pode ser diluído inserindo um 0entre dois bits em sua expansão binária. Isso significa que um nnúmero de bits possui n-1diluições, que não são necessariamente todas distintas.

Por exemplo, para 12(ou 1100em binário), as diluições são

11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

Neste desafio, tomaremos a soma de todas as diluições, excluindo o número original. Pois 12, considerando a soma dos 24, 24, 20resultados 68, 68deve ser a saída para 12.

Desafio

Dado um número inteiro positivo n > 1como entrada, produza / retorna a soma diluída conforme explicado acima.

Exemplos

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

Regras

• Pode-se presumir que a entrada e a saída se encaixam no tipo inteiro nativo do seu idioma.
• A entrada e saída podem ser fornecidas em qualquer formato conveniente .
• Um programa completo ou uma função são aceitáveis. Se uma função, você pode retornar a saída em vez de imprimi-la.
• As brechas padrão são proibidas.
• Isso é código-golfe, portanto todas as regras usuais de golfe se aplicam e o código mais curto (em bytes) vence.

Python 2 , 43 39 bytes

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

Experimente online!

Quão?

Cada chamada da função recursiva calcula uma única diluição. A posição do inserido 0é log2(i). A função se repete até ificar maior que ne a inserção estaria à esquerda do número. If i>n, n/iavalia to 0, que é um valor falso no Python.

n*2desloca o número inteiro um dígito binário para a esquerda n%iou n % 2**(position of insertion)calcula o valor da parte que não deve ser deslocada para a esquerda. Este valor é subtraído do número deslocado.

Exemplo (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

Gelatina , 11 bytes

BJṖ2*ɓdḅḤ}S

Experimente online!

Como funciona

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 bytes

tZl:W&\5ME*+s

Experimente no MATL Online! Ou verifique todos os casos de teste .

Explicação

Considere a entrada 12como um exemplo.

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 bytes

Obrigado a @Dennis por salvar dois bytes!

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

Experimente online!

C (gcc) , 50 bytes

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

Retornar por k=s;é um comportamento indefinido, mas funciona com o gcc quando as otimizações estão desabilitadas. Além disso, n%k+n/k*(k+=k)possui um comportamento não especificado , mas parece funcionar bem com o gcc.

Experimente online!

Geléia , 9 8 bytes

BḊḄÐƤạḤS

Experimente online!

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

Vice-versa B¹ƤṖ+BḄS,: obtenha prefixos, solte por último, adicione-os à entrada e soma.

J , 20 15 14 bytes

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

Experimente online.

15 bytes

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

Experimente online!

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

Japonês , 12 11 bytes

¢¬£¢iYTÃÅxÍ

Tente

Explicação

                 :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 bytes

Economizou 1 byte graças ao Mr.Xcoder

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

Casos de teste

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

Retina , 53 50 47 bytes

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

Experimente online! O link inclui casos de teste. Editar: salvou 3 bytes graças a @MartinEnder. Explicação:

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

Converta de decimal para binário, mas use O para representar 0, pois não é um dígito, e _ para representar 1, pois é o caractere de repetição padrão na Retina 1.

L$`\B
$`O$'

Insira um O entre cada par de dígitos e colete os resultados como uma lista.

+%`\B
¶$`¶

Converter de binário em unário. (Essa conversão produz Os extras , mas não nos importamos.)

_

Soma e converta para decimal.

Pitão , 13 bytes

smiXd.BQZ2Ssl

Experimente aqui!

Explicação

smiXd.BQZ2Ssl | Programa completo.

           sl O logaritmo de base 2 da entrada, com piso para um número inteiro.
          S Crie o intervalo inteiro [1 ... o logaritmo com piso].
 m E mapeie uma função sobre ela.
------------ + - + ----------------------------------- ------------------
  iXd.BQZ2 A função a ser mapeada (usa uma variável d).
     .BQ Na representação binária da entrada ...
   XZ ... Insira um zero ...
    d ... No índice d.
  i 2 | E converta o resultado da base 2 em um número inteiro.
------------ + - + ----------------------------------- ------------------
s Soma a lista resultante.

Gelatina , 10 bytes

BµLḤ_J’×µḄ

Experimente online!

Não é o mais curto atualmente, mas poderia ser se houvesse uma maneira de contornar Bµ µḄ...

Explicação

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.

Basicamente, isso funciona multiplicando cada dígito binário por um número mágico. Não consigo explicar sem visualizá-lo, então aqui está o número binário com o qual trabalharemos:

1111

Conforme explicado pelo desafio, a saída que queremos é a soma desses números binários:

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

No entanto, na verdade, não precisamos inserir zeros: o átomo "não-binário" de Jelly aceitará outros números além de apenas 0e 1. Quando nos permitimos usar 2, esse padrão fica mais simples:

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

Quando somamos os dígitos em cada coluna, obtemos

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

O truque que esta resposta usa é gerar esse padrão e multiplicar cada dígito pelo dígito correspondente no original para cancelar as colunas necessárias. 12, por exemplo, seria representado como

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

Java 8, 55 bytes

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

Resposta C da porta do Steadybox ' e colocou 3 bytes de golfe no processo.

Experimente online.

Casca , 13 12 bytes

-1 byte graças a @Mr. Xcoder!

ṁḋ§z·+Θḣotṫḋ

Experimente online!

Explicação

ṁḋ§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 bytes

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

Experimente online!

Pip , 21 18 bytes

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

Experimente online!

Explicação

Ligue para o nosso número de entrada a. Para cada índice binário ino qual queremos inserir um zero, podemos calcular os bits restantes do ponto de inserção como a // 2**i(onde //é a divisão inteira e a **exponenciação), os bits à direita do ponto de inserção como a % 2**ie, portanto, o número inteiro diluído como 2 * (a // 2**i) * 2**i + (a % 2**i). Mas (a // 2**i) * 2**ié igual a a - (a % 2**i), e assim podemos reorganizar para uma fórmula mais curta: 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 bytes

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

Experimente online!

Ou eu estou fazendo algo realmente errado ou R é terrível em manipulação de bits. Portar a abordagem de Luis Mendo é fácil, correta e divertida.

Mas se você realmente quer apenas mexer com operações de bits, MickyT sugeriu o seguinte 105 byter:

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

Experimente online!

Python 3, 92 80 78 bytes

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

Experimente Online

Obrigado ao Mr.XCoder e ovs por -12 bytes e -2 bytes, respectivamente.

Lote, 92 77 bytes

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

Editar: alternado para a mesma fórmula que todo mundo está usando.

Gelatina , 14 bytes

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

Experimente online!

Perl 5 , 36 + 1 ( -p) = 37 bytes

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

Experimente online!

Anexo , 57 bytes

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

Experimente online!

Eu pensei em abordar o problema a partir de uma abordagem de manipulação não-bit, pois essa abordagem é impraticável no Attache. Eu tenho que investigar algumas das partes desta abordagem para alternativas.

Explicação

Aqui está uma versão expandida:

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

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

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

Isso simplesmente pega a representação binária do número, divide-a em determinados pontos, insere zeros lá, converte de volta para decimal e soma-os.

J , 33 bytes

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

Provavelmente há muito espaço para mais golfe.

Quão?

@#: converter para binário e

<@}.\. - encontre todos os elementos suficientes, solte o primeiro dígito de cada e

<\ - encontre todos os prefixos e encaixe-os

(,0;])"0 - para cada prefixo, adicione 0 e, em seguida, adicione o sufixo decapitado correspondente

;@ raze (unbox)

1#.[:}:#.@ - converter para decimal, reduzir e somar

Experimente online!