Inspiriert vom vierten Problem von BMO2 2009 .

Geben Sie bei einer positiven Ganzzahl n als Eingabe oder einem Parameter die Anzahl der positiven Ganzzahlen zurück, deren binäre Darstellungen als Blöcke in der binären Erweiterung von n auftreten .

Beispiel: 13 -> 6, da 13 in der Binärdatei 1101 ist und Teilzeichenfolgen enthält 1101, 110, 101, 11, 10, 1. Wir zählen keine Binärzahlen, die mit Null beginnen, und wir zählen selbst keine Null.

Testfälle

13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

Sie können n wie folgt aufnehmen:

• eine ganze Zahl
• eine Liste von Wahrheits- / Falschwerten für die Binärdarstellung
• ein String für die Binärdarstellung
• eine Base-10-Saite (obwohl ich nicht sicher bin, warum das jemand tun würde)

Machen Sie Ihren Code so kurz wie möglich.

Python 3, 54 50 Bytes

lambda n:sum(bin(i)[2:]in bin(n)for i in range(n))

Vielen Dank an Rod und Jonathan Allan für das Speichern von vier Bytes.

Gelee , 4 Bytes

ẆQSḢ

Probieren Sie es online!

Übernimmt die Eingabe als Liste von 0s und 1s.

Probieren Sie es online mit Zahlen!

Erläuterung:

