# Challenge :

Count the number of ones 1 in the binary representation of all number between a range.

# Input :

Two non-decimal positive integers

# Output :

The sum of all the 1s in the range between the two numbers.

# Example :

4 , 7        ---> 8
4  = 100 (adds one)   = 1
5  = 101 (adds two)   = 3
6  = 110 (adds two)   = 5
7  = 111 (adds three) = 8

10 , 20     ---> 27
100 , 200   ---> 419
1 , 3       ---> 4
1 , 2       ---> 2
1000, 2000  ---> 5938


I have only explained the first example otherwise it would have taken up a huge amount of space if I tried to explain for all of them.

# Note :

• Numbers can be apart by over a 1000
• All input will be valid.
• The minimum output will be one.
• You can accept number as an array of two elements.
• You can choose how the numbers are ordered.

# Winning criteria :

This is so shortest code in bytes for each language wins.

• OEIS A000788 Jun 5, 2018 at 15:50
• May we take the input as some kind of range type (IntRange in Kotlin, Range in Ruby)? Jun 6, 2018 at 4:03
• Fun fact: case 1000 - 2000 yields 5938, but lower the case by 1000, the result also drops by 1000: 0-1000 = 4938. Proof Nov 16, 2018 at 13:00

# Python 2, 47 bytes

f=lambda x,y:y/x and bin(x).count('1')+f(x+1,y)


Try it online!

• Clever trick to avoid >=... Jun 5, 2018 at 16:38

# JavaScript (ES6), 38 bytes

Takes input in currying syntax (a)(b).

a=>b=>(g=c=>a>b?0:1+g(c^c&-c||++a))(a)


Try it online!

### Commented

a => b => (         // given the input values a and b
g = c =>          // g = recursive function taking c = current value
a > b ?         // if a is greater than b:
0             //   stop recursion and return 0
:               // else:
1 +           //   add 1 to the final result
g(            //   and do a recursive call to g() with:
c ^ c & -c  //     the current value with the least significant bit thrown away
|| ++a      //     or the next value in the range if the above result is 0
)             //   end of recursive call
)(a)                // initial call to g() with c = a


# Jelly, 4 bytes

rBFS


Try it online!

### Explanation

rBFS – Full program. Takes the two inputs from the commands line arguments.
r    – Range.
B   – For each, convert to binary.
FS – Flatten and sum.

• O_o , that was fast ? Jun 5, 2018 at 15:27
• @MuhammadSalman Well, the challenge is also kind of trivial IMO. Jun 5, 2018 at 15:28
• It may be, but an answer a minute after posting. Jun 5, 2018 at 15:30
• @MuhammadSalman Yes, that's not really that fast for trivial challenges like this one; knowledge of Jelly also ensues. The real effort goes in e.g. the language of this month, QBasic. ;-) Jun 5, 2018 at 15:46
• @EriktheOutgolfer : Can you answer this in QBasic / BrainF**k ? Jun 5, 2018 at 15:46

# 05AB1E, 4 bytes

ŸbSO


Try it online!

• Exactly the solution I got :). +1. Jun 7, 2018 at 18:37

# Java (JDK 10), 55 bytes

a->b->{int c=0;for(;a<=b;)c+=a.bitCount(b--);return c;}


Try it online!

• IntStream.range(a,b+1).map(Integer::bitCount).sum()
– user69125
Jun 6, 2018 at 7:33
• @saka1029 The imports are mandatory. So it's actually a->b->java.util.stream.IntStream.range(a,b+1).map(Integer::bitCount).sum(), for a whole 74 bytes. Even if the the import wasn't mandatory, the parameters are, so we'd have to write a->b->IntStream.range(a,b+1).map(Integer::bitCount).sum(), which counts as 57 bytes Jun 6, 2018 at 7:38
• You could also have a->b->IntStream.range(a,b+1).map(Long::bitCount).sum() for a 1 byte improvement. Marginal, but still one. Nov 14, 2018 at 0:00
• @NotBaal As mentioned by Olivier in the comment above, imports are mandatory, so it should be a->b->java.util.stream.IntStream.range(a,b+1).map(Long::bitCount).sum() (71 bytes). Nov 15, 2018 at 13:53

# Pyth, 8 7 bytes

1 byte thanks to Mr. Xcoder.

