To wyzwanie jest proste, biorąc pod uwagę liczbę dziesiętną, przekonwertować na liczbę binarną i obliczyć sumę podłańcuchów liczby binarnej, której długość jest mniejsza niż liczba pierwotna. Oto przykład:

Input:
  11
Binary:
  11 -> 1011
Substrings:
  101 = 5
  011 = 3
  10  = 2
  01  = 1
  11  = 3
  1   = 1
  0   = 0
  1   = 1
  1   = 1
Sum:
  5+3+2+1+3+1+0+1+1=17
Output:
  17

Twój program powinien przyjmować jedną liczbę całkowitą dziesiętną jako dane wejściowe i wyjściowe sumę podciągów binarnych, jak pokazano powyżej. Możesz założyć, że wejście zawsze będzie miało więcej niż dwie cyfry w swojej reprezentacji binarnej i że na wejściu nie spowoduje żadnych błędów podczas wykonywania programu.

To jest code-golf , wygrywa najkrótszy kod w bajtach!

Przypadki testowe:

2  => 1
3  => 2
4  => 3
5  => 5
6  => 7
7  => 9
8  => 7
9  => 10
10 => 14
11 => 17

Galaretka, 10 7 bajtów

BṡRḄFS_

Wypróbuj online!

Jak to działa

BṡRḄFS_  Main link. Input: n

B        Convert n to base 2.
  R      Yield [1, ..., n].
 ṡ       Get all overlapping slices of lengths 1 to n.
         This yields empty arrays if the slice size is longer than the binary list.
   Ḅ     Convert each binary list to integer.
    F    Flatten the resulting, nested list.
     S   Compute the sum of the result.
      _  Subtract n from the sum.

Pyth, 10

sPiR2.:.BQ

Wypróbuj online lub uruchom pakiet testowy

Wyjaśnienie:

sPiR2.:.BQ    ##   Q = eval(input())
       .BQ    ##   get binary string of Q
     .:       ##   get all substrings of that
  iR2         ##   convert them all to base 10
sP            ##   sum all but the last element, which is the input number

CJam, 27 21 bajtów

Wołaj do Dennisa za pomoc w oszczędzeniu 6 bajtów!

q~:Q{)Q2bew2fb~}%1bQ-

Działa tylko z najnowszą wersją CJam (dostępną w TIO). Wypróbuj online !

Stara wersja:

qi2b_,,0-\f{ew}{{2b}%}%e_:+

Wypróbuj online .

Python 3, 111 znaków

N=bin(int(input()))[2:];L=len(N);r=range;print(sum(int(n,2)for n in[N[j:j+i]for i in r(1,L)for j in r(L-i+1)]))

EDYCJA : Objaśnienie:

N=bin(int(input()))[2:]

Konwertuj ciąg wejściowy na int, a następnie int na ciąg binarny i usuń jego pierwsze dwa znaki, ponieważ binmetoda zwraca ciąg w formacie0b...

Weź wszystkie podciągi ciągu binarnego, przekonwertuj je na dziesiętne za pomocą int(n, 2)i zsumuj.

[N[j:j+i]for i in r(1,L)for j in r(L-i+1)]

to lista wszystkich podciągów. Wersja bez golfa:

def all_substrings(N):
    result = []
    for i in range(1, len(N)):
        for j in range(len(N) - i + 1):
            result.append(N[j:j+i])
    return result

Mam nadzieję że to pomoże.

CJam (22 bajty)

Jest to jeden bajt dłuższy niż obecna najlepsza odpowiedź CJam, ale podejście to prawdopodobnie można dość dobrze dostosować do niektórych innych języków.

3,ri_2b_,,:).*\+fbW%:-

Demo online

Analiza

Załóżmy, że pytanie było

obliczyć sumę podłańcuchów liczby binarnej

bez odrobiny

którego długość jest mniejsza niż oryginalny numer

