Wie viele bits Sie brauchen, um zu speichern eine positive ganze Zahl?

Wieviel bit würde man benötigen, um zu speichern eine positive ganze Zahl beispielsweise in Milliardenhöhe? Würdest du den log2 N dies heraus zu finden?

  • Als integer oder floating-point-und mit welcher Genauigkeit?
  • Signed oder unsigned? Das heißt, negative Ganzzahlen möglich, oder sind Sie daran interessiert, die nur nicht-negative Ganzzahlen? (Ich nehme es aus das Ihre Frage ist Kontext, du sprichst von ganzen zahlen, nicht-floating-point-zahlen.)
  • Ja, ich spreche positive ganze zahlen sind. So wäre es den log2 N?
InformationsquelleAutor user1647008 | 2012-09-04
  1. 33

    Da ich gesehen habe, ist die Antwort falsch gemeldet, so viele Male, ich dachte, ich würde post die richtige Antwort.

    Anzahl der bits, die benötigt werden, um repräsentieren die positive ganze Zahl n ist

    bits = floor( log2(n) + 1 )

    wo log2 bedeutet Logarithmus zur Basis 2.

    • Diese Lösung gibt mir ein Falsches Ergebnis mit n = 18446744073709551615 (gleich n = pow(2, 8 * sizeof(unsigned long)) auf eine x86_64 box), weil log2(n) = 64 in diesem Fall + 1 zu hoch ist. Gibt es irgendwelche Nachteile bei der Verwendung bits = ceil(log2(n)) statt?
    • Wie @selurvedu Punkte heraus, trotz fordern, Korrektheit, diese Antwort ist falsch, wenn n eine Potenz von 2 ist. Verwenden ceil(log2(n)) statt.
    • Was redest du, und warum Menschen wie Ihre Kommentare? Math.log2(16).ceil gleich 4, aber wir müssen 5, so Math.log2(16).floor + 1 richtig ist. Math.log2((1 << 64) - 1) gleich 64 wegen der unzureichenden Genauigkeit.
    • richtig ist, lieber die Antwort, und bitte nicht upvote die ersten zwei Kommentare weiter
    • Diese Antwort ist falsch. Siehe diese Antwort unten für die richtige Antwort und auch seiner Herleitung (Beweis). Zum Beispiel in Python: bits_reqd_for_num = math.ceil(math.log2(num+1))
    InformationsquelleAutor bradwilder31415
  2. 10

    Ja. die maximale Anzahl gespeichert, die in k bits ist 2^k-1, da es 2^k Möglichkeiten für die bits, und einer von Ihnen ist null.

    Daher ist die Anzahl der erforderlichen bits zur Speicherung einer Zahl N ist log2(N), da es aber keine halben bit, Sie brauchen, um bis zu die cloest integer vor.

    Hinweis: wenn Sie negative zahlen, muss es ein mehr bit für das Vorzeichen.

    InformationsquelleAutor LeeNeverGup
  3. 5

    Nur um die vorherigen zu beantworten, können Sie herausfinden, wie viele bits nötig sind, um eine Zahl darstellen N mathematisch mit jedem log-Basis. Zum Beispiel, sagen, ich will wissen, wie viele bits notwendig sind, stellen die Zahl 12345, aber mein Rechner kennt nur ln (natürlicher Logarithmus).

    So,

    2^b = 12345

    Unter der ln von beiden Seiten.

    ln(2^b) = ln(12345)

    Natürlich das log von einer Zahl ein exponent ist, der exponent mal die log, der nur in der base So,

    b*ln(2) = ln(12345)

    Teilen sowohl einseitig von ln(2),

    b = ln(12345) /ln(2)

    Und natürlich, wie es in der anderen Antwort, die Sie müssen, um dieses Ergebnis, weil zu repräsentieren, eine Zahl, die Sie benötigen 2^b gleich oder größer als die Anzahl.

    So,

    b = ceil(ln(12345) /ln(2))

    Wo ceil(f) Runden f bis auf die nächste Ganzzahl.

    Unter Verwendung des oben beschriebenen Prozesses finden Sie die Anzahl der bits, die benötigt werden für eine beliebige Anzahl N mit jedem log-base logb, d.h.,

    b = ceil(logb(N) /logb(2))
    • beachten Sie, dass wenn Sie mit 0-basierten Ganzzahlen, wo 000 entspricht 0 und 111 entspricht 7, Sie actaully hinzufügen müssen 1 zu dieser Formel.
    • Explizit von dem, was @siemanko ist zu sagen, verwenden Sie b = ceil(logb(N+1) / logb(2))
    InformationsquelleAutor mjgpy3
Schreibe einen Kommentar