# Sum of Binary Substrings

This challenge is simple, given a decimal number, convert to binary, and calculate the sum of the sub-strings of the binary number, whose length is shorter than the original number. Here is an example:

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


Your program should take a single decimal integer as input and output the sum of the binary sub-strings, as seen above. You may assume the input will always have more than two digits in its binary representation and that in input will not cause any errors during your program's execution.

This is , shortest code in bytes wins!

Test cases:

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

• Curiously, the exclusion of the full-length substring is a significant extra challenge. Feb 22, 2016 at 22:30
• f(n) = A330072(n) - n. (Added to the OEIS almost 4 years after this challenge) May 1 at 14:53

# Jelly, 10 7 bytes

BṡRḄFS_


Try it online!

### How it works

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.

• What encoding gives you 1 byte/char for that program? Feb 23, 2016 at 16:22
• @TobySpeight Jelly uses its own code page. Feb 23, 2016 at 16:27

# Pyth, 10

sPiR2.:.BQ


Try it online or run the Test Suite

### Explanation:

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

Shoutout to Dennis for helping me save 6 bytes!

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


Works only with the newest version of CJam (available on TIO). Try it online!

Old version:

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


## Python 3, 111 characters

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: Explanation:

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


Convert input string to an int, then the int to a binary string and remove its first two characters, since the bin method returns a string in the format of 0b...

Take all substrings of the binary string, convert them to decimal using int(n, 2) and sum them.

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


is a list of all substrings. 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


Hope this helps.

• 98 bytes using a format string and removing the list comprehension Feb 18 at 18:07
• 96 bytes as a function Feb 18 at 18:11

## CJam (22 bytes)

This is one byte longer than the current best CJam answer, but the approach can probably be adapted to some other languages quite profitably.

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


Online demo

### Analysis

Suppose that the question were

calculate the sum of the sub-strings of the binary number

without the bit

whose length is shorter than the original number

Then it's not too hard to show that the most significant bit occurs with total weight 1*(2^B-1) where B is the number of bits; the second-most significant bit occurs with total weight 2*(2^(B-1)-1); down to the Bth-most significant bit, which occurs with total weight B*(2^1-1).

Taking into account now the subtraction of the original number, x, we end up with the sum

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


### Dissection

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


The conversion to base 2 gives the first part of the main sum plus x; to base 1 gives the second part plus x; and to base 0 gives just x, so subtracting the base-1 from the base-2 the xs cancel, and subtracting the base-0 gives the desired result.

## JavaScript (ES6), 78 bytes

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


The outer map builds up leading substrings of n's binary representation; the inner one extracts trailing substrings of the leading substrings, thus covering all possible substrings, including the original binary representation.

Each substring is converted from binary back to decimal and subtracted from the original input as this is slightly shorter than adding them together and subtracting the original input.

# Perl 5-p, 53 bytes

$\=-$_;$_=sprintf'%b',$_;/.*(?{$\+=oct"0b$&"})(?!)/}{


Try it online!

-p          # <cli> Read input and output result automatically
$\=-$_;     # This method will count the full length entry, need to offset that
$_=sprintf'%b',$_; # Convert input to a binary string
/                  # Pattern match
.*                # Any number of characters
(?{              # Execute code, within this pattern match
$\+= # Add to the result oct"0b$&"       # What has been matched, converted to decimal
})
(?!)              # Look ahead, do not match anything
/
}{                 # Close the implicit loop, suppressing output of $_, but outputting$\


The key part is the (?!) in the pattern match. It forces the match to fail, causing the system to backtrack and try again. However, the code block within the match has already executed before this check, so the candidate match will be added to our total.

# Mathematica, 73 70 bytes

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


Function. Integer->Integer

• A pity mathematica doesn't have great tools for dealing with sublists. Feb 22, 2016 at 18:33

# Brachylog, 17 12 bytes

-5 bytes thanks to a tip from Unrelated String in chat

ḃ{scẹ~ḃℕ}ᶠb+


Try it online!

### Explanation

Unfortunately, ḃ doesn't work very conveniently when reversed, and we have to spend three bytes working around its quirks.

ḃ{scẹ~ḃℕ}ᶠb+
ḃ             Convert to list of binary digits
{      }ᶠ    Find every way of satisfying this predicate:
s             Get a continuous sublist of digits
c            Concatenate into a number (getting rid of leading 0s)
ẹ           Convert back to a list of digits
~ḃ         Convert from binary back to decimal
But this also gives negative results, so...
ℕ        Assert that the result is a nonnegative integer
b   Behead, removing the first result, which is the original number
+  Sum


# C, 71 68 bytes

Thanks to ceilingcat for 5 byte reduction.

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


We maintain an accumulator a and mask m. The mask starts at 1 and gets one bit longer each time around the outer loop. In the inner loop, a copy i of the input is successively shifted right until it is shorter than the mask, accumulating the masked value each time.

### Test program

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


    ./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  # Retina, 64 .*$*
+(1+)\1
$1a a1 1 r&!M.* &!M.* ^.* +1(a*)\b a$.1$*1; ;  Try it online! A high level stage by stage description: convert decimal to unary, unary to binary, get prefixes, get suffixes of prefixes, dump the original number, convert binary to unary, return count. I'll write a more detailed description once I'm done golfing, a lot of these stages seem suspicious... C#, 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;}  Or, if I add Import "using static System.Math;" then 138 with 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 languages like C# won't win such a race, but I wanted to try it anyway. Here is a more beautified 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);
}
// 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;
}
}


