Sum of Binary Substrings

Question

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 code-golf, 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

Answer 1

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.

Answer 2

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

Answer 3

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_:+

Try it online.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

Mathematica, 73 70 bytes

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

Function. Integer->Integer

Answer 9

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

Answer 10

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

Test output

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

Answer 11

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

Answer 12

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

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

Answer 13

Vyxal 3 s, 6 bytes

bṢḶṪᵛB

Try it Online!

Answer 14

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!

Answer 15

Scala 2, 156 147 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)
    scala.io.StdIn.readLine() // to mimic System.Console.Read() for pausing
  }

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

Answer 16

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!

Answer 17

Uiua ^SBCS, 17 bytes

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

Try it!

Answer 18

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.

Answer 19

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!

Improved version of shooqies answer.

Answer 20

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.

Answer 21

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

Answer 22

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