Inspirado en el cuarto problema de BMO2 2009 .

Dado un entero positivo n como entrada o parámetro, devuelve el número de enteros positivos cuyas representaciones binarias se producen como bloques en la expansión binaria de n .

Por ejemplo, 13 -> 6 porque 13 en binario es 1101 y tiene subcadenas 1101, 110, 101, 11, 10, 1. No contamos los números binarios que comienzan con cero y no contamos el cero en sí.

Casos de prueba

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

Puede tomar n como cualquiera de los siguientes:

• un entero
• una lista de valores de verdad / falsedad para la representación binaria
• una cadena para la representación binaria
• una cadena de base 10 (aunque no estoy seguro de por qué alguien haría esto)

Haz tu código lo más corto posible.

Python 3, 54 50 bytes

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

Gracias a Rod y Jonathan Allan por guardar cuatro bytes.

Jalea , 4 bytes

ẆQSḢ

Pruébalo en línea!

Toma entrada como lista de 0sy 1s.

¡Pruébelo en línea con números!

Explicación:

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

Prueba de que funciona:

Este programa recibe un número de entrada, N . Lo primero que hace este producto es, por supuesto, tomar las subcadenas de N ₂ ( N en la base 2 ). Esto incluye subcadenas duplicadas que comienzan con 0 o 1 .

Después de eso, simplemente tomamos las subcadenas únicas manteniendo solo la primera aparición de cada valor en la lista de subcadenas.

Luego, este programa suma los primeros elementos de las listas, luego los segundos elementos, luego el tercero, el cuarto, etc. y si una de las listas no tiene dicho elemento, 0se supone. Lo que el desafío pregunta es efectivamente ¿Cuántas subcadenas únicas que comienzan con 1 tiene este número en su forma binaria? . Como cada primer elemento que debe contarse es 1, simplemente podemos sumar en lugar de filtrar las subcadenas apropiadas.

Ahora, el primer elemento de la lista resultante de la suma descrita anteriormente contiene el recuento de los primeros bits de las subcadenas, por lo que simplemente aparece y finalmente lo devuelve.

Octava , 62 61 bytes

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

Pruébalo en línea!

Explicación

Para la entrada n, el código prueba todos los números desde 1hasta npara ver si su representación binaria es una subcadena de la representación binaria de la entrada.

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

Toma la entrada como una cadena binaria.
El encabezado convierte la entrada entera en binario para facilitar la prueba.

ŒCÙĀO

Pruébalo en línea!

Explicación

Π       # 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

Pruébalo en línea!

Toma la entrada como una cadena binaria.

PowerShell , 103 92 82 bytes

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

Pruébalo en línea!

Toma datos como una matriz de 1y 0(verdadero y falso en PowerShell). Recorre $s(es decir, cuántos elementos en la matriz de entrada). Dentro del ciclo, realizamos un ciclo desde el número actual (guardado como $i) hasta $s.count. Cada ciclo interno, dividimos -joinla matriz en una cadena. Luego, sortcon la -ubandera de nique (que es más corta que selectcon la -ubandera de nique y no nos importa si están ordenados o no), tomamos los que no comienzan 0y toman el total .count. Eso queda en la tubería y la salida es implícita.

JavaScript (ES6), 55 bytes

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

Toma la entrada como una cadena binaria.

Aquí hay un triste intento de hacerlo con números y funciones recursivas:

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)

Enfoque antiguo, 74 bytes

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

También toma la entrada como una cadena binaria.

Python 2 ,  118  81 bytes

¡Gracias a @Rod por guardar 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})

Toma la entrada como una cadena binaria.

Pruébalo en línea!

Python 2 , 81 bytes

Gracias a @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]})

Toma la entrada como una cadena binaria.

Pruébalo en línea!

Jalea , 5 bytes

ẆḄQṠS

Pruébalo en línea!

Toma la entrada como una lista de 1s y 0s. El pie de página en el enlace aplica la función a cada uno de los ejemplos en la publicación.

Jonathan Allan señaló que ẆḄQTLes una alternativa de 5 bytes que utiliza el Tátomo que encuentra los índices de todos los elementos de verdad.

Explicación

Tome bin (13) = 1101 como ejemplo. La entrada es[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

Tomó la idea de "verdad" (firmar en este caso) de la respuesta 05AB1E

R , 88 77 bytes

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

Pruébalo en línea!

Toma la entrada como una cadena binaria.

utilizando mapply, genera una matriz de todas las subcadenas de la entrada. strtoilos convierte como 2enteros base , y tomo la suma de la conversión lógica ( !!) de entradas en el resultado.

Retina , 37 29 bytes

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

Pruébalo en línea! Solo tuve que probar el wmodificador de Retina 1.0 . Editar: guardado 8 bytes gracias a @MartinEnder. Explicación:

.+
*

Convierte de decimal a unario.

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

Convierta de unario a binario, utilizando #for 0y _for 1.

wp`_.*

Generar subseries que comienzan con 1, quiero decir, _. El wmodificador continuación, coincide con todas las subcadenas, no sólo la más larga en cada partida _, mientras que el pdeduplica modificadoras los partidos. Finalmente, como esta es la última etapa, el recuento de coincidencias se devuelve implícitamente.

Pyth , 8 bytes

l #{vM.:

Pruébalo aquí!

Toma la entrada como una cadena binaria.

.:genera todas las subcadenas, vMevalúa cada una (es decir, las convierte de binarias), {deduplica, <space>#filtra por identidad y lobtiene la longitud.

Wolfram Language (Mathematica) , 35 bytes

Contando subsecuencias únicas de la representación binaria que comienzan con una, aunque no estoy seguro de que este código incluso necesite una explicación.

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

Pruébalo en línea!

Perl 6 , 47 bytes

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

Pruébalo en línea!

Julia 0.6 , 37 bytes

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

Pruébalo en línea!

Juliafication de la respuesta de Python por J843136028 usando .para la aplicación de función de elementos sabios con difusión. ( enlace )

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();

Donde n es la entrada, b es la representación binaria y l es una lista de todas las subcadenas. Publicar aquí por primera vez, definitivamente necesita mejorar, ¡y siéntase libre de señalar cualquier error! Ligeramente editado para facilitar la lectura.

Adjunto , 35 bytes

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

Pruébalo en línea!

Equivalentemente:

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

Explicación

Explicaré la segunda versión, ya que es más fácil de seguir (siendo explícito):

{#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

Toma una cadena binaria como entrada

Es ultra ineficiente

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

En parte inspirado por esta respuesta de Python 3

Pruébalo en línea!

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

Entrada como cadena binaria.
Debe haber un camino más corto ..>.>

Explicación:

Pruébalo en línea.

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

Esta es una función recursiva. Utilizamos a std::setpara contar valores, ignorando duplicados. Las dos llamadas recursivas enmascaran bits de la izquierda (f(n&i) ) y de la derecha ( f(n/2)), produciendo eventualmente todas las subcadenas como enteros.

Tenga en cuenta que si desea volver a llamarlo, s debe borrarse entre llamadas.

Programa de prueba

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

Resultados

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

Pruébalo en línea!

J , 15 bytes

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

La entrada es una lista binaria. Pruébalo en línea!

#.\\.               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.*/)}

Pruébalo

Expandido:

{
  +                                # 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
                                )
}