Nietrudno więc wykazać, że najbardziej znaczący bit występuje przy całkowitej masie, 1*(2^B-1)gdzie Bjest liczba bitów; drugi najbardziej znaczący bit występuje przy całkowitej masie 2*(2^(B-1)-1); aż do B-najbardziej znaczącego bitu, który występuje przy całkowitej masie B*(2^1-1).

Biorąc teraz pod uwagę odjęcie pierwotnej liczby x, otrzymujemy sumę

sum_i (x & 2^i) * 2^i * 2*(B-i)  -  sum_i (x & 2^i) * (B-i)  -  x

Sekcja

3,        e# Put [0 1 2] on the stack - we'll need it later
ri_       e# Get the input x and copy it
2b        e# Convert the copy to base 2
_,,:).*   e# Pointwise multiply by 1 plus the index
\+        e# Append x to the resulting array, giving A
fb        e# Map a base conversion
W%:-      e# Reverse and fold a subtraction

Konwersja do podstawy 2 daje pierwszą część sumy głównej plus x; podstawa 1 daje drugą część plus x; a podstawa 0 daje właśnie x, więc odjęcie podstawy-1 od podstawy-2 xpowoduje anulowanie s, a odjęcie podstawy-0 daje pożądany wynik.

JavaScript (ES6), 78 bajtów

n=>[...n.toString(2)].map(c=>[...s+=c].map((_,i)=>n-='0b'+s.slice(i)),s='')|-n

Zewnętrzne maptworzy wiodące podciągi nbinarnej reprezentacji; wewnętrzna wyciąga końcowe podciągi wiodących podłoży, pokrywając w ten sposób wszystkie możliwe podłańcuchy, w tym oryginalną reprezentację binarną.

Każdy podciąg jest konwertowany z binarnego z powrotem na dziesiętny i odejmowany od oryginalnego wejścia, ponieważ jest to nieco krótsze niż dodawanie ich razem i odejmowanie oryginalnego wejścia.

Mathematica, 73 70 bajtów

