# Binary Substrings

Inspired by the fourth problem from BMO2 2009.

Given a positive integer n as input or a parameter, return the number of positive integers whose binary representations occur as blocks in the binary expansion of n.

For example, 13 -> 6 because 13 in binary is 1101 and it has substrings 1101, 110, 101, 11, 10, 1. We do not count binary numbers that start with zero and we do not count zero itself.

### Test Cases

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


You may take in n as any of the following:

• an integer
• a list of truthy/falsy values for the binary representation
• a string for the binary representation
• a base 10 string (though I'm not sure why anyone would do this)

Make your code as short as possible.

• Can you confirm 63->5 and not 6? Bin(63)=111111 -> six distinct nonzero substrings – dylnan Jan 22 '18 at 17:19
• Related. (Uses subsequences instead of substrings and doesn't disregard leading zeros.) – Martin Ender Jan 22 '18 at 17:22
• @dylnan Typo. Fixed. – 0WJYxW9FMN Jan 22 '18 at 17:24
• @MartinEnder Is this different enough to stay on this site or shall I delete it as a duplicate? I think it's sufficiently different, but you know a lot better than I do. – 0WJYxW9FMN Jan 22 '18 at 17:26
• @J843136028 The bigger difference for not making it a duplicate is the time restriction on the other challenge. You're fine. (Just posted the link, so that the challenges show up in each other's sidebar.) – Martin Ender Jan 22 '18 at 17:27

# Python 3, 54 50 bytes

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


Thanks to Rod and Jonathan Allan for saving four bytes.

• You can move the +1 from the range to bin(i) – Rod Jan 22 '18 at 17:50
• In fact since we always count n itself and are to always exclude 0 from our count we can instead always exclude n and always count 0 (bin(n) starts '0b...'), hence we can remove the 1, and +1 entirely and leave bin(i) as is to save four bytes Try it online! – Jonathan Allan Jan 22 '18 at 18:11

# Jelly, 4 bytes

ẆQSḢ


Try it online!

Takes input as list of 0s and 1s.

Try it online with numbers!

Explanation:

ẆQSḢ Argument: B = list of bits, e.g. [1, 1, 0, 1]
Ẇ    Get B's non-empty sublists (i.e. [, , , , [1, 1], [1, 0], [0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 0, 1]])
Q   Keep first occurrences (i.e. [, , [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)


Proof it works:

This program gets an input number, N. The first thing this product does is, of course, take the substrings of N2 (N in base 2). This includes duplicate substrings starting with either 0 or 1.

After that, we simply take the unique substrings by keeping only the first occurrence of each value in the substring list.

Then, this program sums the first elements of the lists together, then the second elements, then the third, fourth, etc. and if one of the lists has no such element 0 is assumed. What the challenge asks is effectively How many unique substrings starting with 1 does this number have in its binary form?. Since every first element which is to be counted is 1, we can simply sum instead of filtering for appropriate substrings.

Now, the first element of the resulting list of the summation described above holds the count of the first bits of the substrings, so we simply pop and finally return it.

# Octave, 62 61 bytes

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


Try it online!

### Explanation

For input n, the code tests all numbers from 1 to n to see if their binary representation is a substring of the binary representation of the input.

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

Takes input as a binary string.
The header converts integer input to binary for ease of testing.

ŒCÙĀO


Try it online!

Explanation

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

• Awwhh... I thought my filter was smart. bŒʒć}Ùg but nope, that's better. – Magic Octopus Urn Jan 23 '18 at 20:10

/.*(.+?)(?{$k{0|$1}++})(?!)/;$_=%k-1  Try it online! Takes input as a binary string. # PowerShell, 10392 82 bytes param($s)(($s|%{$i..$s.count|%{-join$s[$i..$_]};$i++}|sort -u)-notmatch'^0').count  Try it online! Takes input as an array of 1 and 0 (truthy and falsey in PowerShell). Loops through $s (i.e., how many elements in the input array). Inside the loop, we loop from the current number (saved as $i) up to $s.count. Each inner loop, we -join the array slice into a string. We then sort with the -unique flag (which is shorter than select with the -unique flag and we don't care whether they're sorted or not), take those that don't start with 0, and take the overall .count. That's left on the pipeline and output is implicit.

## JavaScript (ES6), 55 bytes

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


Takes input as a binary string.

Here's a sad attempt at doing it with numbers and recursive functions:

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)


### Old approach, 74 bytes

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


Also takes input as a binary string.

# Python 2,  118  81 bytes

Thanks to @Rod for saving 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})


Takes input as a binary string.

Try it online!

# Python 2, 81 bytes

Thanks to @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]})


Takes input as a binary string.

Try it online!

