Diese Herausforderung ist einfach: Geben Sie eine Dezimalzahl ein, wandeln Sie sie in eine Binärzahl um und berechnen Sie die Summe der Teilzeichenfolgen der Binärzahl, deren Länge kürzer als die ursprüngliche Zahl ist. Hier ist ein Beispiel:

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

Ihr Programm sollte eine einzelne Dezimalzahl als Eingabe verwenden und die Summe der binären Teilzeichenfolgen ausgeben, wie oben gezeigt. Sie können davon ausgehen, dass die Eingabe in ihrer Binärdarstellung immer mehr als zwei Stellen hat und dass die Eingabe während der Ausführung Ihres Programms keine Fehler verursacht.

Das ist Code-Golf , der kürzeste Code in Bytes gewinnt!

Testfälle:

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

Gelee, 10 7 Bytes

BṡRḄFS_

Probieren Sie es online!

Wie es funktioniert

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

Probieren Sie es online aus oder führen Sie die Test Suite aus

Erläuterung:

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 Bytes

Grüße Dennis, der mir geholfen hat, 6 Bytes zu sparen!

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

Funktioniert nur mit der neuesten Version von CJam (verfügbar bei TIO). Probieren Sie es online !

Alte Version:

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

Probieren Sie es online aus .

Python 3, 111 Zeichen

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)]))

EDIT : Erklärung:

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

Konvertieren Sie die Eingabezeichenfolge in eine Ganzzahl, dann die Ganzzahl in eine Binärzeichenfolge und entfernen Sie die ersten beiden Zeichen, da die binMethode eine Zeichenfolge im Format von zurückgibt0b...

Nehmen Sie alle Teilzeichenfolgen der Binärzeichenfolge, konvertieren Sie sie mit in Dezimalzeichen int(n, 2)und addieren Sie sie.

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

ist eine Liste aller Teilzeichenfolgen. Ungolfed-Version:

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

Hoffe das hilft.

CJam (22 Bytes)

Dies ist ein Byte länger als die derzeit beste CJam-Antwort, aber der Ansatz kann wahrscheinlich recht gewinnbringend an einige andere Sprachen angepasst werden.

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

Online-Demo

Analyse

Angenommen, die Frage wäre

Berechnen Sie die Summe der Teilstrings der Binärzahl

ohne das bisschen

deren Länge ist kürzer als die ursprüngliche Nummer

Dann ist es nicht allzu schwer zu zeigen , dass die höchstwertigen Bits mit einem Gesamtgewicht auftritt , 1*(2^B-1)wo Bdie Anzahl von Bits; Das zweitwichtigste Bit tritt mit dem Gesamtgewicht auf 2*(2^(B-1)-1). bis zum Bth-höchstwertigen Bit, das mit dem Gesamtgewicht auftritt B*(2^1-1).

Berücksichtigt man nun die Subtraktion der ursprünglichen Zahl x, so ergibt sich die Summe

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

Präparation

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

Die Umrechnung auf Basis 2 ergibt den ersten Teil der Hauptsumme plus x; zur Basis 1 gibt der zweite Teil plus x; und zur Basis 0 ergibt gerade x, so subtrahiert man die Basis 1 von der Basis 2, so ergibt die xAufhebung und subtrahiert man die Basis 0, so ergibt sich das gewünschte Ergebnis.

JavaScript (ES6), 78 Byte

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

Das Äußere mapbaut führende Teilzeichenfolgen der nBinärdarstellung auf. Das innere extrahiert nachfolgende Teilzeichenfolgen der führenden Teilzeichenfolgen und deckt so alle möglichen Teilzeichenfolgen ab, einschließlich der ursprünglichen Binärdarstellung.

Jede Teilzeichenfolge wird von binär zurück in dezimal konvertiert und von der ursprünglichen Eingabe subtrahiert, da dies etwas kürzer ist als das Addieren und Subtrahieren der ursprünglichen Eingabe.

Mathematica, 73-70 Bytes

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

Funktion. Ganzzahl-> Ganzzahl

Retina , 64

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

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

Probieren Sie es online!

Eine übergeordnete Beschreibung der einzelnen Phasen: Konvertieren von Dezimalzahlen in Unärzahlen, Unärzahlen in Binärzahlen, Abrufen von Präfixen, Abrufen von Präfix-Suffixen, Ausgeben der ursprünglichen Zahl, Konvertieren von Binärzahlen in Unärzahlen, Zurückgeben der Anzahl. Sobald ich mit dem Golfen fertig bin, schreibe ich eine detailliertere Beschreibung. Viele dieser Stadien scheinen verdächtig ...

C 71 Bytes

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;}

Wir pflegen einen Akku aund eine Maske m. Die Maske beginnt bei 1 und wird jedes Mal um die äußere Schleife ein bisschen länger. In der inneren Schleife wird eine Kopie ider Eingabe nacheinander nach rechts verschoben, bis sie kürzer als die Maske ist. Dabei wird jedes Mal der maskierte Wert akkumuliert.

Testprogramm

#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;
}

Ausgang testen

./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

148 Bytes

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;}

Oder wenn ich Import "using static System.Math;" hinzufüge dann 138 mit

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;}

OOP-Sprachen wie C # werden ein solches Rennen nicht gewinnen, aber ich wollte es trotzdem versuchen. Hier ist eine schönere Version + 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;
    }
}

Das verschachtelte do-while addiert den rechtsverschobenen Wert von iTemp (nachdem es zugewiesen wurde), solange shift + 1 kleiner als pos ist. Die nächste Zeile berechnet den nächsten verschobenen Wert von 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 und x2 berechnen die Maske, x3 wendet sie an und verschiebt sie dann nach links, da die letzte Ziffer immer weggelassen wird. Für 11 sieht es so aus:

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 Bytes

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

Ooof. Diese Konvertierung von / nach Binär ist teuer.

Übernimmt die Eingabe $aund verwendet dann den .NET-Aufruf[convert]::ToString($a,2) in eine Binärdarstellung um. Von dort durchlaufen wir zwei Schleifen - die erste zählt rückwärts vom Ende der Saite abwärts 1und die zweite zählt aufwärts abwärts 0. (Das erste ist, wie lange ein Teilstring entfernt werden soll, und das zweite ist der Index, an welcher Stelle im String der Teilstring gestartet werden soll.) Wir setzen einen Helfer $lauf dem Weg, um diesen zur inneren Schleife durchzuleiten.

Innerhalb der inneren Schleife verwenden wir einen anderen .NET-Aufruf[convert]::ToInt32() , um die entsprechende .substring()from base 2in eine Ganzzahl umzuwandeln . Jeder von diesen wird dann in der Pipeline belassen. Wir kapseln das alles mit parens ()und -joinsie zusammen mit a+ , dann werfen das weg zu iex(kurz für Invoke-Expressionund ähnlich zu eval).

_{Ich denke, dies erfordert technisch v2 oder neuer, um die .NET-Aufrufe richtig aufzurufen.}