Counting Bits

Datum: Mai 2025
Lesedauer: 4 Minuten

Herleitung und Lösung der Leetcode Challenge.

Nr.: 338
Difficulty: Easy
Link: https://leetcode.com/problems/counting-bits (opens in a new tab)

Problem

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Example 1

Input: n = 2
Output: [0,1,1]
Explanation:

0 --> 00
1 --> 01
2 --> 10

Example 2

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:

0 --> 000
1 --> 001
2 --> 010
3 --> 011
4 --> 100
5 --> 101

Constraints

0 <= n <= 105

Lösung

Herleitung

Binärzahlen setzen sich wie folgt zusammen:

✅ 1 (aktiv; highestBit - wird nachfolgend erklärt)
🟩 1 (aktiv)
🟥 0 (inaktiv)

Das Ergebnis jeder Zahl soll in einem Array ans gespeichert und zurückgegeben werden. Dieses Array wird zu Beginn mit dem Wert 0 initialisiert, da die Zahl 0 keine 1 in ihrer binären Darstellung aufweist und somit als Ausgangswert dient.

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    return ans;
}

Mit einer Schleife kann dann die Berechnung für die gewünschte Anzahl an Zahlen durchgeführt werden.

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    for (let i = 1; i <= n; i++) {}
    return ans;
}

Für alle nachfolgenden Zahlen muss die Anzahl der aktivierten Bits ermittelt werden. Es ist bekannt, dass jede Zahl mindestens ein aktives Bit besitzt. Darüber hinaus lässt sich feststellen, dass bei mehr als einem aktiven Bit frühere Berechnungsergebnisse wiederverwendet werden können.

Für die Berechnung der Anzahl der Bits für 3 können die Ergebnisse der Zahlen 2 und 1 genutzt werden.

Dazu muss das vorderste/höchste Bit identifiziert werden. Hierfür bestimmt man den grössten Exponenten von 2, der die Zahl noch abbilden kann. Dieser Exponent wird hier als highestBit bezeichnet. In den Tabellen ist dieser mit einem ✅ markiert.

So sieht dieser Wert aus:

Mit der highestBit Variable kann das grösste, aktive Bit ermittelt werden.
Die Variable wird mit 1 initialisiert. Sobald ein Exponent von 2 (2, 4, 8, ...) erreicht wird, wird der Wert der Variable entsprechend angeglichen.

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    let highestBit = 1;
 
    for (let i = 1; i <= n; i++) {
        if (highestBit * 2 === i) highestBit *= 2;
    }
 
    return ans;
}

Mit dem highestBit ist ein Teil der Zahl bereits abgedeckt. Die verbleibenden/niedrigeren Bits müssen noch bestimmt werden. Beispiel: Die Zahl 7 hat ihr highestBit bei 4. Um die restlichen aktiven Bits zu ermitteln, wird der Wert 3 (7 - 4) ausgewertet.

✅ 1 (aktiv; highestBit)
🟩 1 (aktiv)
🟥 0 (inaktiv)

Die Anzahl der in 3 enthaltenen aktiven Bits muss jedoch nicht neu berechnet werden. Sie ist zu diesem Zeitpunkt bereits bekannt und kann direkt ausgelesen werden.

✅ 1 (aktiv; highestBit)
🟩 1 (aktiv)
🟥 0 (inaktiv)

Formel

Das Ergebnis ergibt sich aus der Summe von 1 für das gesetzte höchste Bit und dem bereits bekannten Ergebnis für den verbleibenden Wert. Daraus ergibt sich folgende Formel:

ans[i] = 1 + ans[i - highestBit];

Beispiel:

ans[7] = 1 + ans[7 - 4];

ans[7] = 1 + ans[3];

0: 0
1: 1
2: 1
3: 2 <- ans[3]
4: 1
5: 2
6: 2
7: 1 + ans[3]

ans[7] = 1 + 2;

Code

/**
 * @param {number} n
 * @return {number[]}
 */
function countBits(n) {
    let ans = [0];
    let highestBit = 1;
 
    for (let i = 1; i <= n; i++) {
        if (highestBit * 2 === i) highestBit *= 2;
        ans[i] = 1 + ans[i - highestBit];
    }
 
    return ans;
}

Ablauf visualisiert

countBits(7);

✅ 1 (aktiv; highestBit)
🟩 1 (aktiv)
🟥 0 (inaktiv)

* i - highestBit
** ans[i - highestBit]
*** 1 + ans[i - highestBit]