Počet nulových bitů v čísle – Java – Fórum – Programujte.com

Ahoj,

řeším takový problém. Mám napsat metodu, která vrátí počet nulových bitů v zadaném long čísle. 

Vím, že long má 64 bitů, ale nějak nevím, jak mám zjistit počet bitů například pro zadané číslo 100. Respektive asi chápu ten princip, zjistím kolik zabírá zadané číslo bitů a poté ho odečtu od celkového počtu bitů které má long.

Můžu poprosit o radu? :)

 Symbolicky

cislo = 123; // musi byt 64 bit
x = 1; // musi byt take 64 bit
bits = 0;
cyklus(i<64) {bits += cislo & x == 0 ? 0 : 1; x = x<<1;} //x = x*2; // if (cislo & x == 0) {bits+=0;} else {bits+=1;}
//cyklus(i<64) {bits += cislo & x; cislo >>= 1;} // cislo /= 2;
vypis(bits);

A tak jestli neznas ani binarni operace, dalo by se pouzit
floor(cislo / 2) == cislo / 2 nebo modulo
floor(5 / 2) == 5 / 2 --> floor(2.5) == 2.5 --> 2 == 2.5 -> false
cislo % 2 == 0
5 % 2 == 0 --> 1==0 --> false
delis 1, 2, 4, 8, ... a zjistujes, jestli je to pak true nebo false

Můžeš mi to prosím nějak okomentovat? Především co dělá ten 4. řádek

#3 Michal
tady máš taky moc hezkou odpoved

https://stackoverflow.com/questions/35639045/converting-an-unsigned-long-to-binary-in-c

Aha. Zkus si polozit otazku, jak zjistis jednotlive bity?

'deleni modulo %' je jen alternativni operace k 'and &'.
'floor + podminka' je jen alternativni operace k 'modulo'.
'nasobeni x*2' je podobna operace k shiftovani doleva x<<1
'deleni floor(x/2)' je podobna operace k shiftovani doprava x>>1

5 / 2 = 2.5
floor (5 / 2) = floor (2.5) = 2 ... orezani desetinne casti
5 % 2 = 1 ... 5 / 2 = 2 zbytek 1 ... matematika modulo, zbytek po celociselnem deleni
5 >> 0 = (bin) 0101>>0 = (bin) 0101 = (dec) 5 ... cislo nijak nezmeni, ale presto je to platna operace
5 >> 1 = (bin) 0101>>1 = (bin) .010 = (dec) 2 ... smaze posledni 1 bit ... cili to same jako floor (5 / 2)
5 >> 2 = (bin) 0101>>2 = (bin) ...01 = (dec) 1 ... smaze posledni 2 bity
5 >> 3 = (bin) 0101>>3 = (bin) ....0 = (dec) 0 ... smaze posledni 3 bity
5 & 1 = (bin) 0101 & 0001 = (bin) 0001 = (dec) 1
(5 >> 0) & 1 = (bin) (0101 >> 0) & 0001 = (bin) 0101 & 0001 = 0001
(5 >> 1) & 1 = (bin) (0101 >> 1) & 0001 = (bin) 0010 & 0001 = 0000
(5 >> 2) & 1 = (bin) (0101 >> 2) & 0001 = (bin) 0001 & 0001 = 0001
(5 >> 3) & 1 = (bin) (0101 >> 3) & 0001 = (bin) 0000 & 0001 = 0000
... dal uz jsou jen nuly
A kdyz sectes vysledek, ziskas pocet jednicek.
A samozrejme misto shiftu muses modulo % nebo floor+podminku.

#1 Michal
jukni na https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

je tam ukázáno a popsáno několik způsobů od jednoduchého for až po různé matematické "zkratky"

#6 Ovrscout
případně pokud to chceš jenom použít tak koukni umí tvůj překladač (případně i procesor) např gcc podporuje

__builtin_popcount(x) https://gcc.gnu.org/onlinedocs/gcc-4.3.4/gcc/Other-Builtins.html

který by se měl optimalizovaně přeložit pro danou architekturu. (v tomto případě bude třeba zavolat zvlášť pro každých 32 bitů)

#7 Ovrscout
něco pro java https://stackoverflow.com/questions/4839128/optimizing-long-bitcount