ẆQSḢ Argument: B = list of bits, e.g. [1, 1, 0, 1]
Ẇ    Get B's non-empty sublists (i.e. [[1], [1], [0], [1], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
 Q   Keep first occurrences (i.e. [[1], [0], [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
  S  Reduce by vectorized addition (i.e. [6, 4, 1, 1])
   Ḣ Pop first element (i.e. 6)

Beweis, dass es funktioniert:

Dieses Programm wird eine Eingangsnummer, N . Das erste, was dieses Produkt tut, ist natürlich, die Teilzeichenfolgen von N ₂ ( N in Basis 2 ) zu nehmen. Dies schließt doppelte Teilzeichenfolgen ein, die mit 0 oder 1 beginnen .

Danach nehmen wir einfach die eindeutigen Teilzeichenfolgen, indem wir nur das erste Vorkommen jedes Werts in der Teilzeichenfolgenliste beibehalten.

Dann summiert dieses Programm die ersten Elemente der Listen zusammen, dann die zweiten Elemente, dann die dritten, vierten usw., und wenn eine der Listen kein solches Element aufweist, 0wird angenommen. Die eigentliche Herausforderung lautet: Wie viele eindeutige Teilzeichenfolgen, die mit 1 beginnen, hat diese Zahl in ihrer binären Form? . Da jedes erste Element, das gezählt werden soll 1, einfach summiert werden kann, anstatt nach geeigneten Teilzeichenfolgen zu filtern.

Nun enthält das erste Element der resultierenden Liste der oben beschriebenen Summierung die Anzahl der ersten Bits der Teilzeichenfolgen, sodass wir sie einfach einfügen und schließlich zurückgeben.

Oktave , 62 61 Bytes

@(n)sum(arrayfun(@(t)any(strfind((g=@dec2bin)(n),g(t))),1:n))

Probieren Sie es online!

Erläuterung

Bei der Eingabe nprüft der Code alle Zahlen von 1bis, num festzustellen, ob ihre Binärdarstellung eine Teilzeichenfolge der Binärdarstellung der Eingabe ist.

@(n)                                                          % Anonymous function of n
        arrayfun(                                      ,1:n)  % Map over range 1:n
                 @(t)                                         % Anonymous function of t
                         strfind(               ,    )        % Indices of ...
                                                 g(t)         % t as binary string ...
                                 (g=@dec2bin)(n)              % within n as binary string
                     any(                             )       % True if contains nonzero
    sum(                                                    ) % Sum of array

05AB1E , 5 Bytes

Übernimmt die Eingabe als binäre Zeichenfolge.
Der Header konvertiert Ganzzahleingaben in Binärwerte, um das Testen zu vereinfachen.

ŒCÙĀO

Probieren Sie es online!

Erläuterung

Π       # push all substrings of input
 C       # convert to base-10 int
  Ù      # remove duplicates
   Ā     # truthify (convert non-zero elements to 1)
    O    # sum

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

/.*(.+?)(?{$k{0|$1}++})(?!)/;$_=%k-1

Probieren Sie es online!

Übernimmt die Eingabe als binäre Zeichenfolge.

PowerShell , 103 92 82 Byte

param($s)(($s|%{$i..$s.count|%{-join$s[$i..$_]};$i++}|sort -u)-notmatch'^0').count

Probieren Sie es online!

Nimmt Eingaben als Array von 1und 0(wahr und falsch in PowerShell). Durchläuft $s(dh wie viele Elemente im Eingabearray). Innerhalb der Schleife durchlaufen wir die Schleife von der aktuellen Nummer (gespeichert unter $i) bis $s.count. In jeder inneren Schleife -joinschneiden wir das Array in eine Zeichenfolge. Wir dann sortmit der -uNique-Flagge (die kürzer ist als selectmit der -uNique-Flagge und es ist uns egal, ob sie sortiert sind oder nicht), nehmen diejenigen, die nicht anfangen 0, und nehmen den Overall .count. Das bleibt in der Pipeline und die Ausgabe ist implizit.

JavaScript (ES6), 55 Byte

f=(s,q="0b"+s)=>q&&s.includes((q--).toString(2))+f(s,q)

Übernimmt die Eingabe als binäre Zeichenfolge.

Hier ist ein trauriger Versuch, dies mit Zahlen und rekursiven Funktionen zu tun:

f=(n,q=n)=>q&&(g=n=>n?n^q&(h=n=>n&&n|h(n>>1))(q)?g(n>>1):1:0)(n)+f(s,q-1)

Alter Ansatz, 74 Bytes

s=>(f=s=>+s?new Set([+s,...f(s.slice(1)),...f(s.slice(0,-1))]):[])(s).size

Nimmt auch Eingaben als Binärstring an.

Python 2 ,  118  81 Bytes

Vielen Dank an @Rod für das Speichern von 37 Bytes!

lambda n:len({int(n[i:j+1],2)for i in range(len(n))for j in range(i,len(n))}-{0})

Übernimmt die Eingabe als binäre Zeichenfolge.

Probieren Sie es online!

Python 2 , 81 Bytes

Vielen Dank an @Rod!

lambda n:len({n[i:j+1]for i in range(len(n))for j in range(i,len(n))if'1'==n[i]})

Übernimmt die Eingabe als binäre Zeichenfolge.

Probieren Sie es online!

Gelee , 5 Bytes

ẆḄQṠS

Probieren Sie es online!

Nimmt die Eingabe als Liste von Einsen und Nullen. Die Fußzeile im Link wendet die Funktion auf jedes der Beispiele im Beitrag an.

Jonathan Allan wies darauf hin, dass ẆḄQTLes sich um eine 5-Byte-Alternative handelt, die das TAtom verwendet , das die Indizes aller wahrheitsgemäßen Elemente findet.

Erläuterung

Nehmen Sie als Beispiel bin (13) = 1101. Eingabe ist[1,1,0,1]

ẆḄQṠS
Ẇ       All contiguous sublists -> 1,1,0,1,11,10,01,110,101,1101 (each is represented as a list)
 Ḅ      From binary to decimal. Vectorizes to each element of the above list -> 1,1,0,1,3,2,1,6,5,13
  Q     Unique elements
   Ṡ    Sign. Positive nums -> 1 , 0 -> 0.
    S   Sum

Hat die Idee "wahrheitsgemäß" (in diesem Fall unterschreiben) aus der 05AB1E-Antwort übernommen

R , 88 77 Bytes

function(x)sum(!!unique(strtoi(mapply(substring,x,n<-1:nchar(x),list(n)),2)))

Probieren Sie es online!

Übernimmt die Eingabe als binäre Zeichenfolge.

using mapplygeneriert ein Array aller Teilzeichenfolgen der Eingabe. strtoikonvertiert sie als Basis- 2Ganzzahlen und ich nehme die Summe der logischen Konvertierung ( !!) der Einträge im Ergebnis.

Retina , 37 29 Bytes

.+
*
+`(_+)\1
$1#
#_
_
wp`_.*

Probieren Sie es online! Ich musste nur den wModifikator von Retina 1.0 ausprobieren . Bearbeiten: 8 Bytes dank @MartinEnder gespeichert. Erläuterung:

.+
*

Konvertiert von dezimal zu unär.

+`(_+)\1
$1#
#_
_

Konvertieren Sie von unär nach binär mit #for 0und _for 1.

wp`_.*

Erzeugen Sie Teilstrings, die mit 1, ich meine, beginnen _. Der wModifikator stimmt dann mit allen Teilzeichenfolgen überein, nicht nur mit der längsten bei jedem Start _, während der pModifikator die Übereinstimmungen dedupliziert. Da dies die letzte Stufe ist, wird die Anzahl der Übereinstimmungen implizit zurückgegeben.

Pyth , 8 Bytes

l #{vM.:

Probieren Sie es hier aus!

Übernimmt die Eingabe als binäre Zeichenfolge.

.:generiert alle Teilstrings, vMwertet jeden aus ( dh konvertiert jeden aus dem Binären), {dedupliziert, <space>#filtert nach Identität und lerhält die Länge.

Wolfram Language (Mathematica) , 35 Byte

Das Zählen eindeutiger Teilsequenzen der Binärdarstellung, die mit einer beginnen, obwohl ich nicht sicher bin, ob dieser Code überhaupt eine Erklärung benötigt.

Union@Subsequences@#~Count~{1,___}&

Probieren Sie es online!

Perl 6 , 47 Bytes

->\n{+grep {n.base(2).contains(.base: 2)},1..n}

Probieren Sie es online!

Julia 0,6 , 37 Bytes

~n=sum(contains.([bin(n)],bin.(1:n)))

Probieren Sie es online!

Juliafizierung der Python-Antwort durch J843136028 unter Verwendung .einer elementweisen Funktionsanwendung mit Rundfunk. ( link )

Java, 232 Bytes

String b=toBin(n);
l.add(b);
for(int i=1;i<b.length();i++){
for(int j=0;j<=b.length()-i;j++){
String t="";
if((""+b.charAt(j)).equals("0"))continue;
for(int k=0;k<i;k++){
t+=""+b.charAt(j+k);
}
if(!l.contains(t))l.add(t);
}
}
return l.size();

Dabei ist n die Eingabe, b die Binärdarstellung und l eine Liste aller Teilzeichenfolgen. Zum ersten Mal hier posten, müssen auf jeden Fall verbessert werden, und zögern Sie nicht, auf Fehler hinzuweisen! Zur besseren Lesbarkeit leicht bearbeitet.

Attache , 35 Bytes

`-&1@`#@Unique@(UnBin=>Subsets@Bin)

Probieren Sie es online!

Äquivalent:

{#Unique[UnBin=>Subsets[Bin[_]]]-1}

Erläuterung

Ich werde die zweite Version erklären, da es einfacher ist zu folgen (explizit zu sein):

{#Unique[UnBin=>Subsets[Bin[_]]]-1}
{                                 }   lambda: _ = first argument
                        Bin[_]        convert to binary
                Subsets[      ]       all subsets of input
         UnBin=>                      map UnBin over these subsets
  Unique[                      ]      remove all duplicates
 #                              -1    size - 1 (since subsets is improper)

Ruby 41 36 27 Bytes

Übernimmt einen binären String als Eingabe

Ist ultra-ineffizient

->n{(?1..n).count{|j|n[j]}}

Teilweise inspiriert von dieser Python 3-Antwort

Probieren Sie es online!

Java 8, 160 159 158 Bytes

import java.util.*;b->{Set s=new HashSet();for(int l=b.length(),i=0,j;i<l;i++)for(j=l-i;j>0;s.add(new Long(b.substring(i,i+j--))))s.add(0L);return~-s.size();}

Eingabe als Binärstring.
Es muss einen kürzeren Weg geben ..>.>

Erläuterung:

Probieren Sie es online aus.

import java.util.*;          // Required import for Set and HashSet
b->{                         // Method with String as parameter and integer as return-type
  Set s=new HashSet();       //  Create a Set
  for(int l=b.length(),      //  Set `l` to the length of the binary-String
      i=0,j;i<l;i++)         //  Loop from 0 up to `l` (exclusive)
    for(j=l-i;j>0;           //   Inner loop from `l-i` down to `0` (exclusive)
      s.add(new Long(b.substring(i,i+j--))))
                             //    Add every substring converted to number to the Set
      s.add(0L);             //    Add 0 to the Set
  return~-s.size();}         //  Return the amount of items in the Set minus 1 (for the 0)

C ++, 110 Bytes

#include<set>
std::set<int>s;int f(int n){for(int i=1;i<n;i+=i+1)f(n&i);return n?s.insert(n),f(n/2):s.size();}

Dies ist eine rekursive Funktion. Wir verwenden a, std::setum Werte zu zählen, wobei Duplikate ignoriert werden. Die beiden rekursiven Aufrufe maskieren Bits links ( f(n&i)) und rechts ( f(n/2)) und erzeugen schließlich alle Teilzeichenfolgen als Ganzzahlen.

Beachten Sie, dass, wenn Sie es erneut anrufen möchten, szwischen den Anrufen gelöscht werden muss.

Testprogramm

#include <cstdlib>
#include <iostream>

int main(int, char **argv)
{
    while (*++argv) {
        auto const n = std::atoi(*argv);
        s={};
        std::cout << n << " -> " << f(n) << std::endl;
    }
}

Ergebnisse

./153846 13 2008 63 65 850 459 716 425 327
13 -> 6
2008 -> 39
63 -> 6
65 -> 7
850 -> 24
459 -> 23
716 -> 22
425 -> 20
327 -> 16

J , 34 Bytes

f=.3 :'<:#~.,(#:i.2^##:y)#.;.1#:y'

Probieren Sie es online!

J , 15 Bytes

#.\\.#@=@-.&,0:

Die Eingabe ist eine Binärliste. Probieren Sie es online!

#.\\.               Convert every substring to decimal
         -.&,0:     Flatten and remove the 0s.        
     #@=            How many unique elements?

Perl 6 , 34 Bytes

{+unique ~«(.base(2)~~m:ex/1.*/)}

Probier es aus

Erweitert:

{
  +                                # turn into Numeric (number of elements)
   unique                          # use only the unique ones
          ~«(                      # turn into strings
             .base(2)              # the input in base 2
                     ~~
                       m:ex/1.*/   # :exhaustive match substrings
                                )
}