Tr[FromDigits[#,2]&/@StringCases[#~IntegerString~2,__,Overlaps->All]]&

Funkcjonować. Liczba całkowita-> Liczba całkowita

Retina , 64

.*
$*
+`(1+)\1
$1a
a1
1
r&!M`.*
&!M`.*
^.*

+`1(a*)\b
a$.1$*1;
;

Wypróbuj online!

Opis wysokiego poziomu etap po etapie: konwertuj liczbę dziesiętną na unarską, unarną na binarną, uzyskaj prefiksy, uzyskaj sufiksy prefiksów, zrzuć oryginalny numer, konwertuj binarny na unarny, zwracaj liczbę. Bardziej szczegółowy opis napiszę, kiedy skończę grać w golfa, wiele z tych etapów wydaje się podejrzanych ...

C, 71 bajtów

f(n){int a=0,m=0,i;for(;++m<n;m+=m)for(i=n;i+i>m;i/=2)a+=i&m;return a;}

Utrzymujemy akumulator a i maskę m. Maska zaczyna się od 1 i za każdym razem staje się nieco dłuższa wokół zewnętrznej pętli. W wewnętrznej pętli kopia idanych wejściowych jest sukcesywnie przesuwana w prawo, aż będzie krótsza niż maska, gromadząc za każdym razem zamaskowaną wartość.

Program testowy

#include <stdio.h>
#include <stdlib.h>
int main(int argc, char **argv) {
    while (*++argv) {
        int n = atoi(*argv);
        printf("%d -> %d\n", n, f(n));
    }
    return 0;
}

Wyjście testowe

./73793 $(seq 0 11)
0 -> 0
1 -> 0
2 -> 1
3 -> 2
4 -> 3
5 -> 5
6 -> 7
7 -> 9
8 -> 7
9 -> 10
10 -> 14
11 -> 17

C #, 148 bajtów

int x(int i){int s,r=0,j=i,p=System.Convert.ToString(i,2).Length+1,k;for(;--p>-1;){k=j;s=-1;for(;++s<p;)r+=(k>>=1);j=(i&((1<<p-1)-1))<<1;}return r;}

Lub jeśli dodam opcję Importuj „za pomocą statycznego System.Math;” następnie 138 z

int x(int i){int s,r=0,j=i,p=(int)Round(Log(i,2)+1.49,0),k;for(;--p>-1;){k=j;s=-1;for(;++s<p;)r+=(k>>=1);j=(i&((1<<p-1)-1))<<1;}return r;}

Języki OOP, takie jak C #, nie wygrywają takiego wyścigu, ale i tak chciałem spróbować. Oto bardziej upiększona wersja + tester.

class Program
{
    // Tester: 50 bytes
    static void Main(string[] args)
    {
        int i=2;
        do System.Console.WriteLine($"{i} -> {x(i++)}"); while (i < 12);
        System.Console.Read();
    }
    // Function: 65 bytes (size according to ILDASM.exe)
    static int x(int iOrg)
    {
        int pos, shift, retVal=0, iPrev=iOrg, iTemp;
        pos = System.Convert.ToString(iOrg, 2).Length;
        do {
            iTemp = iPrev; shift = 0;
            do retVal += (iTemp >>= 1); while (++shift < pos);
            iPrev = (iOrg & ((1 << pos - 1) - 1)) << 1;
        } while (--pos > -1); 
        return retVal;
    }
}

Zagnieżdżona funkcja „do while” dodaje przesuniętą w prawo wartość iTemp (po przypisaniu jej), o ile shift + 1 jest mniejszy niż poz. Następny wiersz oblicza następną przesuniętą wartość iPrev

x1 = 1 << p -1; // 1 << 4 -1 = 8 [1000]
x2 = x1 - 1;    // 8 -  1 = 7    [0111]
x3 = i & x2;    // 1011 & 0111 = 0011 
x4 = x3 << 1;   // 0011 << 1 = 00110
i2 = x4;

x1 i x2 oblicz maskę, x3 stosuje ją, a następnie przesuwa w lewo, ponieważ ostatnia cyfra jest zawsze upuszczana. W przypadku 11 wygląda to tak:

START -> _1011[11]
101
10
1   -->  X0110[6], r=0+5+2+1=8
 011
 01
 0  -->  XX110[6], r=8+4=12
  11
  1 -->  XXX10[2], r=12+4=16
   1 ->  XXXX0[X], r=16+1=17

PowerShell v2 +, 138 bajtów

param($a)$a=[convert]::ToString($a,2);(($b=$a.length-1)..1|%{$l=$_;0..($b-$l+1)|%{[convert]::ToInt32($a.substring($_,$l),2)}})-join'+'|iex

O nie. Ta konwersja do / z pliku binarnego jest droga.

Pobiera dane wejściowe $a, a następnie używa wywołania .NET,[convert]::ToString($a,2) aby przekształcić je w reprezentację binarną. Stamtąd przechodzimy przez dwie pętle - pierwsza odlicza wstecz od końca łańcucha do 1, a druga od góry 0. (Pierwsza to długość podciągu do wyciągnięcia, a druga to indeks miejsca w ciągu, aby rozpocząć podciąg.) Ustawiamy pomocnika$l po drodze, aby przekazać go do wewnętrznej pętli.

Wewnątrz wewnętrznej pętli używamy innego wywołania .NET[convert]::ToInt32() do konwersji odpowiedniej wartości .substring()z bazy 2na liczbę całkowitą. Każdy z nich jest następnie pozostawiany w rurociągu. Łączymy to wszystko za pomocą parens ()i -joinich razem z a +, a następnie wrzucamy to do iex(skrót od Invoke-Expressioni podobne do eval).

_{Myślę, że technicznie wymaga to wersji 2 lub nowszej, aby poprawnie wywoływać wywołania platformy .NET.}