-
X-Received: by 10.182.225.134 with SMTP id rk6mr205107obc.27.1441057258846; Mon, 31
Aug 2015 14:40:58 -0700 (PDT)
X-Received: by 10.182.225.134 with SMTP id rk6mr205107obc.27.1441057258846; Mon, 31
Aug 2015 14:40:58 -0700 (PDT)
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!news.cyf-kr.edu.pl!news.nask
.pl!news.nask.org.pl!news.unit0.net!news.glorb.com!i7no515620igu.0!news-out.goo
gle.com!nt1ni20616igb.0!nntp.google.com!uu8no1031115igb.0!postnews.google.com!g
legroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: pl.comp.programming
Date: Mon, 31 Aug 2015 14:40:58 -0700 (PDT)
In-Reply-To: <v13fst2yrtuh$.1su3vdc690vq2.dlg@40tude.net>
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=89.73.81.145;
posting-account=CvUQzQoAAABvVQmR58QmR6N4Cev1qhAS
NNTP-Posting-Host: 89.73.81.145
References: <1...@4...net>
<s...@t...dom.local>
<v13fst2yrtuh$.1su3vdc690vq2.dlg@40tude.net>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <d...@g...com>
Subject: Re: Szybkie szukanie ustawionego bitu
From: bartekltg <b...@g...com>
Injection-Date: Mon, 31 Aug 2015 21:40:58 +0000
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: quoted-printable
Xref: news-archive.icm.edu.pl pl.comp.programming:208086
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 01.09.15 08:03 voy
- 01.09.15 10:31 szemrany
- 01.09.15 10:45 g...@g...com
- 01.09.15 11:57 M.M.
- 01.09.15 12:23 szemrany
- 01.09.15 12:30 Radoslaw Szwed
- 01.09.15 13:01 AK
- 01.09.15 13:04 szemrany
- 01.09.15 13:37 bartekltg
- 01.09.15 14:29 szemrany
- 01.09.15 14:40 szemrany
- 01.09.15 16:10 bartekltg
- 01.09.15 17:28 szemrany
- 01.09.15 22:20 szemrany
- 04.09.15 09:14 Wojciech Muła
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-28 Przednia lampka rowerowa Basta / AXA pod dynamo w piaście
- 2024-05-28 Boję siię capa...
- 2024-05-24 Efekt gitarowy koda kd-30 trash metal
- 2024-05-27 Re: Efekt gitarowy koda kd-30 trash metal
- 2024-05-27 Wykrywanie przerwy w długim przewodzie zakopanym w ziemi.
- 2024-05-27 PT500
- 2024-05-28 Łódź => SAP CO Consultant <=
- 2024-05-28 Białystok => Senior Developer React Native <=
- 2024-05-28 Kraków => Mid/Senior QA Engineer <=
- 2024-05-28 Wrocław => Key Account Manager <=
- 2024-05-28 Białystok => ERP Implementer <=
- 2024-05-28 => Solution Architect (secure communication and IoT solutions) <=
- 2024-05-28 Warszawa => Staż w dziale Sprzedaży B2B (2 miejsca) <=
- 2024-05-28 Szczecin => Realtime (C) Software Developer <=
- 2024-05-27 Warszawa => Senior Account Manager (stacjonarnie) <=