The nested do-while adds the right-shifted value of iTemp (after assigning it) as long as shift+1 is smaller then pos. The next line calculates the next shifted value of 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 calculate the mask, x3 applies it and then left-shifts it, since the last digit is always dropped. For 11, it looks like this:

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

• I know, most answers in C work seamless in C# as well (@Tony-Speight worked without problems), but I that would defy the purpose. Also, I didn't looked at the comments (well, except the Bold headers) until I was finished myself, so there was no danger of doing it "like C". Feb 24, 2016 at 12:08

# Vyxal 3s, 6 bytes

bṢḶṪᵛB


Try it Online!

• 6 bytes flagless (roughly ports my Japt) by subtracting the input from the sum rather than removing it from the sublist array Feb 14 at 1:25

# PARI/GP, 72 bytes

72 bytes, it can be golfed more.

f(n)=sum(i=1,(#b=binary(n))-1,sum(j=1,#b-i+1,fromdigits(b[j..j+i-1],2)))


Attempt This Online!

# Scala 2, 156147 140 bytes

A port of @DW.com's C# answer in Scala.

Saved 16 bytes thanks to @ceilingcat

Golfed version. Attempt This Online!

i=>{var p=Integer.toBinaryString(i).size;var r=0;var P=i;do{var s=0;var z=P;do{z/=2;r+=z;s+=1;}while(s<p);P=i+i&(1<<p)-2;p-=1}while(-1<p);r}


Ungolfed version. Attempt This Online!

object Main {
def main(args: Array[String]): Unit = {
var i = 2
do {
println(s"$i ->${x(i)}")
i += 1
} while (i < 12)
}

def x(iOrg: Int): Int = {
var pos = Integer.toBinaryString(iOrg).length
var shift = 0
var retVal = 0
var iPrev = iOrg
var iTemp = 0

do {
iTemp = iPrev
shift = 0
do {
iTemp >>= 1
retVal += iTemp
shift += 1
} while (shift < pos)
iPrev = (iOrg & ((1 << pos - 1) - 1)) << 1
pos -= 1
} while (pos > -1)
retVal
}
}


# JavaScript (Node.js), 52 bytes

f=x=>x&&g(x,i=1)+f(x>>=1)+x
g=x=>x&-i&&x%i+g(x,i*=2)


Try it online!

# UiuaSBCS, 17 bytes

/+/◇⊂⍚°⋯⍚◫↘1⇡⊃⧻¤⋯


Try it!

# Japt, 7 6 bytes

n¢ã xÍ


Try it

n¢ã xÍ
n        The input subtracted from:
¢         The input as a binary string
ã        Substrings, including the original string
x      Sum this list after mapping each substring to:
Í       It converted to decimal


It should be 5 bytes:

n¢ãÍx


As according to the docs, when passed a function f, ã “returns all substrings of S after passing each through f.” But there's a bug in the interpreter, and Japt isn't maintained anymore, so 6 bytes it is.

Also, the n is only necessary because ã includes the original string.

# Python 3.8 (pre-release), 95 bytes

def f(n):L=len(N:=f"{n:b}");r=range;return sum(int(N[i:i+l],2)for l in r(1,L)for i in r(L-l+1))


Try it online!

# Go, 143 bytes

import."fmt"
func f(n int)(o int){s:=Sprintf("%b",n)
for i,L:=0,len(s);i<L;i++{for j,e:=i,0;j<L;j++{Sscanf(s[i:j+1],"%b",&e)
o+=e}}
return o-n}


Attempt This Online!

# Go 1.21+, 142 bytes

import."fmt"
func f(n int)(o int){s:=Sprintf("%b",n)
L:=len(s)
for i:=range L{for j,e:=i,0;j<L;j++{Sscanf(s[i:j+1],"%b",&e)
o+=e}}
return o-n}


You Cannot Attempt This Online!

Run on the Go Playground!

This solution has -1 byte from using the new range-over-int loop.

# Ruby, 152 bytes

152 bytes, it can be golfed more.

Golfed version. Attempt This Online!

def x(i)
p=i.to_s(2).length
s=r=0
l=i
while p>-1
t=l
s=0
while s<p
t>>=1
r+=t
s+=1
end
l=(i&((1<<(p-1))-1))<<1
p-=1
end
r
end


Ungolfed version. Attempt This Online!

def x(i_org)
pos = i_org.to_s(2).length
shift = 0
ret_val = 0
i_prev = i_org
i_temp = 0

while pos > -1
i_temp = i_prev
shift = 0
while shift < pos
i_temp >>= 1
ret_val += i_temp
shift += 1
end
i_prev = (i_org & ((1 << (pos - 1)) - 1)) << 1
pos -= 1
end

ret_val
end

i = 2
begin
puts "#{i} -> #{x(i)}"
i += 1
end while i < 12


## 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. That conversion to/from binary is expensive.

Takes input $a, then uses the .NET call [convert]::ToString($a,2) to turn it into the binary representation. From there, we go through two loops -- the first counts backwards from the end of the string down to 1, and the second counts upward from 0. (The first is how long of a substring to pull out, and the second is the index of where in the string to start the substring.) We set a helper \$l along the way to pass that through to the inner loop.

Inside the inner loop, we use another .NET call [convert]::ToInt32() to convert the appropriate .substring() from base 2 into an integer. Each of those is then left on the pipeline. We encapsulate all of that with parens () and -join them together with a +, then toss that off to iex (short for Invoke-Expression and similar-ish to eval).

I think this technically requires v2 or newer to properly call the .NET calls.