Hejka,

Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
ustawione jakieś bity, ale czasem nie.
Jak najszybciej znaleźć indeks ustawionego bitu?
Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
odkryć, że "pali" się np. czterdziesty ósmy?
Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
w najgorszym razie trzeba przeiterować 63 razy.
Może da się szybciej?
Może jakieś operacje arytmetyczne?

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

szemrany <s...@o...off> napisał(a)
> Hejka,
>
> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
> ustawione jakieś bity, ale czasem nie.
> Jak najszybciej znaleźć indeks ustawionego bitu?
> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
> odkryć, że "pali" się np. czterdziesty ósmy?
> Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
> w najgorszym razie trzeba przeiterować 63 razy.
> Może da się szybciej?

A to nie jest "premature optymzation":)?

> Może jakieś operacje arytmetyczne?

Jeśłi to tylko jeden bit, to szukaj binarnie.

--
Tomek

do góry

On Mon, 31 Aug 2015 20:39:28 +0000 (UTC), Tomek Kańka wrote:

>> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
>> ustawione jakieś bity, ale czasem nie.
>> Jak najszybciej znaleźć indeks ustawionego bitu?
>> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
>> odkryć, że "pali" się np. czterdziesty ósmy?
>> Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
>> w najgorszym razie trzeba przeiterować 63 razy.
>> Może da się szybciej?
>
> A to nie jest "premature optymzation":)?

Raczej nie, to część struktury używanej wielowątkowo i często.

>> Może jakieś operacje arytmetyczne?
>
> Jeśłi to tylko jeden bit, to szukaj binarnie.

Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
elementów w tablicy niż tylko 0 i 1.
Ale może masz co innego na myśli?

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

Użytkownik "Tomek Kańka" <t...@t...eu.org> napisał:

>> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
>> odkryć, że "pali" się np. czterdziesty ósmy?

x & (1 << (48 - 1))

AK


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe
Avast.
https://www.avast.com/antivirus

do góry

szemrany <s...@o...off> napisał(a)
> On Mon, 31 Aug 2015 20:39:28 +0000 (UTC), Tomek Kańka wrote:
>
>>> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
>>> ustawione jakieś bity, ale czasem nie.
>>> Jak najszybciej znaleźć indeks ustawionego bitu?
>>> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
>>> odkryć, że "pali" się np. czterdziesty ósmy?
>>> Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
>>> w najgorszym razie trzeba przeiterować 63 razy.
>>> Może da się szybciej?
>>
>> A to nie jest "premature optymzation":)?
>
> Raczej nie, to część struktury używanej wielowątkowo i często.
>
>>> Może jakieś operacje arytmetyczne?
>>
>> Jeśłi to tylko jeden bit, to szukaj binarnie.
>
> Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
> elementów w tablicy niż tylko 0 i 1.


Jeśli zapalony jest tylko 1 bit, to wyszukujemy binarnie (w sensie
dzielenia przedziału na połówki). zaczynamy od 2^32 i sprawdzamy, czy
liczba jest wieksza/mniejsza. Na tej podstawie
zawężamy przedział. Zapalony bit znajdziemy w 6 krokach.

--
Tomek

do góry

On Mon, 31 Aug 2015 23:07:22 +0200, AK wrote:

>>> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
>>> odkryć, że "pali" się np. czterdziesty ósmy?
>
> x & (1 << (48 - 1))

Hmm... tak, tylko, że ja pytam jak odkryć, że to akurat czterdziesty ósmy -
bo tego nie wiem, a nie jak sprawdzić czy czterdziesty ósmy jest ustawiony,
bo to trywialne.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

On Mon, 31 Aug 2015 21:21:18 +0000 (UTC), Tomek Kańka wrote:

>> Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
>> elementów w tablicy niż tylko 0 i 1.
>
> Jeśli zapalony jest tylko 1 bit, to wyszukujemy binarnie (w sensie
> dzielenia przedziału na połówki). zaczynamy od 2^32 i sprawdzamy, czy
> liczba jest wieksza/mniejsza. Na tej podstawie
> zawężamy przedział. Zapalony bit znajdziemy w 6 krokach.

No właśnie nie jest tylko jeden, lecz zazwyczaj więcej. Ta liczba 64 bitowa
to tablica bitów/flag i chce znaleźć pierwszy, dowolny ustawiony bit.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry

W dniu poniedziałek, 31 sierpnia 2015 22:49:24 UTC+2 użytkownik szemrany napisał:
> On Mon, 31 Aug 2015 20:39:28 +0000 (UTC), Tomek Kańka wrote:
>
> >> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
> >> ustawione jakieś bity, ale czasem nie.
> >> Jak najszybciej znaleźć indeks ustawionego bitu?
> >> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
> >> odkryć, że "pali" się np. czterdziesty ósmy?
> >> Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
> >> w najgorszym razie trzeba przeiterować 63 razy.
> >> Może da się szybciej?
> >
> > A to nie jest "premature optymzation":)?
>
> Raczej nie, to część struktury używanej wielowątkowo i często.
>
> >> Może jakieś operacje arytmetyczne?
> >
> > Jeśłi to tylko jeden bit, to szukaj binarnie.
>
> Algorytm wyszukiwania binarnego wymaga chyba większego zróżnicowania
> elementów w tablicy niż tylko 0 i 1.

A to czemu?
Wyszukiwani binarne oznacza tu tyle, że sprawdzasz
na raz połowę bitów.
Tu masz przykład takiego wyszukiwania
https://graphics.stanford.edu/~seander/bithacks.html
#IntegerLog
wyszukuje pierwszy zapalony bit. Obok jest parę innych.

Masz też wbudowaną funckję __builtin_clz
(w innym kompilatorze będzie się nazywałą inaczej).

Jeśli zapalony jest tylko jeden bit, możesz odjać
jedynkę i policzyć bity, lub...
wziąć modulo 37 (tylko dla 32 bitowych) lub 67.

<matma> grupa multiplikatywna liczb modulo 37 i 67 jest
generowana przez 2<matma>
wiąc 2^n % 67 będą różnymi małymi liczbami.
Teraz potrzebna tylko mała tablica odszyfrowująca;-)

pzdr
bartekltg

do góry

W dniu 2015-08-31 o 21:58, szemrany pisze:
> Hejka,
>
> Mam liczbę 64 bit, traktuję ją jako tablicę bitów, zazwyczaj są w niej
> ustawione jakieś bity, ale czasem nie.
> Jak najszybciej znaleźć indeks ustawionego bitu?
> Wiem jak szybko sprawdzić czy zapalone są wszystkie lub żaden, ale jak
> odkryć, że "pali" się np. czterdziesty ósmy?
> Najprostsza jest pętla z przesuwaniem bitowym i testem skrajnego bitu, ale
> w najgorszym razie trzeba przeiterować 63 razy.
> Może da się szybciej?
> Może jakieś operacje arytmetyczne?
>

Nie bardzo wiem o co Ci chodzi :),
ale masz tu przykład funkcji, która zlicza ilość ustawionych bitów,
iterując tylko po ustawionych:

BYTE GetBitCount( UINT uiBits )
{
BYTE byCnt = 0;
while( uiBits )
{
++byCnt;

uiBits &= (uiBits - 1);
}

return byCnt;
}


Pozdr :)

do góry

On Tue, 1 Sep 2015 08:03:15 +0200, voy wrote:

>> Może jakieś operacje arytmetyczne?
>
> Nie bardzo wiem o co Ci chodzi :),
> ale masz tu przykład funkcji, która zlicza ilość ustawionych bitów,
> iterując tylko po ustawionych:

Ok, jeszcze raz, na liczbach 32 bitowych, żeby było prościej:

- mam np. liczbe 1234567890
- binarnie to jest 01001001100101100000001011010010
- chcę teraz wyliczyć/znaleźć indeks pierszego zapalonego bitu
- indeks liczę od prawej strony, jak wagi bitów
- wynik: 1 (indeks bazujący na 0)

drugi przykład:
- liczba np. 4255820448
- binarnie 11111101101010101010101010100000
- wynik 5

I jak pisałem w pierwszym poście, czego raczyłeś nie wziąć pod uwagę,
rozwiązanie bazujące na pętli odrzucam jako oczywiste i najprostsze.
Szukam innego, szybszego.

--
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

do góry