Zählen Sie diejenigen in Reichweite

20

Herausforderung :

Zählen Sie die Anzahl der Einsen 1in der binären Darstellung aller Zahlen zwischen einem Bereich.

Eingabe:

Zwei nicht dezimale positive ganze Zahlen

Ausgabe :

Die Summe aller 1s im Bereich zwischen den beiden Zahlen.

Beispiel

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

Ich habe nur das erste Beispiel erklärt, sonst hätte es sehr viel Platz in Anspruch genommen, wenn ich versucht hätte, es für alle zu erklären.

Hinweis :

  • Zahlen können um mehr als 1000 voneinander entfernt sein
  • Alle Eingaben sind gültig.
  • Die minimale Ausgabe wird eins sein.
  • Sie können number als Array von zwei Elementen akzeptieren.
  • Sie können wählen, wie die Nummern bestellt werden.

Gewinnkriterien:

Dies ist Code-Golf, so dass der kürzeste Code in Bytes für jede Sprache gewinnt.

code-golf math number binary Muhammad Salman
quelle
1
OEIS A000788
Undichte Nonne
1
Dürfen wir die Eingabe als eine Art Bereichstyp annehmen ( IntRangein Kotlin, Rangein Ruby)?
snail_
Spaßtatsache: Fall 1000 - 2000ergibt 5938, aber den Fall von 1000 senken, ist das Ergebnis fällt auch durch 1000: 0-1000 = 4938. Beweis
steenbergh

Antworten:

9

JavaScript (ES6), 38 Byte

Übernimmt Eingaben in der Currying-Syntax (a)(b).

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

Probieren Sie es online!

Kommentiert

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
quelle
6

Python 2 , 47 Bytes

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

Probieren Sie es online!

Dennis
quelle
1
Clevere Trick zu vermeiden >=...
Erik der Outgolfer
5

Java (JDK 10) , 55 Byte

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

Probieren Sie es online!

Olivier Grégoire
quelle
IntStream.range(a,b+1).map(Integer::bitCount).sum()
saka1029
@ saka1029 Die Importe sind obligatorisch. Also ist es eigentlich a->b->java.util.stream.IntStream.range(a,b+1).map(Integer::bitCount).sum()für ganze 74 Bytes. Auch wenn der Import nicht obligatorisch war, sind die Parameter, also müssten wir schreiben a->b->IntStream.range(a,b+1).map(Integer::bitCount).sum(), was wie 57 Bytes zählt
Olivier Grégoire
Sie könnten auch a->b->IntStream.range(a,b+1).map(Long::bitCount).sum()für eine 1-Byte-Verbesserung haben. Marginal, aber immer noch einer.
NotBaal
@NotBaal Wie von Olivier im obigen Kommentar erwähnt, sind Importe obligatorisch, also sollte es sein a->b->java.util.stream.IntStream.range(a,b+1).map(Long::bitCount).sum()(71 Bytes).
Kevin Cruijssen
4

05AB1E , 4 Bytes

ŸbSO

Probieren Sie es online!

Mr. Xcoder
quelle
Genau die Lösung habe ich bekommen :). +1.
Magic Octopus Urn
4

MATL , 5 4 Bytes

&:Bz

Probieren Sie es online!

Danke an Luis Mendo für das Speichern eines Bytes!

(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
quelle
4

R , 41 34 Bytes

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

Probieren Sie es online!

Stark inspiriert von der anderen R-Lösung von ngm . Dies erfolgt nach der Konvertierung in Bits auf andere Weise. Vielen Dank an Giuseppe für den Hinweis auf eine mögliche 34-Byte-Lösung.

JayCe
quelle
34 Bytes sind möglich! Ich habe vergessen, wo ich den Trick gesehen habe (ich weiß, dass ich nicht darauf gekommen bin), aber es gibt eine schwierigere Umwandlung in einen summable-Vektor - ich werde posten, wenn du / ngm ihn nicht finden kannst.
Giuseppe
@ Giuseppe In der Tat!
JayCe
2
Ich habe es auf 37 Bytes mit einer Technik, die sonst nützlich sein könnte. Auch entdeckt, dass sdund varzwingen, was sie können, um zu verdoppeln.
ngm
Sie können pryr::f4 Bytes speichern: tio.run/##K/qfZvu/…
pajonk
@ Pajonk guter Punkt! Aber ich versuche, mich eher an die Basis-R-Pakete als an R + pryr zu halten. Ich werde nach Meta suchen, was als "reines R" bezeichnet werden kann.
JayCe
3

Gelee , 4 Bytes

rBFS

Probieren Sie es online!

Erläuterung

rBFS - Volles Programm. Übernimmt die beiden Eingaben aus den Befehlszeilenargumenten.
r - Reichweite.
 B - Für jede konvertieren Sie in binäre.
  FS - Abflachen und summieren.
Mr. Xcoder
quelle
Oo, das war schnell?
Muhammad Salman
@ Muhammad Salman Nun, die Herausforderung ist auch eine Art triviale IMO.
Mr. Xcoder
Es kann sein, aber eine Minute nach dem Posten eine Antwort.
Muhammad Salman
1
@ MuhammadSalman Ja, das ist nicht wirklich schnell für so einfache Herausforderungen wie diese. Kenntnis von Jelly folgt auch. Der eigentliche Aufwand geht zB in die Sprache dieses Monats, QBasic. ;-)
Erik der Outgolfer
@EriktheOutgolfer: Kannst du das in QBasic / BrainF ** k beantworten?
Muhammad Salman
3

Python 3 , 56 54 52 Bytes

Damit kann imo mehr Golf gespielt werden. -2 Bytes dank Mr.Xcoder -2 Weitere Bytes dank MI Wright

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