• You can accept a binary string as input, you can also replace set(...) with {...} and xrange with range – Rod Jan 22 '18 at 17:37
• You can also move the +1 from the range to the slice, and switch the s.startswith to int(s,2) like this – Rod Jan 22 '18 at 17:42
• If you want to keep your old approach, you can also use this for the same byte count – Rod Jan 22 '18 at 17:48

# Jelly, 5 bytes

ẆḄQṠS


Try it online!

Takes input as a list of 1s and 0s. The footer in the link applies the function to each of the examples in the post.

Jonathan Allan pointed out that ẆḄQTL is 5 byte alternative which uses the T atom which finds the indices of all truthy elements.

Explanation

Take bin(13)=1101 as an example. Input is [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


Took the "truthify" (sign in this case) idea from the 05AB1E answer

• You could actually use Jelly's Truthy Indexes atom, T, with ẆḄQTL – Jonathan Allan Jan 22 '18 at 17:46

# R, 88 77 bytes

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


Try it online!

Takes input as a binary string.

using mapply, generates an array of all substrings of the input. strtoi converts them as base 2 integers, and I take the sum of the logical conversion (!!) of entries in the result.

# Retina, 37 29 bytes

.+
*
+(_+)\1
$1# #_ _ wp_.*  Try it online! I just had to try out Retina 1.0's w modifier. Edit: Saved 8 bytes thanks to @MartinEnder. Explanation: .+ *  Convert from decimal to unary. +(_+)\1$1#
#_
_


Convert from unary to binary, using # for 0 and _ for 1.

wp_.*


Generate substrings that begin with 1, I mean, _. The w modifier then matches all substrings, not just the longest one at each starting _, while the p modifier deduplicates the matches. Finally as this is the last stage the count of matches is implicitly returned.

• You can roll the last three stages into one by using the q (or p) modifier in addition to w. You also don't need to specify C explicitly, because it's the default stage type if there is only a single source left. – Martin Ender Jan 23 '18 at 9:15
• @MartinEnder Thanks, I'm still used to M being the default stage type! – Neil Jan 23 '18 at 9:53
• Well, C kinda is what M used to be. :) – Martin Ender Jan 23 '18 at 9:53
• I know why it's the default, it's just getting used to switching. – Neil Jan 23 '18 at 9:56

# Pyth, 8 bytes

l #{vM.:


Try it here!

Takes input as a binary string.

.: generates all the substrings, vM evaluates each (that is, it converts each from binary), { deduplicates, <space># filters by identity and l gets the length.

# Wolfram Language (Mathematica), 35 bytes

Counting unique subsequences of the binary representation that start with one, although I'm not sure this code even needs an explanation.

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


Try it online!

• What does ___ do? – FrownyFrog Jan 23 '18 at 20:07
• Pattern matching, _ is a single item, __ is one or more, ___ is 0 or more. – Kelly Lowder Jan 23 '18 at 20:14

# Perl 6, 47 bytes

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


Try it online!

# Julia 0.6, 37 bytes

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


Try it online!

Juliafication of the Python answer by J843136028 using . for element-wise function application with broadcasting. (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();


Where n is the input, b is the binary representation and l is a list of all the substrings. First time posting here, definitely need to improve, and feel free to point out any mistakes! Slightly edited for readability.

• Welcome to PPCG! Regarding your insertion of newlines for readability, it is usually preferred to have one scoring version which has exactly the amount of bytes as written in the header, and then an additional ungolfed or less-golfed version for readability. – Laikoni Jan 22 '18 at 23:42
• @Laikoni Thanks for the heads-up! Will keep in mind for future posts! – Nihilish Jan 22 '18 at 23:46
• String b=...,t and int i=...,j,k to save chars for repeated declarations of the same type. Your code also wouldn't qualify as an entry because it's a snippet, neither a full program nor a functional fragment, you have to write either a function or wrap your code in the lambda form – Unihedron Jan 23 '18 at 3:30

# Attache, 35 bytes

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


Try it online!

Equivalently:

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


## Explanation

I will explain the second version, as it is easier to follow (being explicit):

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


# Ruby41 36 27 bytes

Takes binary string as input

Is ultra-inefficient

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


Partly inspired by this python 3 answer

Try it online!

# Java 8, 160159 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();}


Input as binary-String.
There must be a shorter way.. >.>

Explanation:

Try it online.

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


This is a recursive function. We use a std::set to count values, ignoring duplicates. The two recursive calls mask bits off the left (f(n&i)) and off the right (f(n/2)), eventually producing all the substrings as integers.

Note that if you want to call it again, s must be cleared between calls.

## Test program

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


## Results

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


Try it online!

# J, 15 bytes

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


Input is a binary list. Try it 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.*/)}


Test it

## Expanded:

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