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

Mathematica, 73 70 bytes

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

Function. Integer->Integer

Answer 8

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 9

C, 71 bytes

f(n){int a=0,m=0,i;for(;++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 10

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 11

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