Dodatnią liczbę całkowitą można rozcieńczyć , wstawiając 0między dwa bity w jej rozwinięciu binarnym. Oznacza to, że nliczba -bitowa ma n-1rozcieńczenia, które niekoniecznie wszystkie są różne.

Na przykład dla 12(lub 1100binarnie) rozcieńczenia są

11000 = 24
   ^

11000 = 24
  ^

10100 = 20
 ^

W tym wyzwaniu weźmiemy sumę wszystkich rozcieńczeń, z wyjątkiem oryginalnej liczby. Ponieważ 12, biorąc sumę 24, 24, 20wyników 68, 68powinna być również wynikiem dla 12.

Wyzwanie

Biorąc pod uwagę dodatnią liczbę całkowitą n > 1jako dane wejściowe, wyślij / zwróć rozcieńczoną sumę, jak wyjaśniono powyżej.

Przykłady

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

Zasady

• Można założyć, że dane wejściowe i wyjściowe pasują do natywnego typu liczb całkowitych twojego języka.
• Dane wejściowe i wyjściowe można podawać w dowolnym dogodnym formacie .
• Dopuszczalny jest pełny program lub funkcja. Jeśli funkcja, możesz zwrócić dane wyjściowe zamiast je wydrukować.
• Standardowe luki są zabronione.
• To jest golf golfowy, więc obowiązują wszystkie zwykłe zasady gry w golfa, a wygrywa najkrótszy kod (w bajtach).

Python 2 , 43 39 bajtów

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

Wypróbuj online!

W jaki sposób?

Każde wywołanie funkcji rekurencyjnej oblicza pojedyncze rozcieńczenie. Pozycja wstawionego 0to log2(i). Funkcja powtarza się, aż istanie się większa niż, na wstawianie będzie po lewej stronie liczby. Jeśli i>n, n/iocenia na 0, co jest wartością falsy w Pythonie.

n*2przesuwa całą cyfrę binarną numer jeden w lewo n%ilub n % 2**(position of insertion)oblicza wartość części, której nie należy przesuwać w lewo. Ta wartość jest odejmowana od przesuniętej liczby.

Przykład (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

Galaretka , 11 bajtów

BJṖ2*ɓdḅḤ}S

Wypróbuj online!

Jak to działa

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 bajtów

tZl:W&\5ME*+s

Wypróbuj w MATL Online! Lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie

Rozważ dane wejściowe 12jako przykład.

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 bajtów

Dzięki @Dennis za uratowanie dwóch bajtów!

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

Wypróbuj online!

C (gcc) , 50 bajtów

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

Powrót przez k=s;jest niezdefiniowanym zachowaniem, ale działa z gcc, gdy optymalizacje są wyłączone. Ponadto n%k+n/k*(k+=k)ma nieokreślone zachowanie , ale wydaje się działać dobrze z gcc.

Wypróbuj online!

Galaretka , 9 8 bajtów

BḊḄÐƤạḤS

Wypróbuj 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

Odwrotnie B¹ƤṖ+BḄS: pobierz prefiksy, upuść ostatni, dodaj je do danych wejściowych i zsumuj.

J , 20 15 14 bajtów

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

Wypróbuj online.

15 bajtów

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

Wypróbuj online!

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

Japt , 12 11 bajtów

¢¬£¢iYTÃÅxÍ

Spróbuj

Wyjaśnienie

                 :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 bajtów

Zapisano 1 bajt dzięki Mr.Xcoder

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

Przypadki testowe

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

Siatkówka , 53 50 47 bajtów

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

Wypróbuj online! Link zawiera przypadki testowe. Edycja: Zapisano 3 bajty dzięki @MartinEnder. Wyjaśnienie:

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

Konwertuj z dziesiętnego na dwójkowy, ale używając O do reprezentowania 0, ponieważ nie jest to cyfra, i _ do reprezentowania 1, ponieważ jest to domyślny znak powtórzenia w Retina 1.

L$`\B
$`O$'

Wstaw literę O między każdą parą cyfr i zbierz wyniki jako listę.

+%`\B
¶$`¶

Konwertuj z binarnego na jednoargumentowy. (Ta konwersja generuje dodatkowe Os, ale nas to nie obchodzi.)

_

Suma i przeliczenie na dziesiętne.

Pyth , 13 bajtów

smiXd.BQZ2Ssl

Wypróbuj tutaj!

Wyjaśnienie

smiXd.BQZ2Ssl | Pełny program

           sl | Logarytm base-2 wejścia wprowadzony do liczby całkowitej.
          S | Utwórz zakres liczb całkowitych [1 ... logarytm zmiennoprzecinkowy].
 m | I odwzoruj na nim funkcję.
