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:

  11 -> 1011
  101 = 5
  011 = 3
  10  = 2
  01  = 1
  11  = 3
  1   = 1
  0   = 0
  1   = 1
  1   = 1

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
  • 5
    \$\begingroup\$ Curiously, the exclusion of the full-length substring is a significant extra challenge. \$\endgroup\$ Feb 22, 2016 at 22:30

20 Answers 20


Jelly, 10 7 bytes


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.
  • \$\begingroup\$ What encoding gives you 1 byte/char for that program? \$\endgroup\$ Feb 23, 2016 at 16:22
  • 2
    \$\begingroup\$ @TobySpeight Jelly uses its own code page. \$\endgroup\$ Feb 23, 2016 at 16:27

Pyth, 10


Try it online or run the Test Suite


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!


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

Old version:


Try it online.


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:


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):
    return result

Hope this helps.

  • \$\begingroup\$ 98 bytes using a format string and removing the list comprehension \$\endgroup\$
    – movatica
    Feb 18 at 18:07
  • \$\begingroup\$ 96 bytes as a function \$\endgroup\$
    – movatica
    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.


Online demo


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


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


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


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.


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

Mathematica, 73 70 bytes


Function. Integer->Integer

  • 1
    \$\begingroup\$ A pity mathematica doesn't have great tools for dealing with sublists. \$\endgroup\$
    – A Simmons
    Feb 22, 2016 at 18:33

Brachylog, 17 12 bytes

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


Try it online!


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

ḃ             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

Retina, 64



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]
1   -->  X0110[6], r=0+5+2+1=8
 0  -->  XX110[6], r=8+4=12
  1 -->  XXX10[2], r=12+4=16
   1 ->  XXXX0[X], r=16+1=17
  • \$\begingroup\$ 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". \$\endgroup\$
    – DW.com
    Feb 24, 2016 at 12:08

Vyxal 3 s, 6 bytes


Try it Online!

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

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

The n is only necessary because ã includes the original string.

It should be 5 bytes:


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.


Python 3, 96 bytes

def f(n):N=f"{n:b}";L=len(N);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.


PARI/GP, 72 bytes

72 bytes, it can be golfed more.


Attempt This Online!


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)

JavaScript (Node.js), 52 bytes


Try it online!


Uiua SBCS, 17 bytes


Try it!


PowerShell v2+, 138 Bytes


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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