count ones in range

Question

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 code-golf so shortest code in bytes for each language wins.

Answer 1

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

Answer 2

Python 2, 47 bytes

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

Try it online!

Answer 3

Java (JDK 10), 55 bytes

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

Try it online!

Answer 4

05AB1E, 4 bytes

ŸbSO

Try it online!

Answer 5

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)

Answer 6

Python 2, 45 bytes

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

Try it online!

Answer 7

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.

Answer 8

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.

Answer 9

Python 3, 56 54 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!

Answer 10

Pyth, 8 7 bytes

1 byte thanks to Mr. Xcoder.

ssjR2}F

Try it online!

Answer 11

APL (Dyalog Unicode), 16 bytes

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

Try it online!

-1 thanks to H.PWiz.

Left argument = min
Right argument = max

Answer 12

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

Answer 13

Stax, 6 bytes

çy╠Ƽ☻

Run and debug it

Answer 14

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

Answer 15

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

Answer 16

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.

Answer 17

Husk, 4 bytes

Σṁḋ…

Try it online!

Explanation

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

Answer 18

Pari/GP, 31 bytes

Saved one byte thanks to Mr. Xcoder.

a->b->sum(i=a,b,sumdigits(i,2))

Try it online!

Answer 19

Japt -x, 10 8 7 bytes

òV ®¤è1

Try it online!

Answer 20

Proton, 40 37 bytes

x=>y=>str(map(bin,x..y+1)).count("1")

Try it online!

Answer 21

Ruby, 38 bytes

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

Try it online!

Answer 22

Japt -x, 8 7 bytes

Takes input as an array of 2 integers.

rõ ®¤¬x

Try it

---

Explanation

rõ          :Reduce by inclusive range
   ®        :Map
    ¤       :  Convert to binary string
     ¬      :  Split
      x     :  Reduce by addition
            :Implicitly reduce by addition and output

Answer 23

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[0],$argv[1]))),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[0],$argv[1])   //generate a range between the arguments
     )
),1);   //count "1"'s

Answer 24

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

Answer 25

PowerShell, 72 bytes

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.

Answer 26

Haskell, 42 bytes

import Data.Bits
a%b=sum$popCount<$>[a..b]

Try it online!

Answer 27

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 +)

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

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!

Answer 32

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

Answer 33

QBasic, 95 93 83 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:

Answer 34

APL (Dyalog Extended), 6 bytes^SBCS

≢⍤⍸⍤⊤…

Try it online!

 ≢ tally

⍤ of

 ⍸ where true

⍤ in

 ⊤ the binary representation of

… the range

Answer 35

6510 machine code, 29 28 bytes

sub routine;
takes input from A (lower bound) and X (upper bound) registers;
returns result in A (MSB) and Y (LSB)

machine code:

85 02 A0 00 84 FC E8 CA
E4 02 30 OD 8A F0 F8 46
90 FB E8 90 F8 E6 FC D0
F4 A5 FC 60

source code:

        STA $02     store lower bound in $02
        LDY #0      init result to 0 (Y = LSB, $FC=MSB)
        STY $FC
        INX         increment upper bound
LOOP1:  DEX         decrement upper bound
        CPX $02     compare to lower bound
        BMI :FINISH if smaller, return
        TXA         copy X to A
LOOP2:  BEQ :LOOP1  if 0, next outer loop
        LSR         shift right
        BCC :LOOP2  if carry is clear, next inner loop
        INY         else increment result
        BCC :LOOP2
        INC $FC
        BNE :LOOP2  next inner loop
FINISH: LDA $FC
        RTS

notes

• With only 8 bit input possible, the maximum number of set bits is 1024; so incrementing the MSB (INC $FC) always has a non-zero result; hence BNE :LOOP always branches.
• BEQ following that BNE never branches, even not if the accumulator is zero (so I could actually add two to the BEQ parameter and save one cycle); but that doesn´t matter: LSR will clear the carry and set the zero flag, BCC will hop to LOOP2 and the BEQ to LOOP1.
• I´m not completely sure (it´s been so long I actually coded on the C64), but it may fail if the range is larger than 127: CPX $02 is actually a substraction; if the result is >127, the negative flag may be set, so BMI would end the routine.
• I hope I got the branching parameters correct - I assembled the machine code manually.

Answer 36

Retina 0.8.2, 43 bytes

\d+
$*
M!&`(?<=^(1+),.*)\1.*
+`(1+)\1
$1x
1

Try it online!

Answer 37

RProgN 2, 10 bytes

