23
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ OEIS A000788 \$\endgroup\$
    – Leaky Nun
    Jun 5, 2018 at 15:50
  • 1
    \$\begingroup\$ May we take the input as some kind of range type (IntRange in Kotlin, Range in Ruby)? \$\endgroup\$
    – snail_
    Jun 6, 2018 at 4:03
  • \$\begingroup\$ Fun fact: case 1000 - 2000 yields 5938, but lower the case by 1000, the result also drops by 1000: 0-1000 = 4938. Proof \$\endgroup\$
    – steenbergh
    Nov 16, 2018 at 13:00
  • \$\begingroup\$ @steenbergh Consider 0-2000 + 1000. For 0<=i<1000, pair i with (2i,2i+1), then <0-2000,1000> is 2 times <0-1000> plus 1000 extra 1's. Removing a 0-1000 is, 1000-2000 is <0-1000> + 1000 \$\endgroup\$
    – l4m2
    Mar 26 at 6:30

64 Answers 64

1
\$\begingroup\$

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

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: Hij doet het!

\$\endgroup\$
0
1
\$\begingroup\$

Pari/GP, 31 bytes

Saved one byte thanks to Mr. Xcoder.

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

Try it online!

\$\endgroup\$
0
1
\$\begingroup\$

APL (Dyalog Extended), 6 bytesSBCS

≢⍤⍸⍤⊤…

Try it online!

 tally

 of

 where true

 in

 the binary representation of

 the range

\$\endgroup\$
1
  • 1
    \$\begingroup\$ … and it looks cute too \$\endgroup\$
    – Adám
    Nov 11, 2018 at 16:44
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

Perl 5 -p, 39 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Japt -x, 10 8 7 bytes

òV ®¤è1

Try it online!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 8 bytes: òV m¤¬è1 \$\endgroup\$
    – Shaggy
    Jun 5, 2018 at 15:43
1
\$\begingroup\$

Scala, 45 44 bytes

_.to(_)flatMap(_.toBinaryString)count(49==)

Try it in Scastie

\$\endgroup\$
1
\$\begingroup\$

Thunno 2 S, 4 bytes

I2Bʂ

Attempt This Online!

Explanation

I2Bʂ  # Implicit input
I     # Inclusive range
 2B   # Convert each to binary
   ʂ  # Sum each inner list
      # Implicit output of sum
\$\endgroup\$
1
\$\begingroup\$

Rust, 54 50 btyes

Try it online!

|l:u32,h:u32|(l..=h).fold(0,|c,x|c+x.count_ones())

count_ones does the heavy lifting of counting the number of ones in each number here.

Used fold to avoid turbofish from sum.

Ungolfed:

|low: u32, high: u32| (low..=high).fold(0, |total, x| total + x.count_ones())
\$\endgroup\$
1
\$\begingroup\$

J-uby, 26 bytes

:!~|:sum+(~:digits&2|:sum)

Attempt This Online!

\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 43 bytes

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

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ 42 bytes \$\endgroup\$
    – Neil
    Jun 5, 2018 at 23:57
0
\$\begingroup\$

RProgN 2, 10 bytes

R²2Br.`0-L

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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
}
\$\endgroup\$
0
\$\begingroup\$

Burlesque - 12 bytes

per@b2\['1CN

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

Try it online.

\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
1
  • 1
    \$\begingroup\$ 50 bytes: c;f(a,b){c=b-a?f(a+1,b):0;for(;a;a/=2)c+=a&1;a=c;} \$\endgroup\$
    – GPS
    Nov 15, 2018 at 14:41
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

x86-16 machine code, 16 bytes

Binary:

00000000: 33c0 8bd1 d1e2 7301 4075 f93b cbe0 f3c3  3.....s.@u.;....

Listing:

33 C0       XOR  AX, AX         ; clear 1's counter in AX 
        INTLOOP: 
8B D1       MOV  DX, CX         ; current number into DX 
        BITLOOP: 
D1 E2       SHL  DX, 1          ; MSb into CF, ZF = ( DX == 0 )
73 01       JNC  BITZERO        ; if a zero, check ZF
40          INC  AX             ; increment counter 
        BITZERO: 
75 F9       JNZ  BITLOOP        ; if DX > 0 keep looping 
3B CB       CMP  CX, BX         ; is CX < BX? 
E0 F3       LOOPNZ INTLOOP      ; if not, decrement CX and loop 
C3          RET                 ; return to caller

Callable function, low range number in BX, high number in CX. Result in AX.

Note: There is another IA machine code submission which uses the POPCNT instruction introduced with SSE4 requiring an Intel Core or later architecture. This one will run on any 8086 or later CPU.

Test program:

enter image description here

\$\endgroup\$
0
\$\begingroup\$

Wolfram Language (Mathematica), 28 bytes

Tr@DigitCount[Range@##,2,1]&

Try it online!

\$\endgroup\$

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.