Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #27281 > unrolled thread

Szybkie szukanie ustawionego bitu

Back to article view | Back to pl.comp.programming

Contents

  Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-08-31 21:58 +0200
    Re: Szybkie szukanie ustawionego bitu Tomek Kańka <tom@tomkan.eu.org> - 2015-08-31 20:39 +0000
      Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-08-31 22:49 +0200
        Re: Szybkie szukanie ustawionego bitu Tomek Kańka <tom@tomkan.eu.org> - 2015-08-31 21:21 +0000
          Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-08-31 23:37 +0200
        Re: Szybkie szukanie ustawionego bitu bartekltg <bartekltg@gmail.com> - 2015-08-31 14:40 -0700
      Re: Szybkie szukanie ustawionego bitu "AK" <nobody@nowhere.com> - 2015-08-31 23:07 +0200
        Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-08-31 23:34 +0200
          Re: Szybkie szukanie ustawionego bitu "AK" <nobody@nowhere.com> - 2015-09-01 13:01 +0200
    Re: Szybkie szukanie ustawionego bitu voy <v_o_yNOSP@Mgazeta.pl> - 2015-09-01 08:03 +0200
      Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 10:31 +0200
        Re: Szybkie szukanie ustawionego bitu godek.maciek@gmail.com - 2015-09-01 01:45 -0700
    Re: Szybkie szukanie ustawionego bitu "M.M." <mmarszik@gmail.com> - 2015-09-01 02:57 -0700
      Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 12:23 +0200
    Re: Szybkie szukanie ustawionego bitu "Radoslaw Szwed" <radekszwed@pochta.fm> - 2015-09-01 12:30 +0200
      Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 13:04 +0200
        Re: Szybkie szukanie ustawionego bitu bartekltg <bartekltg@gmail.com> - 2015-09-01 13:37 +0200
          Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 14:29 +0200
            Re: Szybkie szukanie ustawionego bitu bartekltg <bartekltg@gmail.com> - 2015-09-01 16:10 +0200
              Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 17:28 +0200
    Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 14:40 +0200
      Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-01 22:20 +0200
        Re: Szybkie szukanie ustawionego bitu Wojciech Muła <wojtek.mula@gmail.com> - 2015-09-04 00:14 -0700
          Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-04 09:53 +0200
            Re: Szybkie szukanie ustawionego bitu Wojciech Muła <wojtek.mula@gmail.com> - 2015-09-04 08:01 -0700
              Re: Szybkie szukanie ustawionego bitu szemrany <szemrany@offline.off> - 2015-09-04 20:20 +0200
                Re: Szybkie szukanie ustawionego bitu "Radoslaw Szwed" <radekszwed@pochta.fm> - 2015-09-07 09:46 +0200

Page 1 of 2  [1] 2  Next page →

#27281 — Szybkie szukanie ustawionego bitu

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ę"

[toc] | [next] | [standalone]

#27282

szemrany <szemrany@offline.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

[toc] | [prev] | [next] | [standalone]

#27283

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ę"

[toc] | [prev] | [next] | [standalone]

#27285

szemrany <szemrany@offline.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

[toc] | [prev] | [next] | [standalone]

#27287

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ę"

[toc] | [prev] | [next] | [standalone]

#27288

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

[toc] | [prev] | [next] | [standalone]

#27284

Użytkownik "Tomek Kańka" <tom@tomkan.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

[toc] | [prev] | [next] | [standalone]

#27286

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ę"

[toc] | [prev] | [next] | [standalone]

#27299

Użytkownik "szemrany" <szemrany@offline.off> napisał:

> 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.

Szukaj polowkowo.

AK 


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

[toc] | [prev] | [next] | [standalone]

#27289

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 :)

[toc] | [prev] | [next] | [standalone]

#27293

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ę"

[toc] | [prev] | [next] | [standalone]

#27294

W dniu wtorek, 1 września 2015 10:31:11 UTC+2 użytkownik szemrany napisał:
> 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.

http://stackoverflow.com/questions/757059/position-of-least-significant-bit-that-is-set

[toc] | [prev] | [next] | [standalone]

#27296

On Monday, August 31, 2015 at 9:58:51 PM UTC+2, szemrany wrote:
> 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ę"

( x & ~(x-1) )

[toc] | [prev] | [next] | [standalone]

#27297

On Tue, 1 Sep 2015 02:57:01 -0700 (PDT), M.M. wrote:

> ( x & ~(x-1) )

Lub (x & -x ). To jest też w linku, który podał godek.
Ale to zwraca wartość bitu, a nie indeks, czyli problem przesuwania nadal
pozostaje.

-- 
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ę"

[toc] | [prev] | [next] | [standalone]

#27298

Użytkownik "szemrany" <szemrany@offline.off> napisał w wiadomości news:1i3y3j1aqrgzm.oc3pbikd1n92.dlg@40tude.net...
> 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?

Proponuję rozwiązanie sprzętowe za pomocą rozkazu BSR.
W rejestrze RAX umieszczamy liczbę do sprawdzenia np.:

mov    rax, 10000000b
bsr    rbx, rax

Po wykonaniu powyższych rozkazów w rejstrze RBX bedzie warość 7


Pozdrawiam
Radek
 

[toc] | [prev] | [next] | [standalone]

#27300

On Tue, 1 Sep 2015 12:30:28 +0200, Radoslaw Szwed wrote:

> mov    rax, 10000000b
> bsr    rbx, rax

Tylko, że rejest RAX wymaga x64, a ja kompiluję na 32 bity. Ale już ten
rozkaz też biorę pod uwagę i go w testach zastosuję do dwóch połówek po 32
bity.

-- 
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ę"

[toc] | [prev] | [next] | [standalone]

#27301

On 01.09.2015 13:04, szemrany wrote:
> On Tue, 1 Sep 2015 12:30:28 +0200, Radoslaw Szwed wrote:
>
>> mov    rax, 10000000b
>> bsr    rbx, rax
>
> Tylko, że rejest RAX wymaga x64, a ja kompiluję na 32 bity. Ale już ten
> rozkaz też biorę pod uwagę i go w testach zastosuję do dwóch połówek po 32
> bity.

Nie musisz używaś assemblera.

__builtin_ctz //gcc
_BitScanForward, _BitScanForward64   //VS

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#27302

On Tue, 01 Sep 2015 13:37:58 +0200, bartekltg wrote:

> Nie musisz używaś assemblera.
> 
> __builtin_ctz //gcc
> _BitScanForward, _BitScanForward64   //VS
> 
> pzdr
> bartekltg

Piszę w Delphi ;-)

-- 
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ę"

[toc] | [prev] | [next] | [standalone]

#27304

On 01.09.2015 14:29, szemrany wrote:
> On Tue, 01 Sep 2015 13:37:58 +0200, bartekltg wrote:
>
>> Nie musisz używaś assemblera.
>>
>> __builtin_ctz //gcc
>> _BitScanForward, _BitScanForward64   //VS
>>
>> pzdr
>> bartekltg
>
> Piszę w Delphi ;-)

Toto jeszcze żyje? ;-)

Freepascal ma tu wbudowane:
http://wiki.freepascal.org/FPC_New_Features_2.6.0#Bitscan_intrinsics

delphi prawdopodobnie też, ale trzeba poszukać w ichniejszej
dokumentacji... której na szybko nie wygoglalem;-)

Z tego co pamietam procedury w asm pisało się tam bardzo przyjemnie,
więc jak nie znajdziesz, zrób jak Radosław radzi i napisz samemu.
bsf/bsr dzialają tak samo na 32 bitach, trzeba tylko pamitać,
w czym przychodzi zmienna i gdzie umieścić wynik.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#27306

On Tue, 01 Sep 2015 16:10:46 +0200, bartekltg wrote:

>> Piszę w Delphi ;-)
> 
> Toto jeszcze żyje? ;-)

I ma się całkiem dobrze, poza ceną :/
 
> delphi prawdopodobnie też, ale trzeba poszukać w ichniejszej
> dokumentacji... której na szybko nie wygoglalem;-)

Nie spotkałem się i na 90% nie ma, ale sobie jeszcze zobacze jak to we FPC
zrobili.
 
> Z tego co pamietam procedury w asm pisało się tam bardzo przyjemnie,
> więc jak nie znajdziesz, zrób jak Radosław radzi i napisz samemu.
> bsf/bsr dzialają tak samo na 32 bitach, trzeba tylko pamitać,
> w czym przychodzi zmienna i gdzie umieścić wynik.

1,5h przed Twoim postem pisałem, że to już zrobiłem, w asmie też ;-)

-- 
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ę"

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | pl.comp.programming

csiph-web