Bits in einem Zahlenbereich zählen ohne Iteration

[Dennis89]

Hallo zusammen,

habe heute eine Programmieraufgabe entdeckt, bei der ich nicht mal einen Ansatz finde, ich wäre aber sehr an der Lösung interessiert. Wäre nett, wenn ihr einen Hinweis für mich hättet.
Die Aufgabenstellung:

Given two numbers: 'left' and 'right' (1 <= 'left' <= 'right' <= 200000000000000) return sum of all '1' occurencies in binary representations of numbers between 'left' and 'right' (including both)

Example:

Code: Alles auswählen

countOnes 4 7 should return 8, because:
4(dec) = 100(bin), which adds 1 to the result.
5(dec) = 101(bin), which adds 2 to the result.
6(dec) = 110(bin), which adds 2 to the result.
7(dec) = 111(bin), which adds 3 to the result.
So finally result equals 8.

WARNING: Segment may contain billion elements, to pass this kata, your solution cannot iterate through all numbers in the segment!

Ich habe schon `bit_count()` entdeckt. Ich habe aber nur den Ansatz im Kopf das ich über den Zahlenbereich iteriere und dass ist das, was ich nicht soll.

Wie macht man so was? Habe echt gar keine Idee und auch kein Suchbegriff mit dem ich die Ente füttern könnte. Ich denke dass das schon eine Aufgabe ist, die über die Grundlagen von Python hinausgeht und etwas mehr Programmierhintergrund erfordert. Es gibt immer viele Weg, nur hier sollte man sich wohl vor dem programmieren über die Performance Gedanken machen. Ich bin eigentlich bis jetzt glücklich gewesen, wenn ich strukturierten Code hinbekam, der seine Aufgabe erfüllte, aber nun bin ich sehr neugierig.

Würde mich über Tipps freuen.

Vielen Dank und Grüße
Dennis

[noisefloor]

Hallo,

vorab: ich kannte das (auch) nicht, aber der 1. Suchbegriff bei Google "count 1 in binary number" bringt als 1. Treffer einen SO Thread mit Erklärungen und dem Stichwort "Hamming weight" und der 2. Suchtreffer ist dieser Post bei GeeksForGeeks, der diverse Implementierungen inkl. Python 3 zeigt.

Gruß, noisefloor

[nezzcarth]

Ich denke, wenn es iterativ sein soll, dass du nicht weiter als bis 48 iterieren musst. Wenn du einen eher mathematischen Ansatz bevorzugst, hier etwas zur Inspiration: https://oeis.org/A000120

[narpfel]

Das ist keine Programmieraufgabe, sondern eine Matheaufgabe, würde ich vermuten. Ohne das jetzt genau durchgegangen zu sein, ist das ein Aufgabentyp, bei dem man am Ende gerne mal eine geschlossene Formel oder einen Algorithmus hat, der in O(1) läuft.

... Aber: Wenn ich das richtig überschlagen habe, kann eine aktuelle Zen4-CPU pro Takt und Kern 5,3 Zahlen durchgehen. Das heißt, dass eine Ryzen-7950X-CPU zum Bruteforcen des gesamten Bereichs nur gut vier Minuten braucht? Ist vielleicht eine interessante Fingerübung, wenn man so eine CPU gerade zur Hand hat.

[sparrow]

Wirkt auf den erstenb Blick eher so, als wäre nicht die Herausforderung das für eine Zahl zu errechnen, sondern das für die Range zu errechnen, ohne jede Zahl wieder herausfinden zu müssen.

Das geht aus dem Beitrag schon hervor, aber auch mein Reflex war im ersten Moment das auf eine Dezimalzahl zu optimieren.

[nezzcarth]

Das geht aus dem Beitrag schon hervor, aber auch mein Reflex war im ersten Moment das auf eine Dezimalzahl zu optimieren.

