# 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 '18 at 15:50
• May we take the input as some kind of range type (IntRange in Kotlin, Range in Ruby)? Jun 6 '18 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 '18 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 '18 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 '18 at 15:27
• @MuhammadSalman Well, the challenge is also kind of trivial IMO. Jun 5 '18 at 15:28
• It may be, but an answer a minute after posting. Jun 5 '18 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 '18 at 15:46
• @EriktheOutgolfer : Can you answer this in QBasic / BrainF**k ? Jun 5 '18 at 15:46

# 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 '18 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 '18 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 '18 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 '18 at 13:53

# 05AB1E, 4 bytes

ŸbSO


Try it online!

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

# 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 '18 at 17:36
• @Giuseppe Indeed! Jun 5 '18 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 '18 at 18:14
• You can use pryr::f to save 4 bytes: tio.run/##K/qfZvu/… Jun 6 '18 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 '18 at 20:27

# APL (Dyalog Unicode), 16 bytes

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


Try it online!

-1 thanks to H.PWiz.

Left argument = min
Right argument = max

# 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!

# Ruby, 38 bytes

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


Try it online!

# 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 '18 at 13:40 • @mazzy count will always be 1 because we're counting the length of a string, not an array. Jul 2 '18 at 13:43 • string! you are right. thanks. -replace0 is smart. Jul 2 '18 at 14:04 # 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  # 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  # 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 '18 at 17:00

# J, 16, 15 14 bytes

1 byte saved thanks to FrownyFrog!

+/@,@#:@}.i.,]


Try it online!

Explanation:

A dyadic verb, the left argument is the lower bound m of the range, the right one - the upper n.

            ,    append
]   n to the
i.     list 0..n-1
}.      drop m elements from the beginning of that list
#:@        and convert each element to binary
,@           and flatten the table
+/@             and find the sum

• Can you make it 14? Jun 7 '18 at 9:31
• @FrownyFrog I'll try later today (apparently it's possible, since you are asking :) ) Jun 7 '18 at 10:11
• @FrownyFrog 15 for now, I'm still trying... Jun 7 '18 at 14:28
• 14 Jun 8 '18 at 1:42
• @FrownyFrog Aah, so easy! I was thinking about }. but always in a fork and not in a hook. Thanks! Jun 8 '18 at 6:51