22
\$\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.

Improve this question
\$\endgroup\$
3
  • 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

62 Answers 62

Reset to default
1
2 3
9
\$\begingroup\$

Python 2, 47 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Clever trick to avoid >=... \$\endgroup\$
    – Erik the Outgolfer
    Jun 5, 2018 at 16:38
9
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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

05AB1E, 4 bytes

ŸbSO

Try it online!

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Exactly the solution I got :). +1. \$\endgroup\$
    – Magic Octopus Urn
    Jun 7, 2018 at 18:37
5
\$\begingroup\$

Java (JDK 10), 55 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ IntStream.range(a,b+1).map(Integer::bitCount).sum() \$\endgroup\$
    – user69125
    Jun 6, 2018 at 7:33
  • \$\begingroup\$ @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 \$\endgroup\$
    – Olivier Grégoire
    Jun 6, 2018 at 7:38
  • \$\begingroup\$ You could also have a->b->IntStream.range(a,b+1).map(Long::bitCount).sum() for a 1 byte improvement. Marginal, but still one. \$\endgroup\$
    – NotBaal
    Nov 14, 2018 at 0:00
  • \$\begingroup\$ @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). \$\endgroup\$
    – Kevin Cruijssen
    Nov 15, 2018 at 13:53
4
\$\begingroup\$

Pyth, 8 7 bytes

1 byte thanks to Mr. Xcoder.

ssjR2}F

Try it online!

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

Python 2, 45 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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)

Improve this answer
\$\endgroup\$
0
4
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$
    – Giuseppe
    Jun 5, 2018 at 17:36
  • \$\begingroup\$ @Giuseppe Indeed! \$\endgroup\$
    – JayCe
    Jun 5, 2018 at 18:14
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – ngm
    Jun 5, 2018 at 18:14
  • \$\begingroup\$ You can use pryr::f to save 4 bytes: tio.run/##K/qfZvu/… \$\endgroup\$
    – pajonk
    Jun 6, 2018 at 7:27
  • \$\begingroup\$ @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". \$\endgroup\$
    – JayCe
    Jun 6, 2018 at 20:27
3
\$\begingroup\$

Ruby, 38 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

APL (Dyalog Unicode), 16 bytes

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

Try it online!

-1 thanks to H.PWiz.

Left argument = min
Right argument = max

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Vyxal d, 2 bytes

ṡb

Try it online or see a four byte flagless version.

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Stax, 6 bytes

çy╠Ƽ☻

Run and debug it

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ try to use count instead length :) \$\endgroup\$
    – mazzy
    Jul 2, 2018 at 13:40
  • 1
    \$\begingroup\$ @mazzy count will always be 1 because we're counting the length of a string, not an array. \$\endgroup\$
    – AdmBorkBork
    Jul 2, 2018 at 13:43
  • \$\begingroup\$ string! you are right. thanks. -replace0 is smart. \$\endgroup\$
    – mazzy
    Jul 2, 2018 at 14:04
2
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)))
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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

Husk, 4 bytes

Σṁḋ…

Try it online!

Explanation

Σṁḋ…
   …     Get the (inclusive) range.
 ṁḋ      Convert each to binary and concatenate.
Σ        Get the sum.
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ it seems you can just do this \$\endgroup\$
    – dzaima
    Jun 5, 2018 at 17:07
  • \$\begingroup\$ For a second i absolutely forgot that you can set php function's name directly as a parameter :-( \$\endgroup\$
    – Francisco Hahn
    Jun 5, 2018 at 17:10
  • \$\begingroup\$ $argv[0] is the program name or "-"; You should work with $argv[1] and $argv[2]. And you can use join instead of implode, shortening this to 68 bytes: <?=substr_count(join(array_map(decbin,range($argv[1],$argv[2]))),1); \$\endgroup\$
    – Titus
    Nov 11, 2018 at 18:15
1
\$\begingroup\$

Haskell, 42 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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 +)
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Proton, 40 37 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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

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!

Improve this answer
\$\endgroup\$
1
1
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can reduce it by one byte if you use [...](@_) instead of ($^a..$^b) \$\endgroup\$
    – Brad Gilbert b2gills
    Jun 7, 2018 at 17:00
1
2 3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.