Ich bin irgendwie eher bei Zweierpotenzen und dem Pascal'schen Dreieck. Man weiß, dass die genannte Oberschranke, bis zu der das funktionieren soll, 48 Bit hat also auch maximal nur so viele Einsen haben kann und man weiß, dass alle 2**n genau eine 1 haben; der Fall dass eine Zahl durch eine 1 repräsentiert wird, kommt einmal vor, genauso wie der, dass eine Zahl so viele Einsen hat, wie sie Bit lang ist. Die Häufigkeitsverteilung aller anderen Fälle (Zahlen, die durch 2, 3, … Einsen repräsentiert werden) in so einem Abschnitt zwischen 2**n und 2**(n+1) entspricht den Zeilen des Pascal'schen Dreiecks.

Hier außerdem noch eine rekursive Implementation für eine einzelne Zahl:

Code: Alles auswählen

from math import floor, log2

def get_ones(x):
    if x == 0:
        return 0
    # Normalerweise +1; hebt sich hier auf durch die Zeile danach   
    bits = floor(log2(x)) 
    diff = x - 2**bits
    if diff == 0:
        return 1
    return get_ones(diff) + 1

Das wären jedenfalls die Hinweise, die mir gerade so einfallen.

[Dennis89]

Vielen Dank an alle für eure Tipps und Beiträge.
Wollte nur kurz Bescheid geben, ich bin dabei dass alles so gut es geht durch zu arbeiten und ich werde mich melden, sobald ich weiter gekommen bin oder keine Haare mehr auf dem Kopf habe.


Viele Grüße
Dennis

[Qubit]

Ja, das wohl eher ein mathematisches Problem

Die Summe aller Einsen bis zu einer Zweierpotenz 2^k-1 ist k*2^(k-1) (zb. für 0 bis 3=2^2-1 sind das in Summe 2*2^1=4 Einsen).

Das kann man sich zB. durch vollständige Induktion klar machen:

Code: Alles auswählen

A(k) für 2^k-1: 
k*2^(k-1)

A(k+1) für 2^(k+1)-1:
Dazu die Eins (mehr) für 2^k, also:
k*2^(k-1)+1

Dazu die bekannte Summe aus A(k) zum Auffüllen: 
k*2^(k-1)

Plus der Summe der "Eins" für 2^k bei den 2^k-1 zusätzlichen Summanden , also: 
2^k - 1

-> A(k+1):
[k*2^(k-1)+1] + [k*2^(k-1)] + [2^k - 1] = 2*k*2^(k-1) + 2^k = (k+1)*2^(k+1-1)

Das kann man sich jetzt als kleines Programm zusammenbasteln.
(PS: schöner machen kann es jeder selbst.. )

Code: Alles auswählen

from math import floor, log


def count_ones(k,l):

    numbers = k*2**(k-1)+1 + l*2**k

    return int(numbers)


def main(start,end=2):

    result=[]

    for number in (start,end-1):

        counts = 0
        l = 0

        while True:

            k = floor(log(number)/log(2))

            counts += count_ones(k,l)

            number = number - 2**k
            l += 1

            if k == 0 or number == 0:
                break

        result.append(counts)

    return result


if __name__ == "__main__":

    arg = (7,4)
    res = main(*arg)
    print(f"Anzahl 'Einsen' von {arg[1]} bis {arg[0]}: \r\n {res[0]-res[1]}")
    print()

    arg = (200000000000000,12345)
    res = main(*arg)
    print(f"Anzahl 'Einsen' von {arg[1]} bis {arg[0]}: \r\n {res[0]-res[1]}")
    print()

    arg = (13,)
    res = main(*arg)
    print(f"Anzahl 'Einsen' bis {arg[0]}: \r\n {res[0]}")

Code: Alles auswählen

Anzahl 'Einsen' von 4 bis 7:
 8

Anzahl 'Einsen' von 12345 bis 200000000000000:
 4712825299304192

Anzahl 'Einsen' bis 13:
 25

[DeaD_EyE]

Bei der Aufgabe ist mit Absicht eine so große Zahl für das Ende gewählt worden, damit der Computer nie fertig wird, wenn man iteriert. Mit Iteration geht es bis eine Million noch recht fix. Bei einer Milliarde dauert es ....