conte os que estão ao alcance

20

Desafio:

Conte o número de unidades 1na representação binária de todos os números entre um intervalo.

Entrada :

Dois inteiros positivos não decimais

Saída:

A soma de todos os 1s no intervalo entre os dois números.

Exemplo:

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

Eu expliquei apenas o primeiro exemplo, caso contrário, ele ocuparia uma quantidade enorme de espaço se tentasse explicar para todos eles.

Nota :

  • Os números podem ser separados em mais de 1000
  • Toda entrada será válida.
  • A saída mínima será uma.
  • Você pode aceitar o número como uma matriz de dois elementos.
  • Você pode escolher como os números são ordenados.

Critérios de vitória:

Este é o código-golfe, pelo que o código mais curto em bytes para cada idioma vence.

code-golf math number binary Muhammad Salman
fonte
1
OEIS A000788
Freira
1
Podemos considerar a entrada como algum tipo de faixa ( IntRangeno Kotlin, Rangeno Ruby)?
snail_
Fun fato: caso 1000 - 2000produz 5938, mas abaixar o caso em 1000, o resultado também cai em 1000: 0-1000 = 4938. Prova
steenbergh

Respostas:

9

JavaScript (ES6), 38 bytes

Recebe entrada na sintaxe de currying (a)(b).

a=>b=>(g=c=>a>b?0:1+g(c^c&-c||++a))(a)

Experimente online!

Comentado

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
Arnauld
fonte
6

Python 2 , 47 bytes

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

Experimente online!

Dennis
fonte
1
Truque inteligente para evitar >=...
Erik the Outgolfer
5

Java (JDK 10) , 55 bytes

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

Experimente online!

Olivier Grégoire
fonte
IntStream.range(a,b+1).map(Integer::bitCount).sum()
saka1029
@ saka1029 As importações são obrigatórias. Então é realmentea->b->java.util.stream.IntStream.range(a,b+1).map(Integer::bitCount).sum() , são 74 bytes inteiros. Mesmo se a importação não era obrigatória, os parâmetros são, por isso, teria que escrever a->b->IntStream.range(a,b+1).map(Integer::bitCount).sum(), que conta como 57 bytes
Olivier Grégoire
Você também pode ter a->b->IntStream.range(a,b+1).map(Long::bitCount).sum()uma melhoria de 1 byte. Marginal, mas ainda assim.
NotBaal
@ NotBaal Como mencionado por Olivier no comentário acima, as importações são obrigatórias, portanto devem ser a->b->java.util.stream.IntStream.range(a,b+1).map(Long::bitCount).sum()(71 bytes).
21718 Kevin Kurtzssen
4

05AB1E , 4 bytes

ŸbSO

Experimente online!

Mr. Xcoder
fonte
Exatamente a solução que eu tenho :). +1.
Urna de polvo mágico
4

MATL , 5 4 bytes

&:Bz

Experimente online!

Obrigado a Luis Mendo por salvar um 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)

Giuseppe
fonte
4

R , 41 34 bytes

function(a,b)sum(intToBits(a:b)>0)

Experimente online!

Fortemente inspirado pela outra solução R da ngm . Isso usa uma abordagem diferente após a conversão em bits. Muito obrigado a Giuseppe por sugerir uma solução possível de 34 bytes.

JayCe
fonte
34 bytes é possível! Eu esqueço onde vi o truque (sei que não o sumcriei ), mas há uma conversão mais complicada em um vetor mable - postarei se você / ngm não conseguir encontrá-lo.
Giuseppe
@Giuseppe Indeed!
Jayce
2
Eu reduzi para 37 bytes usando uma técnica que poderia ser útil. Também descobriram isso sde varcoagiram tudo o que podiam para dobrar.
Ng
Você pode usar pryr::fpara salvar 4 bytes: tio.run/##K/qfZvu/…
pajonk
@pajonk good point! Mas estou tentando manter os pacotes R básicos em vez de R + pryr. Vou procurar na meta o que pode ser considerado "R puro".
Jayce
3

Gelatina , 4 bytes

rBFS

Experimente online!

Explicação

rBFS - programa completo. Toma as duas entradas dos argumentos da linha de comandos.
r - alcance.
 B - Para cada, converta para binário.
  FS - Achatar e somar.
Mr. Xcoder
fonte
O_o, isso foi rápido?
Muhammad Salman
@MuhammadSalman Bem, o desafio também é uma espécie de IMO trivial.
Mr. Xcoder
Pode ser, mas uma resposta um minuto após a postagem.
Muhammad Salman
1
@MuhammadSalman Sim, isso não é realmente tão rápido para desafios triviais como este; o conhecimento de geléia também se segue. O esforço real está presente, por exemplo, no idioma deste mês, QBasic. ;-)
Erik the Outgolfer
@EriktheOutgolfer: Você pode responder isso no QBasic / BrainF ** k?
Muhammad Salman
3