R²2Br.`0-L

Try it online!

Answer 38

C (GCC), 49 bytes

This function takes lower (a) and upper (b) bounds. Output is either through global c or by return value (if your ABI uses the same register from accumulating and function return).

c;f(a,b){for(c=b-a?f(a+1,b):0;a;a/=2)c+=a&1;a=c;}

Try It Online (output by return value)

Acknowledgments

• -5 bytes thanks to GPS
• -1 byte thanks to ceilingcat

Answer 39

Javascript ES6, 78 bytes

With currying syntax

x=>y=>[...Array(y-x+1)].map((e,i)=>(i+x).toString`2`).join``.split`1`.length-1

Answer 40

Red, 82 bytes

func[a b][s: 0 until[n: a until[if n % 2 = 1[s: s + 1]1 > n: n / 2]b < a: a + 1]s]

Try it online!

Answer 41

F#, 80 bytes

let c s e=Seq.sumBy(fun x->seq{for i=0 to 31 do yield x>>>i&&&1}|>Seq.sum){s..e}

Try it online!

For each number x in the range, shift the number by i bytes, AND it with 1, and add that to the sum for that number. Finally add all the shifting results for each number and return it.

It does the shift 32 times, since the starting and ending numbers are of type int32.

Answer 42

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

Answer 43

sed 4.2.2, 59

:
s/\b(1+) (11\1)/\1 1\1 \2/
t
:a
s/(1+)\1/\10/
ta
s/0| //g

Try it online!

Input and output as unary. Input is two space-separated unary integers.

The TIO has a footer line to convert to decimal, as a convenience.

The 1000, 2000 testcase takes too long - TIO times out after 1 minute.

Answer 44

Tcl, 80 bytes

proc P a\ b {while \$a<=$b {incr c [regexp -all 1 [format %b $a]]
incr a}
set c}

Try it online!

Answer 45

Julia 0.6, 28 bytes

(a,b)->sum(count_ones.(a:b))

Try it online!

---

If input can be sent in in the form of a range (i.e. c(4:7) instead of c(4,7)), that saves 6 bytes:

Julia 0.6, 22 bytes

r->sum(count_ones.(r))

Try it online!

Answer 46

Powershell, 59 58 bytes

param($n,$m)$n..$m|%{for(;$_){$s+=$_-band1;$_=$_-shr1}};$s

Test script:

$f = {
param($n,$m)$n..$m|%{for(;$_){$s+=$_-band1;$_=$_-shr1}};$s
}

@(
,(4,7,8)
,(10,20,27)
,(100,200,419)
,(1,3,4)
,(1,2,2)
,(1000,2000,5938)
) | % {
    $n,$m,$e=$_
    $r = &$f $n $m
    $c = $r -eq $e

    "$c : $n , $m ---> $e = $r"
}

Output:

True : 4 , 7 ---> 8 = 8
True : 10 , 20 ---> 27 = 27
True : 100 , 200 ---> 419 = 419
True : 1 , 3 ---> 4 = 4
True : 1 , 2 ---> 2 = 2
True : 1000 , 2000 ---> 5938 = 5938

Answer 47

Pyt, 3 bytes

Input is the larger number then the smaller number

ŘĦƩ

Explanation:

      Implicitly get the two numbers x and y (x<y)
Ř     Push [x,x+1,...,y]
Ħ     Get the Hamming weight of each element of the array
Ʃ     Sum the list of Hamming weights
      Implicit output

Try it online!

Answer 48

x86 machine code, 14 bytes

00000000: 31c0 f30f b8d9 01d8 4139 d17e f5c3       1.......A9.~..

Takes bottom of range in ecx, and top of range in ebx. Returns in eax.

Assembly (NASM syntax):

section .text
	global func
func:
					;1st arg = ecx, 2nd arg = edx
	xor eax, eax			;reset total
	loop:
		popcnt ebx, ecx		;get number of binary 1's in current number and store in ebx
		add eax, ebx		;add ebx to total (eax)
		inc ecx			;increase the current number (ecx) in range
		cmp ecx, edx
		jle loop		;repeat while current number (ecx) >= range max (edx)
	ret				;return the register eax

Try it online!

C code equivalent:

/*
ecx=range_start
edx=range_end
eax=total
ebx=ones_count
*/

int ones_in_range(int range_start, int range_end){
	int total = 0;
	do {
		int ones_count = __builtin_popcount(range_start);
		total += ones_count;
		range_start++;	
	} while(range_start <= range_end);
	return total;
}

Answer 49

APL(NARS), 15 chars, 30 bytes

{+/∊(⍵⍴2)⊤⍺..⍵}

test

  f←{+/∊(⍵⍴2)⊤⍺..⍵}
  1000 f 2000
5938

This seems ok even in the case 0 f 0 because +/⍬ is 0.

Answer 50

PHP, 68 bytes

The mapping variant already has been posted (though not yet in it´s mostly golfed version), so here is a looping solution:

for($i=$argv[2];$i>=$argv[1];)for($n=$i--;$n;$n>>=1)$s+=$n&1;echo$s;

Run with -nr or try it online.

Answer 51

Perl 5 -p, 39 bytes

map$\+=(sprintf'%b',$_)=~y/1//,$_..<>}{

Try it online!

Answer 52

C# (.NET Core) with LINQ, 82 bytes

(a,b)=>{int c=0;for(;a<=b;a++)c+=Convert.ToString(a,2).Count(x=>x=='1');return c;}

Try it online!

Ungolfed:

(a, b) => {                     // takes in two integer inputs, separated by a comma
    int c = 0;                  // initialize the sum variable
    for(; a <= b; a++)          // from a (inclusive) to b (exclusive)
        c +=                            // add to c:
            Convert.ToString(a, 2)          // convert a to binary
                .Count(x => x == '1');      // count the number of ones in the binary form
    return c;                   // print c after the loop
}

Answer 53

Burlesque - 12 bytes

per@b2\['1CN

pe             Parse eval
  r@           range
    b2         convert to base2
      \[       concat
        '1CN   count the `1`.

Try it online.