Zliczana liczba bitów: Jak działa ta linia? n = n &(n-1);

Question

Potrzebuję wyjaśnienia, jak działa ta konkretna linia.
Wiem, że ta funkcja zlicza liczbę bitów 1, ale jak dokładnie ta linia usuwa prawy 1 bit?

int f(int n) { 
    int c; 
    for (c = 0; n != 0; ++c) 
     n = n & (n - 1); 
    return c; 
} 

Czy niektórzy mogą mi to krótko wyjaśnić lub podać jakiś "dowód"?

Answer 1

Wszystkie niepodpisane liczby całkowite "n" będą miały następujące ostatnie cyfry k: jeden po którym następują (k-1) zera: 100 ... 0 Należy zauważyć, że k może wynosić 1, w którym to przypadku nie ma zer.

(n - 1) zakończy się w tym formacie: Zero następnie (k-1) na 1: 011 ... 1

n & (n-1) zakończy się zatem w zer 'k': 100 ... 0 & 011 ... 1 = 000 ... 0

Stąd n & (n - 1) usunie prawe "1". Każda iteracja spowoduje usunięcie najbardziej na prawo cyfry "1", a więc możesz policzyć liczbę 1.

Answer 2

Odświeżyłem nieco manipulację i natknąłem się na to. Może to nie być użyteczne dla oryginalnego plakatu (3 lata później), ale i tak mam odpowiedzieć, aby poprawić jakość dla innych widzów.

Co to oznacza dla n & (n-1) na zero?

Powinniśmy upewnić się, że wiemy, że jest to jedyny sposób na przerwanie pętli (n != 0). Powiedzmy, że n=8. Bit reprezentacji dla tego byłby 00001000. Bit reprezentacji dla n-1 (lub 7) będzie 00000111. Operator & zwraca bity ustawione w obu argumentach. Ponieważ 00001000 i 00000111 nie mają żadnych podobnych zestawów bitów, wynikiem będzie 00000000 (lub zero). Być może przyłapałeś się na tym, że liczba 8 nie została przypadkowo wybrana. Był to przykład, gdzie n jest potęgą 2. Wszystkie moce 2 (2,4,8,16 itd.) Będą miały ten sam rezultat.

Co stanie się, gdy przekażesz coś, co nie jest wykładnikiem 2? Na przykład, gdy n=6 reprezentacja bit jest 00000110 i n-1=5 lub 00000101 .Powierzchnia & stosuje się do tych 2 argumenty i mają tylko jeden pojedynczy bit, który jest wspólny 4. Teraz n=4 który nie jest zerem, więc przyrost c i spróbuj ten sam proces z n=4. Jak widzieliśmy powyżej, 4 jest wykładnikiem 2, więc przerwie pętlę w następnym porównaniu. To jest odcięcie nieco na prawo, aż n jest równa sile 2.

Co jest c?

To jest zwiększany tylko przez jednego każdą pętlę i rozpoczyna się od 0. c to liczba bitów odcięte przed numerem równa moc 2.