ssjR2}F


Try it online!

# Python 2, 45 bytes

lambda x,y:map(bin,range(x,y+1)).count('1')


Try it online!

# MATL, 5 4 bytes

&:Bz


Try it online!

Thanks to Luis Mendo for saving a byte!

(implicit input a and b, a<b)
&:                              % two-element input range, construct [a..b]
B                             % convert to Binary as a logical vector (matrix)
z                            % number of nonzero entries
(implicit output of the result)

# R, 41 34 bytes

function(a,b)sum(intToBits(a:b)>0)


Try it online!

Heavily inspired by the other R solution by ngm. This uses a different approach after the conversion to bits. Huge thanks to Giuseppe for hinting at a possible 34 bytes solution.

• 34 bytes is possible! I forget where I saw the trick (I know I didn't come up with it) but there's a trickier conversion to a summable vector -- I'll post if you/ngm can't find it. Jun 5, 2018 at 17:36
• @Giuseppe Indeed! Jun 5, 2018 at 18:14
• I got it down to 37 bytes using a technique that might otherwise be useful. Also discovered that sd and var coerce anything they can to double.
– ngm
Jun 5, 2018 at 18:14
• You can use pryr::f to save 4 bytes: tio.run/##K/qfZvu/… Jun 6, 2018 at 7:27
• @pajonk good point! But I'm trying to stick to the base R packages rather than R+pryr. I'm going to search on meta what can be considered "pure R". Jun 6, 2018 at 20:27

# Ruby, 38 bytes

->a,b{("%b"*(b-a+1)%[*a..b]).count ?1}


Try it online!

# APL (Dyalog Unicode), 16 bytes

{≢⍸(⍵⍴2)⊤⍺↓0,⍳⍵}


Try it online!

-1 thanks to H.PWiz.

Left argument = min
Right argument = max

# Octave with Communication toolbox, 21 bytes

@(a,b)nnz(de2bi(a:b))


Try it online!

The code should be fairly obvious. Number of nonzero elements in the binary representation of each of the numbers in the range.

This would be @(a,b)nnz(dec2bin(a:b)-48) without the communication toolbox.

# Python 3, 5654 52 bytes

This can be golfed more imo. -2 Bytes thanks to Mr.Xcoder -2 More bytes thanks to M. I. Wright

lambda a,b:''.join(map(bin,range(a,b+1))).count('1')


Try it online!

# Vyxald, 2 bytes

ṡb


Gets the range between the two inputs, converts each to a list of 1s and 0s, then deep flattens and sums with the d flag.

# Stax, 6 bytes

çy╠Æ¼☻


Run and debug it

param($x,$y)$x..$y|%{$o+=([convert]::ToString($_,2)-replace0).length};$o  Try it online! Long because of the conversion to binary [convert]::ToString($_,2) and getting rid of the zeros -replace0. Otherwise we just take the input numbers, make a range $x..$y and for each number in the range convert it to binary, remove the zeros, take the .length thereof (i.e., the number of ones remaining), and add it to our $output. • try to use count instead length :) Jul 2, 2018 at 13:40 • @mazzy count will always be 1 because we're counting the length of a string, not an array. Jul 2, 2018 at 13:43 • string! you are right. thanks. -replace0 is smart. Jul 2, 2018 at 14:04 # Bash + common utilities, 50 jot -w%o -$@|tr 247356 1132|fold -1|paste -sd+|bc


Try it online!

Converting integers to binary strings is always a bit of pain in bash. The approach here is slightly different - convert the integers to octal, then replace each octal digit with the number of binary 1s it contains. Then we can just sum all converted digits

# APL+WIN, 33 26 bytes

Prompts for vector of integers:

+/,((↑v)⍴2)⊤(1↓v)+0,⍳-/v←⎕


Try it online! Courtesy of Dalog Classic

Explanation:

v←⎕ prompt for input of a vector of two integers max first

(v←1↓v)+0,⍳-/ create a vector of integers from min to max

(↑v)⍴2 set max power of 2 to max

⊤ convert integers to a matrix of binaries

+/, convert matrix to a vector and sum


# R, 44 40 37 bytes

function(a,b)sum(c(0,intToBits(a:b)))


Try it online!

Previously:

