liczba 1 w 32 bitowym numerze

Question

Szukam metody numer 1 w 32 bitowym numerze bez użycia pętli pomiędzy. może pomóc dowolne ciało i dostarczyć mi kod lub algorytm , aby to zrobić. Z góry dzięki.

Answer 1

Patrz kanonicznej odniesienia: Bit Twiddling Hacks

Answer 2

rozdzielać liczba 32-bitowa w czterech 8-bitowych liczb (patrz nieco przesuwa operatora, odlewanie itp)

Następnie za pomocą odnośnika z 256 wpisów, które przetwarza 8 bit liczba do liczby zestawów bitów. Dodaj cztery wyniki, presto!

także zobaczyć, co powiedział Mitch Wheat - nieco błahy może być dużo zabawy;)

Answer 3

Zobacz Integer.bitCount(int). Można odwołać się do kodu źródłowego, jeśli chcesz zobaczyć, jak to działa; wielu z rutyny nieco twiddling klasy za Integer są pobierane z Hacker's Delight.

Answer 4

Można go zdefiniować rekurencyjnie:

int bitcount(int x) { 
    return (x==0) ? 0 : (x & 1 + bitcount(x/2)); 
} 

Powyższy kod nie został przetestowany i prawdopodobnie działa tylko dla x> = 0. Mamy nadzieję, że dostaniesz pomysł Anyways ...

Answer 5

mój osobisty faworyt, bezpośrednio z Bit Twiddling Hacks:

v = v - ((v >> 1) & 0x55555555); 
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; 

Answer 6

krótki, nieprzyzwoicie zoptymalizowaną odpowiedź (w C):

int pop(unsigned x) { 
    x = x - ((x >> 1) & 0x55555555); 
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333); 
    x = (x + (x >> 4)) & 0x0F0F0F0F; 
    x = x + (x >> 8); 
    x = x + (x >> 16); 
    return x & 0x0000003F; 
} 

Aby zrozumieć, dlaczego ta magia działa, patrz: Quest for Accelerated Population Count autorstwa Henry S. Warren, Jr. rozdział 10 w Piękny kod.

Answer 7

Poniżej JDK 1,5 realizacja z Integer.bitCount

public static int bitCount(int i) { 
    // HD, Figure 5-2 
i = i - ((i >>> 1) & 0x55555555); 
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); 
i = (i + (i >>> 4)) & 0x0f0f0f0f; 
i = i + (i >>> 8); 
i = i + (i >>> 16); 
return i & 0x3f; 
}