------------ + - + ----------------------------------- ------------------
  iXd.BQZ2 | Funkcja do zmapowania (wykorzystuje zmienną d).
     .BQ | W binarnej reprezentacji wejścia ...
   XZ | ... Wstaw zero ...
    d | ... o indeksie d.
  i 2 | I przekonwertuj wynik z podstawy 2 na liczbę całkowitą.
------------ + - + ----------------------------------- ------------------
s | Zsumuj wynikową listę.

Galaretka , 10 bajtów

BµLḤ_J’×µḄ

Wypróbuj online!

Obecnie nie najkrótszy, ale może być, jeśli istnieje sposób na obejście Bµ µḄ...

Wyjaśnienie

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.

Zasadniczo działa to poprzez pomnożenie każdej cyfry binarnej przez liczbę magiczną. Nie potrafię tego wyjaśnić bez wizualizacji, więc oto liczba binarna, z którą będziemy pracować:

1111

Jak wyjaśniono w wyzwaniu, chcemy, aby wynik był sumą tych liczb binarnych:

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

Jednak tak naprawdę nie musimy wstawiać zer: „niebinarny” atom galaretki akceptuje liczby inne niż tylko 0i 1. Gdy pozwolimy sobie na użycie 2, ten wzór staje się prostszy:

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

Po zsumowaniu cyfr w każdej kolumnie otrzymujemy

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

Trik zastosowany w tej odpowiedzi polega na wygenerowaniu tego wzoru i pomnożeniu każdej cyfry przez odpowiednią cyfrę w oryginale, aby skasować niezbędne kolumny. 12, na przykład, byłoby reprezentowane jako

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

Java 8, 55 bajtów

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

Port odpowiedzi Steadyboksa C i grał w golfa 3 bajty.

Wypróbuj online.

Łuska , 13 12 bajtów

-1 bajt dzięki @Mr. Xcoder!

ṁḋ§z·+Θḣotṫḋ

Wypróbuj online!

Wyjaśnienie

ṁḋ§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 bajtów

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

Wypróbuj online!

Pip , 21 18 bajtów

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

Wypróbuj online!

Wyjaśnienie

Zadzwoń na nasz numer wejściowy a. Dla każdego indeksu binarnego, iprzy którym chcemy wstawić zero, możemy obliczyć bity po lewej stronie punktu wstawiania jako a // 2**i(gdzie //jest dzielenie całkowite i **wykładnik), bity po prawej stronie punktu wstawienia jako a % 2**i, a zatem rozcieńczoną liczbę całkowitą jako 2 * (a // 2**i) * 2**i + (a % 2**i). Ale (a // 2**i) * 2**ijest równa a - (a % 2**i), a więc możemy zmienić na krótszą formułę: 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 bajtów

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

Wypróbuj online!

Albo robię coś naprawdę złego, albo R jest po prostu okropnie manipulowany. Podejście do portowania Luisa Mendo jest łatwe, poprawne i gra w golfa.

Ale jeśli naprawdę chcesz po prostu wygrać z operacjami bitowymi, MickyT zasugerował następujące 105 bajtów:

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

Wypróbuj online!

Python 3, 92 80 78 bajtów

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

Wypróbuj online

Dzięki Mr.XCoder i ovs odpowiednio dla -12 bajtów i -2 bajtów.

Partia, 92 77 bajtów

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

Edycja: Przełączono na tę samą formułę, której używają wszyscy inni.

Galaretka , 14 bajtów

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

Wypróbuj online!

Perl 5 , 36 + 1 ( -p) = 37 bajtów

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

Wypróbuj online!

Attache , 57 bajtów

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

Wypróbuj online!

Myślałem, że podchodzę do problemu z nie-bitowej manipulacji, ponieważ takie podejście jest niepraktyczne w Attache. Muszę zbadać niektóre części tego podejścia w odniesieniu do alternatyw.

Wyjaśnienie

Oto rozszerzona wersja:

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

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

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

To po prostu bierze binarną reprezentację liczby, dzieli ją w określonych punktach, wstawia tam zera, konwertuje z powrotem na dziesiętne i sumuje je razem.

J , 33 bajty

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

Najprawdopodobniej jest dużo miejsca na dalszą grę w golfa.

W jaki sposób?

@#: przekonwertować na binarny i

<@}.\. - znajdź wszystkie wystarczające, upuść pierwszą cyfrę z każdego i pola

<\ - znajdź wszystkie prefiksy i zapakuj je

(,0;])"0 - do każdego prefiksu dołącz 0, a następnie dołącz odpowiedni sufiks ścięty

;@ Raze (rozpakuj)

1#.[:}:#.@ - konwertuj na dziesiętne, skracaj i sumuj

Wypróbuj online!