function(a,b)sum(strtoi(intToBits(a:b)))
function(a,b)sum(as.integer(intToBits(a:b)))


# Brachylog, 8 bytes

⟦₂ḃᵐcọht


Try it online!

### Explanation

⟦₂         Ascending range between the two elements in the input
ḃᵐ       Map to base 2
c      Concatenate
ọ     Occurrences of each element
h    Head: take the list [1, <number of occurrences of 1>]
t   Tail: the number of occurrences of 1


# Forth (gforth), 69 bytes

: f 1+ 0 -rot swap do i begin 2 /mod -rot + swap ?dup 0= until loop ;


Try it online!

### Explanation

The basic algorithm is to loop over every number in range, and sum the binary digits (divide by two, add remainder to sum, repeat until number is 0)

### Code Explanation

1+                   \ add one to the higher number to make it inclusive
0 -rot swap          \ create a sum value of 0 and put loop parameters in high low order
do                   \ start a loop over the range provided
i                  \ place the index on the stack
begin              \ start an indefinite loop
2 /mod           \ get the quotient and remainder of dividing by 2
-rot             \ move the quotient to the back
+ swap           \ add the remainder to the sum and move it down the stack
?dup             \ duplicate the quotient unless it equals 0
0=               \ check if it equals 0
until              \ if it does equal 0, end the inner loop
loop                 \ end the outer loop


# Husk, 4 bytes

Σṁḋ…


Try it online!

### Explanation

Σṁḋ…
…     Get the (inclusive) range.
ṁḋ      Convert each to binary and concatenate.
Σ        Get the sum.


## PHP, 97 Bytes

(sure this can be shortened, but wanted to use the functions)

Try it online

Code

<?=substr_count(implode(array_map(function($v){return decbin($v);},
range($argv,$argv))),1);


Explanation

<?=
substr_count(   //Implode the array and count every "1"
implode(
array_map(function($v){return decbin($v);}, //Transform every decimal to bin
range($argv,$argv)   //generate a range between the arguments
)
),1);   //count "1"'s

• it seems you can just do this Jun 5, 2018 at 17:07
• For a second i absolutely forgot that you can set php function's name directly as a parameter :-( Jun 5, 2018 at 17:10
• $argv is the program name or "-"; You should work with $argv and $argv. And you can use join instead of implode, shortening this to 68 bytes: <?=substr_count(join(array_map(decbin,range($argv,$argv))),1); Nov 11, 2018 at 18:15 # Haskell, 42 bytes import Data.Bits a%b=sum$popCount<$>[a..b]  Try it online! # Pip, 10 bytes $+JTB:a\,b


Try it online!

### Explanation

            a and b are command-line args (implicit)
a\,b  Inclusive range from a to b
TB:      Convert to binary (: forces TB's precedence down)
J         Join into a single string of 1's and 0's
$+ Sum (fold on +)  # Proton, 40 37 bytes x=>y=>str(map(bin,x..y+1)).count("1")  Try it online! # Charcoal, 10 bytes ＩΣ⭆…·ＮＮ⍘ι²  Try it online! Link is to verbose version of code. Explanation:  ＮＮ Input numbers …· Inclusive range ⭆ Map over range and join ι Current value ² Literal 2 ⍘ Convert to base as string Σ Sum of digits Ｉ Cast to string Implicitly print  # Bash + coreutils, 38 32 bytes seq -f2o%.fn$*|dc|tr -d 0|wc -c


Thanks to @Cowsquack for golfing off 6 bytes!

Try it online!

# K (ngn/k), 19 13 bytes

{+//2\x_!1+y}


Try it online!

{ } is a function with arguments x and y

!1+y is the list 0 1 ... y

x_ drops the first x elements

2\ encodes each int as a list of binary digits of the same length (this is specific to ngn/k)

+/ sum

+// sum until convergence; in this case sum of the sum of all binary digit lists

# Perl 6, 32 30 bytes

-1 bytes thanks to Brad Gillbert

{[…](@_)>>.base(2).comb.sum}


Try it online!

Explanation:

[…](@_)    #Range of parameter 1 to parameter 2
>>    #Map each number to
.sum  #The sum of
.comb      #The string of
.base(2)    #The binary form of the number

• You can reduce it by one byte if you use [...](@_) instead of ($^a..$^b) Jun 7, 2018 at 17:00