# 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 – Leaky Nun Jun 5 '18 at 15:50
• May we take the input as some kind of range type (IntRange in Kotlin, Range in Ruby)? – snail_ 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 – steenbergh Nov 16 '18 at 13:00

# 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


# 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 >=... – Erik the Outgolfer Jun 5 '18 at 16:38

# 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() – saka1029 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 – Olivier Grégoire 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. – NotBaal 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). – Kevin Cruijssen Nov 15 '18 at 13:53

# 05AB1E, 4 bytes

ŸbSO


Try it online!

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

# 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. – Giuseppe Jun 5 '18 at 17:36
• @Giuseppe Indeed! – JayCe 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/… – pajonk 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". – JayCe Jun 6 '18 at 20:27

# 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 ? – Muhammad Salman Jun 5 '18 at 15:27
• @MuhammadSalman Well, the challenge is also kind of trivial IMO. – Mr. Xcoder Jun 5 '18 at 15:28
• It may be, but an answer a minute after posting. – Muhammad Salman 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. ;-) – Erik the Outgolfer Jun 5 '18 at 15:46
• @EriktheOutgolfer : Can you answer this in QBasic / BrainF**k ? – Muhammad Salman Jun 5 '18 at 15:46

# Pyth, 8 7 bytes

1 byte thanks to Mr. Xcoder.

ssjR2}F


Try it online!

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

# 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 :) – mazzy Jul 2 '18 at 13:40 • @mazzy count will always be 1 because we're counting the length of a string, not an array. – AdmBorkBork Jul 2 '18 at 13:43 • string! you are right. thanks. -replace0 is smart. – mazzy 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  # 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  # 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) – Brad Gilbert b2gills 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? – FrownyFrog Jun 7 '18 at 9:31
• @FrownyFrog I'll try later today (apparently it's possible, since you are asking :) ) – Galen Ivanov Jun 7 '18 at 10:11
• @FrownyFrog 15 for now, I'm still trying... – Galen Ivanov Jun 7 '18 at 14:28
• 14 – FrownyFrog 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! – Galen Ivanov Jun 8 '18 at 6:51

# QBasic, 959383 82 bytes

@DLosc saved me some a lot of bytes!

Saved another byte using this technique!

INPUT a,b
FOR i=a TO b
k=i
FOR j=i TO 0STEP-1
x=k>=2^j
s=s-x
k=k+x*2^j
NEXT j,i
?s


Language of the Month FTW!

Explanation

INPUT a,b           Ask user for lower and upper bound
FOR i=a TO b        Loop through that range
k=i                 we need a copy of i to not break the FOR loop
FOR j=i TO 0STEP-1  We're gonna loop through exponents of 2 from high to low.
Setting the first test up for 4 to 2^4 (etc) we know we're overshooting, but that 's OK
x=k>=2^j            Test if the current power of 2 is equal to or smaller than k
(yields 0 for false and -1 for true)
s=s-x               If k is bigger than 2^j, we found a 1, so add 1 to our running total s
(or sub -1 from the total s...)
k=k+x*2^j           Lower k by that factor of 2 if the test is true, else by 0
NEXT                Test the next exponent of 2
NEXT                process the next number in range
?s                  print the total


Last testcase of 1000 to 2000 actually works, in QBasic 4.5 running on Dosbox: