W dniu 2015-12-05 o 00:49, bartekltg pisze:
> Jak opisałem poprzednio, kolejka fifo w cyklicznym buforze.
> Ale inicjalizowana małą ilośćią liczb na początek.
> Jeśli kolejka opustoszje, realokujesz dla niej dwa raz wiekszą
> pamieć (tzn powiekszasz vectror, w którym to trzymasz:)
> i dodajesz kolejne liczby.

Pomysł ciekawy, zwłaszcza to, że jest inicjowana małą ilością liczb na
początek, a potem można zwiększać. Kolejkę FIFO rozumiem jako dwa
indeksy wskazujące na bufor, aby nie trzeba było przemieszczać danych?
Na razie zaangażowałem się w maski potrójnego poziomu - maska maks. 256
bitów, drugiego poziomu miała być 65 K a trzeciego 16 M. To raczej
skomplikowana sprawa, więc, jak będą trudności zrobię powiększające się
FIFO.
Wracając do szukania bitu w słowie:
zrobiłem testy, tam m.in. dwie metody z Uczty Programistów, które
przesuwają kolejno o 18,8,4 i 2 bity. Metoda połówkowania całkowita do
bitu i do czterech bitów; dodałem również dla porządku najoczywistszą
metodę pętli.
Co się okazało: wszystkie mniej więcej w tym samym czasie, a najszybsza
była metoda w pętli: (co dziwne, bo czas miał być proporcjonalny do
liczby bitów a nie logarytmu z nich)
int ntz5_15(unsigned x)
{
int n;
x = ~x & (x - 1);
n = 0;
while (x != 0)
{
n = n + 1;
x = x >> 1;
}
return n;
}
Tutaj jest jeden myk: "x = ~x & (x - 1)" wypełnia bity aż do napotkania
pierwszej jedynki od dołu. Dzięki temu nie trzeba w pętli stosować AND.
W gruncie rzeczy potrzebowałem szukać zer, więc:
int findZero32(uint32_t x)
{
int n;
x = x & (~x - 1);
n = 0;
while (x != 0)
{
n = n + 1;
x = x >> 1;
}
return n;
}
Lecz dla 64 bitów pętla to przesada, więc połówkuję go:
int findZero64(uint64_t x)
{
if ((x | 0xffffffff00000000)!= 0xffffffffffffffff)
return findZero32((uint32_t)x); //this branch must be first
else
return findZero32((uint32_t)(x >> 32)) + 32;
}


Jeszcze o testach: test jednorodny odpada, bo połowa przypadków to były
by pomiędzy 2 miliardy a 4 miliardy. Wybieram więc liczbę jedynek od 1
do trzech, potem dla bitu losuję pozycję od 0 do 31 i ustawiam.

Pozdrawiam