Number of 1 Bits

Q: Jaka jest złożoność czasowa zadania „Number of 1 Bits”?

Pętla przesunięć wykonuje się raz na każdą cyfrę binarną: O(log n) , tutaj najwyżej 31 kroków. Pętla n & (n-1) wykonuje się raz na każdy bit 1: O(k) , gdzie k jest odpowiedzią. Obie wykorzystują dodatkowo O(1) pamięci.

ŁatweOperacje na bitach

+10

Otrzymujesz nieujemną liczbę całkowitą n. Zapisz n w systemie binarnym i zwróć liczbę cyfr równych 1. Ta liczba jest również nazywana liczbą ustawionych bitów, liczbą jedynek lub wagą Hamminga. Na przykład 6 w systemie binarnym to 110, więc ma dwa bity równe 1.

Funkcja

hammingWeight(n: integer) → integer

ninteger: nieujemna liczba całkowita mieszcząca się w 32-bitowej liczbie całkowitej ze znakiem
Zwracainteger: liczba cyfr 1 w postaci binarnej liczby n

Ograniczenia

0 ≤ n ≤ 2³¹-1

Przykłady

Wejście: n = 11
Wyjście: 3
Wyjaśnienie: 11 w systemie binarnym to 1011, czyli 8 + 2 + 1. Trzy z jego czterech cyfr binarnych to 1, więc odpowiedź to 3.

Wejście: n = 128
Wyjście: 1
Wyjaśnienie: 128 to 2^7, zapisane jako 10000000: jedna jedynka, po której następują zera, więc odpowiedź to 1.

Pytanie dodatkowe

Jeśli ta funkcja wykonałaby się miliony razy, jak można policzyć bity liczby 32-bitowej za pomocą czterech odwołań do tabeli zawierającej 256 wcześniej obliczonych liczników?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Przejdź przez cyfry binarne liczby n bez tworzenia ciągu znaków. Odczytanie ostatniego bitu i przesunięcie go zajmuje jeden krok na każdą cyfrę binarną, maksymalnie 31. Wyczyszczenie najniższego bitu 1 za pomocą n & (n-1) zajmuje jeden krok na każdy bit 1, dokładnie tyle, ile wynosi odpowiedź.

Sprawdź ostatni bit i przesuń w prawo

Intuicja

n & 1 to ostatnia cyfra binarna n: 1, gdy n jest nieparzyste, 0, gdy jest parzyste. Dodaj ją do licznika. Następnie n >> 1 usuwa tę cyfrę i przesuwa kolejną na ostatnie miejsce; dla liczby nieujemnej oznacza to dzielenie przez 2 z zaokrągleniem w dół. Dla 11, czyli 1011, ostatnie bity mają wartość 1, 1, 0 i 1, gdy n zmniejsza się do 0: trzy bity 1.

Pętla zatrzymuje się, gdy n wynosi 0, więc nie odwiedza początkowych zer: około log2(n) kroków, 8 dla 128 i najwyżej 31. Przechowuje tylko n i licznik.

Algorytm

Rozpocznij licznik od 0.
Gdy n jest większe od 0, dodaj n & 1 do licznika.
Przesuń n w prawo o jeden bit.
Gdy n osiągnie 0, zwróć licznik.

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1  # the last bit is 1 or 0
        n >>= 1         # drop the last bit
    return count

Wyczyść najmłodszy ustawiony bit za pomocą n & (n-1)

Intuicja

Odjęcie 1 zamienia najmłodszy bit o wartości 1 na 0, a każde 0 poniżej niego na 1, pozostawiając bity powyżej bez zmian. Zatem n & (n-1) zachowuje starsze bity i zeruje najmłodszy bit o wartości 1: 12 to 1100, 11 to 1011, a 1100 & 1011 to 1000.

Każdy krok usuwa dokładnie jeden bit o wartości 1, więc odpowiedzią jest liczba kroków potrzebnych do uzyskania n równego 0. Dla 128 potrzeba 1 kroku zamiast 8, choć dla 2^31-1 potrzeba 31. Lua 5.1 nie ma operatorów bitowych, więc jej wersja znajduje najmłodszy bit o wartości 1 przez kolejne dzielenie przez 2 i odejmuje go; pętla nadal wykonuje się raz na każdy bit o wartości 1.

Algorytm

Ustaw licznik na 0.
Dopóki n nie jest równe 0, zastępuj n wartością n & (n-1).
Po każdym zastąpieniu zwiększ licznik o 1.
Zwróć licznik.

def hammingWeight(n):
    count = 0
    while n != 0:
        n &= n - 1  # turn off the lowest 1 bit
        count += 1
    return count

Pułapki i przypadki brzegowe

Wykonywanie pętli while n > 1. Pętla zatrzymuje się przed ostatnim bitem 1 i zwraca 0 dla n = 1.
Dzielenie z użyciem liczby zmiennoprzecinkowej. W JavaScript, Lua i R, 11 / 2 wynosi 5.5, a kolejne reszty są ułamkami. Zaokrąglaj w dół za pomocą Math.floor, math.floor lub %/% albo zamiast tego przesuwaj bity.
Zapisywanie n & 1 w Lua 5.1. Nie ma tam operatorów bitowych, więc kod się nie kompiluje; użyj n % 2 i math.floor(n / 2).

Najczęstsze pytania3

Jaka jest złożoność czasowa zadania „Number of 1 Bits”?

Pętla przesunięć wykonuje się raz na każdą cyfrę binarną: O(log n), tutaj najwyżej 31 kroków. Pętla n & (n-1) wykonuje się raz na każdy bit 1: O(k), gdzie k jest odpowiedzią. Obie wykorzystują dodatkowo O(1) pamięci.

Czy istnieje wbudowana funkcja, która zlicza ustawione bity?

Większość języków ma taką funkcję, często opartą na pojedynczej instrukcji procesora: Integer.bitCount w Javie, __builtin_popcount w GCC, bits.OnesCount w Go, count_ones w Rust i int.bit_count w Pythonie 3.10 i nowszych. Na rozmowie kwalifikacyjnej napisz pętlę i wspomnij o wbudowanej funkcji.

Jaka jest różnica między wagą Hamminga a odległością Hamminga?

Waga Hamminga liczby to liczba jej cyfr binarnych równych 1 — właśnie tę wartość zwraca ten problem. Odległość Hamminga między dwiema liczbami to liczba pozycji bitowych, na których się różnią: policz bity równe 1 w a ^ b, ponieważ XOR ustawia dokładnie te pozycje, na których liczby się różnią.

def hammingWeight(n):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argument

n = 11

Oczekiwany wynik