Probieren Sie es online!

Windmühle Cookies
quelle
2

Bash + gemeinsame Dienstprogramme, 50

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

Probieren Sie es online!

Das Konvertieren von Ganzzahlen in binäre Zeichenfolgen bereitet im Bash immer einige Schmerzen. Die Vorgehensweise hier ist etwas anders - konvertieren Sie die Ganzzahlen in Oktal und ersetzen Sie dann jede Oktalziffer durch die Anzahl der darin enthaltenen binären Einsen. Dann können wir einfach alle umgerechneten Ziffern summieren

Digitales Trauma
quelle
2

APL + WIN, 33 26 Bytes

Eingabeaufforderungen für den Vektor von ganzen Zahlen:

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

Probieren Sie es online! Mit freundlicher Genehmigung von Dalog Classic

Erläuterung:

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
quelle
2

R , 44 40 37 Bytes

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

Probieren Sie es online!

Vorher:

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

Oktave mit Kommunikationswerkzeugkasten, 21 Bytes

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

Probieren Sie es online!

Der Code sollte ziemlich offensichtlich sein. Anzahl der Nicht-Null-Elemente in der Binärdarstellung jeder der Zahlen im Bereich.

Dies wäre @(a,b)nnz(dec2bin(a:b)-48)ohne die Kommunikations-Toolbox.

Stewie Griffin
quelle
1

Schale , 4 Bytes

Σṁḋ…

Probieren Sie es online!

Erläuterung

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

quelle
1

PHP, 97 Bytes

(Sicher, das kann gekürzt werden, wollte aber die Funktionen nutzen)

Probieren Sie es online aus

Code

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

Erläuterung

<?=
 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
quelle
es scheint, dass Sie dies einfach tun können
dzaima
Für eine Sekunde habe ich absolut vergessen, dass Sie den Namen der PHP-Funktion direkt als Parameter festlegen können :-(
Francisco Hahn
$argv[0]ist der Programmname oder "-"; Sie sollten mit $argv[1]und arbeiten $argv[2]. Und Sie können joinstattdessen verwenden implode, um dies auf 68 Bytes zu verkürzen:<?=substr_count(join(array_map(decbin,range($argv[1],$argv[2]))),1);
Titus
1

PowerShell , 72 Byte

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

Probieren Sie es online!

Lange wegen der Umstellung auf Binär [convert]::ToString($_,2)und Loswerden der Nullen -replace0. Ansonsten nehmen wir einfach die eingegebenen Zahlen, bilden einen Bereich $x..$yund wandeln ihn für jede Zahl im Bereich in Binär um, entfernen die Nullen, nehmen .lengthdie Anzahl der verbleibenden Einsen und addieren sie zu unserem $oErgebnis.

AdmBorkBork
quelle
versuchen Sie es countstattdessen zu verwenden length:)
mazzy
1
@mazzy countwird immer sein, 1weil wir die lengthZeichenfolge und nicht das Array zählen.
AdmBorkBork
Zeichenfolge! Du hast recht. Vielen Dank. -replace0ist schlau.
mazzy
1

Pip , 10 Bytes

$+JTB:a\,b

Probieren Sie es online!

Erläuterung

            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
quelle
1

Kohle , 10 Bytes

ＩΣ⭆…·ＮＮ⍘ι²

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

     ＮＮ     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
quelle
1

Brachylog , 8 Bytes

⟦₂ḃᵐcọht

Probieren Sie es online!

Erläuterung

⟦₂         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
Tödlich
quelle
1

K (NGN / k) , 19 13 Bytes

{+//2\x_!1+y}

Probieren Sie es online!

{ }ist eine Funktion mit Argumenten xundy

!1+y ist die Liste 0 1 ... y

x_ Lässt die ersten x Elemente fallen

2\ codiert jedes int als eine Liste von Binärziffern gleicher Länge (dies ist spezifisch für ngn / k)

+/ Summe

+//Summe bis zur Konvergenz; in diesem Fall Summe der Summe aller Binärziffernlisten

ngn
quelle
1

Perl 6 , 32-30 Bytes

-1 Bytes dank Brad Gillbert

{[…](@_)>>.base(2).comb.sum}

Probieren Sie es online!

Erläuterung:

[…](@_)    #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
Scherzen
quelle
1
Sie können es um ein Byte reduzieren, wenn Sie [...](@_)anstelle von($^a..$^b)
Brad Gilbert b2gills
1

J , 16, 15, 14 Bytes

Dank FrownyFrog 1 Byte gespart!

+/@,@#:@}.i.,]

Probieren Sie es online!

Erläuterung:

Bei einem dyadischen Verb ist das linke Argument die untere Grenze mdes Bereichs, das rechte die obere 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
quelle
Schaffst du es 14?
FrownyFrog
@ FrownyFrog werde ich später versuchen heute (anscheinend ist es möglich, da Sie fragen :))
Galen Ivanov
@ FrownyFrog 15 für jetzt versuche ich immer noch ...
Galen Ivanov
1
14
FrownyFrog
@FrownyFrog Aah, so einfach! Ich habe darüber nachgedacht, }.aber immer in einer Gabel und nicht in einem Haken. Vielen Dank!
Galen Ivanov
1

QBasic, 95 93 83 82 Bytes

@ DLosc hat mir ein paar Bytes gespart !

Mit dieser Technik ein weiteres Byte gespeichert !

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

Sprache des Monats FTW!

Erläuterung

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

Letzter Testfall von 1000 bis 2000 funktioniert tatsächlich in QBasic 4.5 unter Dosbox: Hij doet het!

steenbergh
quelle