Hamming Gewicht der Kräfte

Was ist bei positiven ganzen Zahlen und über die räumliche und zeitliche Komplexität des Findens des Hamming-Gewichts (Anzahl der binären Einsen) von ? $b$ $e$ $b^e$

Wenn Bits verfügbar sind, kann die Anzahl einfach durch Standardtechniken berechnet und die Einsen gezählt werden. Aber welche Techniken sind möglich, wenn weniger Speicher verwendet werden kann? $e\log b$

ds.algorithms co.combinatorics space-bounded space-time-tradeoff Charles
quelle

Warum rechnen Sie nicht in der chinesischen Restdarstellung, verwenden den Chiu-Davida-Litow-Algorithmus, um im logarithmischen Raum in eine binäre Darstellung umzuwandeln, und zählen dann einfach?

Markus Bläser

@ MarkusBläser antworten?

Suresh Venkat

Antworten:

Diese Antwort erweitert meinen obigen Kommentar.

Sie können dies mit wie folgt tun : $O(\log e + \log \log b)$

1) Zuerst compute in chinesischer Rest Darstellung modulo ausreichend viele Primzahlen. $b^e$

2) Verwenden Sie dann den Chiu-Davida-Litow-Algorithmus, um die chinesische Restdarstellung in eine binäre Darstellung umzuwandeln. (Informatique Theoretique et Applications, Band 35 (3), Seiten 259-275, 2001)

3) Schließlich zählen nur die Anzahl der ‚s. $1$

Dies ist eine Zusammensetzung einer endlichen Anzahl von berechenbaren Funktionen des Protokollraums, die selbst berechenbar sind.

Markus Bläser
quelle