Python 3 , 56 54 52 bytes

Isso pode ser jogado mais imo. -2 bytes graças ao Mr.Xcoder -2 bytes adicional graças ao MI Wright

lambda a,b:''.join(map(bin,range(a,b+1))).count('1')

Experimente online!

Bolinhos de moinho de vento
fonte
2

Bash + utilitários comuns, 50

jot -w%o - $@|tr 247356 1132|fold -1|paste -sd+|bc

Experimente online!

Converter números inteiros em seqüências binárias é sempre um pouco trabalhoso. A abordagem aqui é um pouco diferente - converta os números inteiros em octal e substitua cada dígito octal pelo número de 1s binários que ele contém. Então podemos somar todos os dígitos convertidos

Trauma Digital
fonte
2

APL + WIN, 33 26 bytes

Solicita o vetor de números inteiros:

+/,((↑v)⍴2)⊤(1↓v)+0,⍳-/v←⎕

Experimente online! Cortesia de Dalog Classic

Explicação:

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
Graham
fonte
2

R , 44 40 37 bytes

function(a,b)sum(c(0,intToBits(a:b)))

Experimente online!

Anteriormente:

function(a,b)sum(strtoi(intToBits(a:b)))
function(a,b)sum(as.integer(intToBits(a:b)))
ngm
fonte
2

Oitava com caixa de ferramentas Comunicação, 21 bytes

@(a,b)nnz(de2bi(a:b))

Experimente online!

O código deve ser bastante óbvio. Número de elementos diferentes de zero na representação binária de cada um dos números no intervalo.

Isso seria @(a,b)nnz(dec2bin(a:b)-48)sem a caixa de ferramentas de comunicação.

Stewie Griffin
fonte
1

Casca , 4 bytes

Σṁḋ…

Experimente online!

Explicação

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

fonte
1

PHP, 97 bytes

(com certeza isso pode ser reduzido, mas você deseja usar as funções)

Experimente online

Código

<?=substr_count(implode(array_map(function($v){return decbin($v);},
 range($argv[0],$argv[1]))),1);

Explicação

<?=
 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
Francisco Hahn
fonte
parece que você só pode fazer isso
dzaima
Por um segundo eu absolutamente se esqueceu de que você pode definir o nome de função php diretamente como um parâmetro :-(
Francisco Hahn
$argv[0]é o nome do programa ou "-"; Você deve trabalhar com $argv[1]e $argv[2]. E você pode usar em joinvez de implodereduzi-lo para 68 bytes:<?=substr_count(join(array_map(decbin,range($argv[1],$argv[2]))),1);
Titus
1

PowerShell , 72 bytes

param($x,$y)$x..$y|%{$o+=([convert]::ToString($_,2)-replace0).length};$o

Experimente online!

Longo por causa da conversão para binário [convert]::ToString($_,2)e se livrar dos zeros -replace0. Caso contrário, apenas pegamos os números de entrada, fazemos um intervalo $x..$ye, para cada número no intervalo, o convertemos em binário, removemos os zeros, pegamos o .lengthmesmo (ou seja, o número restante) e o adicionamos ao nosso $oresultado.

AdmBorkBork
fonte
try to use count instead length :)
mazzy
1
@mazzy count will always be 1 because we're counting the length of a string, not an array.
AdmBorkBork
corda! você está certo. obrigado. -replace0é inteligente.
#
1

Pip , 10 bytes

$+JTB:a\,b

Experimente online!

Explicação

            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 +)
DLosc
fonte
1

Carvão , 10 bytes

ＩΣ⭆…·ＮＮ⍘ι²

Experimente online! Link é a versão detalhada do código. Explicação:

     ＮＮ     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
Neil
fonte
1

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
Fatalize
fonte
1

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

ngn
fonte
1

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
Jo King
fonte
1
You can reduce it by one byte if you use [...](@_) instead of ($^a..$^b)
Brad Gilbert b2gills
1

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
Galen Ivanov
fonte
Can you make it 14?
FrownyFrog
@FrownyFrog I'll try later today (apparently it's possible, since you are asking :) )
Galen Ivanov
@FrownyFrog 15 for now, I'm still trying...
Galen Ivanov
1
14
FrownyFrog
@FrownyFrog Aah, so easy! I was thinking about }. but always in a fork and not in a hook. Thanks!
Galen Ivanov
1

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!

steenbergh
fonte