Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
share|improve this question
2  
Curiously, the exclusion of the full-length substring is a significant extra challenge. – Peter Taylor 22 hours ago

10 Answers 10

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.
share|improve this answer
    
What encoding gives you 1 byte/char for that program? – Toby Speight 4 hours ago
1  
@TobySpeight Jelly uses its own code page. – Aqua Tart 4 hours ago

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
share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
Welcome to Programming Puzzles and Code Golf. This is a good answer, however it could be improved by adding a code explanation and breakdown in addition to the golfed code. That way, other people can learn from your code. If you need help with anything, just reply to this comment. – wizzwizz4 yesterday
    
Added an explanation. – shooqie yesterday
3  
Added an upvote. – wizzwizz4 yesterday

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.

share|improve this answer

Mathematica, 73 bytes

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

Function. Integer->Integer

share|improve this answer
    
A pity mathematica doesn't have great tools for dealing with sublists. – A Simmons yesterday

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.

share|improve this answer

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

share|improve this answer

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
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.