🚀 go-pugleaf

Dnia Thu, 14 Sep 2006 18:54:23 +0000, Sektor van Skijlen napisał(a):

> To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> STAŁYM CZASIE.
> 
> Powtarzam: zrobienie tego może być niemożliwe. Ale chciałbym wiedzieć, czy da
> się to udowodnić, że się nie da, a nie że po prostu wszyscy się poddali :)

Powiedz, które z tych operacji uznajesz za O(1) dla danych ciągów maski i
wartości.
AND logiczny, przesunięcie bitowe, porównanie (arytmetyczne)

Przy pewnych założeniach można to zrobić O(1), ale problem sprecyzowałeś
na tyle abstrakcyjnie, że podejrzewam iż ciągi bitów są dowolnie długie,
znaczy ich rozmiar jest O(N)

Tak na szybko przyszło mi do głowy coś takiego, ale to zakłada powyższe i
ogólnie jestem przemęczony wiec pewnie się zaraz znajdzie przypadek, dla
którego nie działa ;)

return ((wartosc & maska) > (wartosc>>1) )

Pozdrawiam
-- 
Tomek 'QsoRiX' Rydzyński   Linux Registered User #178082
http://rtfm.killfile.pl/   http://apcoln.linuxpl.org/

["Followup-To:" header set to pl.comp.lang.c.]
Sektor van Skijlen wrote:
> Czyli, ogólniej: pierwszy bit od lewej strony, który ma wartość 1 jest bitem
> charakterystycznym. Pozostałe bity od niego w prawo mogą mieć dowolne
> wartości.
>
> Ok, a teraz co należy zrobić: napisać funkcję, która przyjmie jako argumenty
> wartość oraz maskę i zwróci true lub false określające, czy bit
> charakterystyczny wartości zawiera się w masce.
>
> To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> STAŁYM CZASIE.

[przepraszam, jeśli za bardzo wchodzę w złożoność asymptotyczną]

W stałym względem czego? Liczby bitów?

Jeśli liczba bitów jest dowolna i względem niej mierzymy złożoność
algorytmu, wtedy naturalne jest przyjęcie, że operacje na wektorach
bitów (AND, OR, XOR, NOT) działają w czasie liniowym względem liczby
bitów (czyli operacje jednostkowe dotyczą pojedynczych bitów). Wtedy
Twoje zadanie nie ma rozwiązania.

Jeśli mamy stałe górne ograniczenie na liczbę bitów, to dowolny sensowny
algorytm działa w czasie stałym. Wtedy zadanie jest trywialne.

Pozostała jeszcze ostatnia, trochę dziwna możliwosć, w której mierzymy
złożoność obliczeniową względem liczby bitów, która nie jest ograniczona,
ale traktujemy operacje na wektorach bitów jako jednostkowe. Wtedy to
zadanie może być ciekawe.

Prawdopodobnie chodzi Ci o ostatnią opcję, w wydaniu trochę bardziej
praktycznym, tzn. chciałbyś, żeby niezależnie od liczby bitów dało się
to zrobić przy użyciu kilku instrukcji maszynowych.

Zacząłbym od czegoś takiego:

    2 * (wartość & maska) > wartość

(to jest najprawdopodobniej błędne, ale może widać pomysł).

Pozdrawiam
Tomek

"Sektor van Skijlen" <ethouris@guess.if.gmail.com.is.valid.or.invalid>
wrote:

[...]

> Ok, a teraz co należy zrobić: napisać funkcję, która przyjmie jako
> argumenty wartość oraz maskę i zwróci true lub false określające, czy bit
> charakterystyczny wartości zawiera się w masce.
>
> To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> STAŁYM CZASIE.

O ile dobrze zrozumialem - nie jest mozliwe.

Ten problem jest rownowazny ffs. Z uwagi na przydatnosc, na niektorych
architekturach byl nawet implementowany hardware'owo.


mp

On Thu, 14 Sep 2006 18:54:23 +0000 (UTC), Sektor van Skijlen
<ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:
 
>To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
>STAŁYM CZASIE.

Co to znaczy "stalym czasie"?... Wzgledem czego?...

A.L.

Michal Przybylek wrote:
> "Sektor van Skijlen" <ethouris@guess.if.gmail.com.is.valid.or.invalid>
> wrote:
>
> [...]
>
>> Ok, a teraz co należy zrobić: napisać funkcję, która przyjmie jako
>> argumenty wartość oraz maskę i zwróci true lub false określające, czy bit
>> charakterystyczny wartości zawiera się w masce.
>>
>> To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
>> STAŁYM CZASIE.
>
> O ile dobrze zrozumialem - nie jest mozliwe.
>
> Ten problem jest rownowazny ffs.

Niezupełnie, nie musisz podawać indeksu pierwszego zapalonego bitu :-)

Sprawdziłem moje rozwiązanie - wydaje się działać (chyba, że ja źle
zrozumiałem zadanie). Możliwe, że wysłałem je tylko do pl.comp.lang.c.

Pozdrawiam
Tomasz

Tomasz Zielonka wrote:
> Sprawdziłem moje rozwiązanie - wydaje się działać (chyba, że ja źle
> zrozumiałem zadanie). Możliwe, że wysłałem je tylko do pl.comp.lang.c.

Rozwiązanie

    2 * (value .&. mask) > value

oczywiście nie działa w przypadku, kiedy dochodzi do przekroczenia
zakresu na skutek mnożenia. Trzeba by to jeszcze zabezpieczyć oddzielnym
sprawdzeniem najstarszych bitów.

PS. No i nadal nie wiemy, czy o to chodziło Sektorowi...

Pozdrawiam
Tomasz

Tomasz Zielonka wrote:
>     2 * (value .&. mask) > value

Oops, wyskoczyłem z Haskellem na grupie o C ;-)
Powinno być:

    2 * (value & mask) > value

Best regards
Tomasz

"Tomasz Zielonka" <tomasz.zielonka@gmail.com> wrote:

> > O ile dobrze zrozumialem - nie jest mozliwe.
> >
> > Ten problem jest rownowazny ffs.
>
> Niezupełnie, nie musisz podawać indeksu pierwszego
> zapalonego bitu :-)

Faktycznie. Ale Ty tez chyba masz blad :-)

> Sprawdziłem moje rozwiązanie - wydaje się działać

Wezmy:

v = 1100...

i maski

p = 1000...
q = 0000...


mp

Na pl.comp.lang.c "Tomek RydzyĹ?ski" skrobie:
> Dnia Thu, 14 Sep 2006 18:54:23 +0000, Sektor van Skijlen napisał(a):

> > To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> > STAŁYM CZASIE.
> > 
> > Powtarzam: zrobienie tego może być niemożliwe. Ale chciałbym wiedzieć, czy da
> > się to udowodnić, że się nie da, a nie że po prostu wszyscy się poddali :)

> Powiedz, które z tych operacji uznajesz za O(1) dla danych ciągów maski i
> wartości.
> AND logiczny, przesunięcie bitowe, porównanie (arytmetyczne)

Obojętnie. W sensie, że O(N) oznaczałoby, że, powiedzmy, operacja ma złożoność
zależną od tego, który to od lewej bit jest bitem charakterystycznym.

> Przy pewnych założeniach można to zrobić O(1), ale problem sprecyzowałeś
> na tyle abstrakcyjnie, że podejrzewam iż ciągi bitów są dowolnie długie,
> znaczy ich rozmiar jest O(N)

Zrobienie tego w O(N) jest proste - przesuwasz po kolei bity wartości w lewo
(wraz z maską), a jak trafisz na ustawiony bit w wartości, to sprawdzasz
wtedy tylko najstarszy bit w masce, ewentualnie cyklicznie inkrementujesz
licznik i tworzysz następnie wartość z jednym bitem przez przesunięcie
najstarszego bitu o wartość licznika i to maczujesz z maską.

> Tak na szybko przyszło mi do głowy coś takiego, ale to zakłada powyższe i
> ogólnie jestem przemęczony wiec pewnie się zaraz znajdzie przypadek, dla
> którego nie działa ;)

> return ((wartosc & maska) > (wartosc>>1) )

Mnie to też dokładnie przyszło do głowy "na szybko", ale to niestety nie
działa.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Na pl.comp.lang.c Michal Przybylek skrobie:
> "Sektor van Skijlen" <ethouris@guess.if.gmail.com.is.valid.or.invalid>
> wrote:

> [...]

> > Ok, a teraz co należy zrobić: napisać funkcję, która przyjmie jako
> > argumenty wartość oraz maskę i zwróci true lub false określające, czy bit
> > charakterystyczny wartości zawiera się w masce.
> >
> > To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> > STAŁYM CZASIE.

> O ile dobrze zrozumialem - nie jest mozliwe.

> Ten problem jest rownowazny ffs. Z uwagi na przydatnosc, na niektorych
> architekturach byl nawet implementowany hardware'owo.

W sensie, szukanie pierwszego ustawionego bitu i zwracanie pozycji, na której
się znajduje? Kojarzę coś takiego, ale to jest bardzo architecture-specific.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

"Michal Przybylek" <mrp@neostrada.pl> wrote:

> > Niezupełnie, nie musisz podawać indeksu pierwszego
> > zapalonego bitu :-)
>
> Faktycznie. Ale Ty tez chyba masz blad :-)

Zreszta tak czy inaczej wydaje mi sie, ze mozna latwo udowodnic, ze dolne
ograniczenie jest rzedu O(lg(n)). Wyglada na to, ze wystarczy rozwazac maski
jednobitowe i argumentacja bedzie podobna jak przy dolnym ograniczeniu na
sortowanie (przy czym technicznie bardziej skomplikowana, bo mamy wiecej
operacji).

Ale jestem zbyt zmeczony aby powiedziec cos ntt. dzisiaj "na pewno" :-)


mp

On Thu, 14 Sep 2006 22:25:25 +0200, "Michal Przybylek"
<mrp@neostrada.pl> wrote:

>"Michal Przybylek" <mrp@neostrada.pl> wrote:
>
>> > Niezupełnie, nie musisz podawać indeksu pierwszego
>> > zapalonego bitu :-)
>>
>> Faktycznie. Ale Ty tez chyba masz blad :-)
>
>Zreszta tak czy inaczej wydaje mi sie, ze mozna latwo udowodnic, ze dolne
>ograniczenie jest rzedu O(lg(n)). Wyglada na to, ze wystarczy rozwazac maski
>jednobitowe i argumentacja bedzie podobna jak przy dolnym ograniczeniu na
>sortowanie (przy czym technicznie bardziej skomplikowana, bo mamy wiecej
>operacji).
>
>Ale jestem zbyt zmeczony aby powiedziec cos ntt. dzisiaj "na pewno" :-)
>

Panie Przybylek, Pan na pewno jest zmeczony, ale Pan Sektor ejszcze
bardziej. Inaczej zadalby pytanie tak aby mialo sens. On sie nei
pytal o DOLNE OGRANICZENIE. On sie pytal o STALY CZAS. Staly czas
nei wiadomo ze wzgledu na co - czy liczbe bitow, czy polozenie "bitu
charakterystycznego". On sie nie pytal o MINIMALNY CZAS. Wiec niech
sie zdecyduje o co wlasciwie pyta, bo inaczej wszystkei odpowiedzi
nie maja sensu.

A.L>

Na pl.comp.lang.c Tomasz Zielonka skrobie:
> Tomasz Zielonka wrote:
> >     2 * (value .&. mask) > value

> Oops, wyskoczyłem z Haskellem na grupie o C ;-)
> Powinno być:

>     2 * (value & mask) > value

Ok, widzę, że po prostu za szybko się poddałem. :)

Nie potrafię udowodnić, że działa, ale wystarczyło mi, że sprawdziłem warunki
brzegowe. :)

No kurde, wiszę ci co najmniej kilka piw :)



-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Możesz wykorzystać sposób taki:
x - liczba którą chcesz przyrównać do maski;

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
wynik = (x - (x >> 1)) & maska;

Lub wynik = (1 << (31 - nlz(x))) & maska,
gdzie nlz to liczba wiodących zer. Coś mi się wydawało że jest w
liście rozkazów procesora x86 więc też jest w czasie stałym. Ale
nie mogę teraz znaleźć więc być może coś mi się pomyliło -
asemblerowiec ze mnie kiepski.

W każdym razie rozwiązanie nr. jeden jest w czasie stałym i chyba
spełnia założenia :)

Na pl.comp.lang.c A.L. skrobie:
> On Thu, 14 Sep 2006 18:54:23 +0000 (UTC), Sektor van Skijlen
> <ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:
>  
> >To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> >STAŁYM CZASIE.

> Co to znaczy "stalym czasie"?... Wzgledem czego?...

Względem numeru kolejnego bitu charakterystycznego licząc od lewej.

Najprostsza implementacja polega na tym, że przesuwa się bity po jednym w
lewo, aż na pierwszej od lewej pozycji będzie ustawiony bit. Licznik pokaże
wtedy, który w kolei od lewej bit jest tym bitem charakterystycznym.

Cóż, z jednej strony, nie ma co mówić, dałem plamę. Z drugiej, jak pytałem
znajomych (w tym również jednego bardzo zapalonego "algorytmika"!), to nikomu
nie chciało się ruszyć głową.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

"Michal Przybylek" <mrp@neostrada.pl> wrote:

> Wezmy:
> 
> v = 1100...
> 
> i maski
> 
> p = 1000...
> q = 0000...

Grr...

q = 0100...


mp

On Thu, 14 Sep 2006 20:47:15 +0000 (UTC), Sektor van Skijlen
<ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:

>Na pl.comp.lang.c A.L. skrobie:
>> On Thu, 14 Sep 2006 18:54:23 +0000 (UTC), Sektor van Skijlen
>> <ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:
>>  
>> >To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
>> >STAŁYM CZASIE.
>
>> Co to znaczy "stalym czasie"?... Wzgledem czego?...
>
>Względem numeru kolejnego bitu charakterystycznego licząc od lewej.
>
>Najprostsza implementacja polega na tym, że przesuwa się bity po jednym w
>lewo, aż na pierwszej od lewej pozycji będzie ustawiony bit. Licznik pokaże
>wtedy, który w kolei od lewej bit jest tym bitem charakterystycznym.

W dalszym ciagu cos nie klapuje z postawieniem problemu. Wystarczy
przesuwac WSZYSTKIE bity slowa i nei zatrzymywac sie po pierwszym
zapalonym bicie a tylko zapamietac jego pozycje. Czas bedzie taki
sam niezaleznie od polozenia bitu. Czy o to chodzilo?...

A.L.

"A.L." <alewando@fala2005.com> wrote:

> Panie Przybylek, Pan na pewno jest zmeczony, ale Pan Sektor
> ejszcze bardziej. Inaczej zadalby pytanie tak aby mialo sens.
> On sie nei pytal o DOLNE OGRANICZENIE. On sie pytal
> o STALY CZAS. Staly czas nei wiadomo ze wzgledu na co
> - czy liczbe bitow, czy polozenie "bitu charakterystycznego".
> On sie nie pytal o MINIMALNY CZAS. Wiec niech
> sie zdecyduje o co wlasciwie pyta, bo inaczej wszystkei odpowiedzi
> nie maja sensu.

Nie, no jasne, ze pytanie jest bez sensu. I nawet nie chodzi tyle o
powiedzenie wzgledem czego mierzymy zlozonosc, ale sprecyzowaniem samego
modelu (jakie operacje mamy dostepne i o jakich kosztach).

Ale nie kazdy jest w stanie mowic precyzyjnie i nie kazdy jest w pelni
swiadomym tego o czym mowi. Czesto brakuje ludziom nawet odpowiedniego
jezyka do mowienia.

Ja mysle o takim problemie raczej jako tylko o pewnej idei, zas o
rozwiazaniu problemu, jak o pytaniu "co mozna ciekawego powiedziec o X w
odniesieniu do Y".


mp

Wydaje mi się, że praktyczne i ścisłe sformułowanie tego problemu
powinno wyglądać tak: liczba bitów jest duża i chcemy wykonać stałą
liczbę operacji z pewnego zbioru.

Te operacje to &, >>, ==, < itd. na ciągach bitów długości wejścia
do zadania, mamy do dyspozycji stałe ...0000 i ...0001. To jest szkic
zbioru operacji, można go doprecyzować.

Nie przejmujemy się, że każda z tych operacji wymaga przejrzenia
liniowej liczby bitów, żeby ją zrealizować za pomocą prawdziwie
elementarnych czynności działających na pojedynczych bitach.
Mierzymy tylko liczbę operacji.

Trudno formułować oryginalny cel językiem asymptotycznej złożoności.
Faktycznie nie chodzi bowiem o asymptotyczną złożoność, tylko o to,
że bitów jest np. 32 (stała, ale znacząca), pewne operacje działajace
hurtem na paczkach 32 bitów mamy (np. &), a innych, które w zasadzie
powinny mieć tę samą złożoność, nie mamy (np. znalezienie najstarszego
zapalonego bitu) i chcemy, żeby wykonanych operacji było kilka, a nie
trzydzieści kilka.

-- 
   __("<         Marcin Kowalczyk
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Na pl.comp.objects A.L. skrobie:
> On Thu, 14 Sep 2006 20:47:15 +0000 (UTC), Sektor van Skijlen
> <ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:

> >Na pl.comp.lang.c A.L. skrobie:
> >> On Thu, 14 Sep 2006 18:54:23 +0000 (UTC), Sektor van Skijlen
> >> <ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:
> >>  
> >> >To jest oczywiście wciąż jeszcze proste, więc teraz coś trudniejszego: W
> >> >STAŁYM CZASIE.
> >
> >> Co to znaczy "stalym czasie"?... Wzgledem czego?...
> >
> >Względem numeru kolejnego bitu charakterystycznego licząc od lewej.
> >
> >Najprostsza implementacja polega na tym, że przesuwa się bity po jednym w
> >lewo, aż na pierwszej od lewej pozycji będzie ustawiony bit. Licznik pokaże
> >wtedy, który w kolei od lewej bit jest tym bitem charakterystycznym.

> W dalszym ciagu cos nie klapuje z postawieniem problemu. Wystarczy
> przesuwac WSZYSTKIE bity slowa i nei zatrzymywac sie po pierwszym
> zapalonym bicie a tylko zapamietac jego pozycje.

Jeśli dla pana określenie "... aż na pierwszej od lewej pozycji będzie
ustawiony bit" oznacza, że "nie należy zatrzymywać się po pierwszym zapalonym
bicie", to szczerze panu gratuluję logicznego rozumowania.

> Czas bedzie taki
> sam niezaleznie od polozenia bitu. Czy o to chodzilo?...

Nie, panie AL, nie o to chodziło.

"Bąbelkowa" wersja tego algorytmu polega na tym, że wykonujemy w pętli
przesunięcia bitowe w lewo dotąd aż albo w pierwszym bicie od lewej będzie
wartość 1, albo przesuwanie się w lewo przekroczyło rozmiar bitsetu, przy czym
drugie można praktycznie pominąć, bo zakładamy, że co najmniej jeden bit jest
w wartości sprawdzanej ustawiony.

Ilość iteracji będzie zatem ściśle zależna od tego, na której pozycji znajduje
się pierwszy od lewej ustawiony bit.

Rozumiem, że dla pana pewnie jeśli algorytm ma za zadanie pracować tylko dla
zadanego maksymalnego N, to w takim razie do osiągnięcia złożoności O(1)
wystarczy, aby wykonywał zawsze N iteracji niezależnie od tego, ile ich
rzeczywiście potrzeba. Ale, wybaczy pan, to jest computer science, a nie
computer engineering.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

On Thu, 14 Sep 2006 23:02:41 +0000 (UTC), Sektor van Skijlen
<ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:
 
>Nie, panie AL, nie o to chodziło.
>
>"Bąbelkowa" wersja tego algorytmu polega na tym, że wykonujemy w pętli
>przesunięcia bitowe w lewo dotąd aż albo w pierwszym bicie od lewej będzie
>wartość 1, albo przesuwanie się w lewo przekroczyło rozmiar bitsetu, przy czym
>drugie można praktycznie pominąć, bo zakładamy, że co najmniej jeden bit jest
>w wartości sprawdzanej ustawiony.
>
>Ilość iteracji będzie zatem ściśle zależna od tego, na której pozycji znajduje
>się pierwszy od lewej ustawiony bit.
>
>Rozumiem, że dla pana pewnie jeśli algorytm ma za zadanie pracować tylko dla
>zadanego maksymalnego N, to w takim razie do osiągnięcia złożoności O(1)
>wystarczy, aby wykonywał zawsze N iteracji niezależnie od tego, ile ich
>rzeczywiście potrzeba. Ale, wybaczy pan, to jest computer science, a nie
>computer engineering.

Nei wiedzialem ze Pan scientysta.. Ale w dalszym czigu Pan nie
postawil problemu prawidlowo. Widac jednak Pan izynier.

A.L.

Sektor van Skijlen wrote:

> Na pl.comp.lang.c Tomasz Zielonka skrobie:
>> Tomasz Zielonka wrote:
>>>     2 * (value .&. mask) > value
> 
>> Oops, wyskoczyłem z Haskellem na grupie o C ;-)
>> Powinno być:
> 
>>     2 * (value & mask) > value
> 
> Ok, widzę, że po prostu za szybko się poddałem. :)
> 
> Nie potrafię udowodnić, że działa, ale wystarczyło mi, że sprawdziłem warunki
> brzegowe. :)

Dowód jest banalny, szkoda nawet przytaczać.

Zastanawiam się jednak, czy aby na pewno właściwie sprawdziłeś warunki 
brzegowe, ot np. dla: value = mask = 2^32 wynik będzie błędny 
(zakładając, że maksymalna ilość bitów to 32).

Wygodniej przekształcić rozwiązanie do postaci:

    (value & mask) > (value >> 1)

wtedy to już tylko znaki mogą zamieszać, ale to już inny problem...


piotr

Rafał Rawicki wrote:

> Możesz wykorzystać sposób taki:
> x - liczba którą chcesz przyrównać do maski;
> 
> x = x | (x >> 1);
> x = x | (x >> 2);
> x = x | (x >> 4);
> x = x | (x >> 8);
> x = x | (x >> 16);
> wynik = (x - (x >> 1)) & maska;

Tu warto dodać: Hacker's Delight, Figure 3-1. :)

Rozwiązanie podane przez Tomasza Zielonkę jest jednak 1) bardziej 
uniwersalne ("słowo" może być dowolnej długości), 2) podejrzewam, że 
zwykle wydajniejsze.

Można tu już jednak o znak się nie martwić.


piotr

Sektor van Skijlen wrote:
> Na pl.comp.lang.c Tomasz Zielonka skrobie:
>>     2 * (value & mask) > value
>
> Ok, widzę, że po prostu za szybko się poddałem. :)

Dla kompletności, oto pełne rozwiązanie w C++:

template <typename UnsignedIntegral>
bool check(UnsignedIntegral mask, UnsignedIntegral value)
{
    const int highestBit = 1 << (std::numeric_limits<UnsignedIntegral>::digits - 1);
    return
        (value & highestBit)
            ? (mask & highestBit)
            : (((value & mask) << 1) > value);
}

Ze względu na porównanie, działa tylko dla typów bez znaku.

> Nie potrafię udowodnić, że działa, ale wystarczyło mi, że sprawdziłem warunki
> brzegowe. :)

Ja sprawdziłem wszystkie kombinacje dla uint8_t. Można by się pokusić na
dowód.

> No kurde, wiszę ci co najmniej kilka piw :)

O, jak miło :-)
Bywasz czasem w Warszawie?

Pozdrawiam
Tomek

Michal Przybylek wrote:
> Faktycznie. Ale Ty tez chyba masz blad :-)
>
> Wezmy:
>
> v = 1100...
>
> i maski
>
> p = 1000...
> q = 0000...

Tak, na początku o tym nie pomyślałem.
Obecna wersja już to obsługuje.

A tak w ogóle na początku to chciałem napisać, że się nie da :-)

Pozdrawiam
Tomasz

Tomasz Zielonka wrote:

> Sektor van Skijlen wrote:
>> Na pl.comp.lang.c Tomasz Zielonka skrobie:
>>>     2 * (value & mask) > value
>> Ok, widzę, że po prostu za szybko się poddałem. :)
> 
> Dla kompletności, oto pełne rozwiązanie w C++:
> 
> template <typename UnsignedIntegral>
> bool check(UnsignedIntegral mask, UnsignedIntegral value)
> {
>     const int highestBit = 1 << (std::numeric_limits<UnsignedIntegral>::digits - 1);
>     return
>         (value & highestBit)
>             ? (mask & highestBit)
>             : (((value & mask) << 1) > value);
> }
> 
> Ze względu na porównanie, działa tylko dla typów bez znaku.

Aleś popsuł... ;)

Po pierwsze, 'digits' niekoniecznie musi być "stałe w czasie". Ale, co 
najważniejsze, może być też 0. W konsekwencji możesz mieć '1 << -1'. A w 
papierach do C++ odnośnie shiftów stoi tak:

"(...) The behavior is undefined if the right operand is negative, or 
greater than or equal to the length in bits of the promoted left operand"

Po drugie, jeśli już postanowiłeś wyznaczyć 'highestBit' (pomijając tego 
złożoność), to rozwiązanie masz natychmiast takie:

     return (mask & highestBit);


Nie wiem też po co tak kombinujesz, skoro poprawną w każdej dziedzinie 
unsinged modyfikację Twojego rozwiązania masz w moim wcześniejszym 
poście, którą dla wygody czytelnika powtórzę:

     return (value & mask) > (value >> 1);

> 
>> Nie potrafię udowodnić, że działa, ale wystarczyło mi, że sprawdziłem warunki
>> brzegowe. :)
> 
> Ja sprawdziłem wszystkie kombinacje dla uint8_t.

W ten sposób niestety, ale z Twoim ostatnim rozwiązaniem nigdy pewności 
nie będzie, nawet jak sprawdzisz to na wszystkich dostępnych 
kompilatorach C++. Takie to już niestety piękno tkwi w "results are 
undefined"...

> Można by się pokusić na
> dowód.

Podpowiem, że w mojej modyfikacji wystarczy dowieść, że:

   (y >= x) => (y > x/2) | (y = 0).

dla każdego x i y z dziedziny unsigned.


piotr

PS.

Przepraszam, że z FUT wciąż wyrzucam pl.comp.objects, powody to 1) 
gazeta.pl nie pozwala na więcej niż 2 FUTy, 2) z obiektowością wspólnego 
ma to IMHO nic.

Piotr Kobzda wrote:
> Tomasz Zielonka wrote:

[...]

> Aleś popsuł... ;)

Ech. Twoje rozwiązanie jest jednak poprawne.
Nie przyjrzałem się dokładnie.

Gdy snu mało, zaczyna się widzieć, nie to co widać, ale co chce się 
widzieć... :))
Sorry za zamieszanie. :)


piotr

bez obrotow sie nie obejdzie:

int fun(int v, int m) {
int i, n, nr, nv, ig1, ig2;

         ig1 = 1;
         for(i=15; i>-1; i--) {
                 n = v & (1 << i);
                 if(n && ig1) {
                         nr = i;
                         ig1 = 0;
                 } else {
                         nv = i;         //time dep.
                         ig2 = 0;
                 }
         }
         return m & (1 << nr);
}


Z tym stalym czasem to i tak sie w 100 % nie da. Przy 16 bitach 
zchodzimy do poziomu pojedynczych instukcji procesora, a tu trzeba by 
wylaczyc caly OS wraz z mulitaskingiem , MMU , cache i jednostke
predykcji skokow i przejsc na asembler (analizujac szczegolowa w ktory 
potok trafia instrukcja).
Z drugiej strony w asm mamy do dyskozycji instrukcje bt (bit test) ktora 
upraszcza sprawe.


pozdrawiam

Marek

"Rafał Rawicki" <rawicki@gmail.com> writes:

> Lub wynik = (1 << (31 - nlz(x))) & maska,
> gdzie nlz to liczba wiodących zer. Coś mi się wydawało że jest w
> liście rozkazów procesora x86 więc też jest w czasie stałym.

BSR - Bit Scan Reverse. Zwraca numer ustawionego bitu licząc, że bit
najmniej znaczący ma numer 0. Instrukcja wprwoadzona została
w 80386. Zatem:

#v+
check   PROC
ARG     wartosc:WORD, maska:WORD
        push cx
        mov  ax, [wartosc]
        bsr  cx, ax
        and  ax, [maska]
        shr  ax, cl
        pop  cx
        ret
check   ENDP

check32 PROC
ARG     wartosc:DWORD, maska:DWORD
        push cx
        mov  eax, [wartosc]
        bsr  cx, eax
        and  eax, [maska]
        shr  eax, cl
        pop  cx
        ret
check32 ENDP
#v-

Rzecz jasna o ile pamiętam jeszcze jak się programuje w Assemblerze. ;)


-- 
Pozdrawiam                                            _     _
 .o. | Wasal Jasnie Oswieconej Pani Informatyki     o' \,=./ `o
 ..o | Michal "mina86" Nazarewicz  <mina86*tlen.pl>    (o o)
 ooo +--<jid:mina86*jabber.org>---<tlen:mina86>----ooO--(_)--Ooo--

Na pl.comp.lang.c Tomasz Zielonka skrobie:
> Sektor van Skijlen wrote:
> > Na pl.comp.lang.c Tomasz Zielonka skrobie:
> >>     2 * (value & mask) > value
> >
> > Ok, widzę, że po prostu za szybko się poddałem. :)

> Dla kompletności, oto pełne rozwiązanie w C++:

E, po co. Przecież powiedziałem jasno - ja u siebie będę stosował dokładnie 16
bitów na identyfikator i maskę. Wystarczy mi więc wykonać operację na uint16_t.

Nie jest mi potrzebne generyczne rozwiązanie, tylko specjalizowane dla
konkretnego zastosowania. Nie przewiduję rozbudowy maski do 32 bitów, bo
aktualnie nie jestem w stanie zapełnić nawet 16 kategorii. I nie zanosi się,
żeby istniała potrzeba dodawania nowych kategorii zdarzeń, bo to jest GUI, a
co za tym idzie, jest ściśle związane z urządzeniami sterującymi komputera
(myszka, klawiatura itp. bajery) i nawet jeśli kiedyś pojawi się jakieś nowe,
to i tak najczęściej zdarzenia przysyłane przez te sprzęty będzie można
podpiąć pod jakąś istniejącą kategorię.

> > No kurde, wiszę ci co najmniej kilka piw :)

> O, jak miło :-)
> Bywasz czasem w Warszawie?

Bywam, najczęściej w weekendy. Emaila masz w sygnnaturce.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Na pl.comp.lang.c A.L. skrobie:
> >Rozumiem, że dla pana pewnie jeśli algorytm ma za zadanie pracować tylko dla
> >zadanego maksymalnego N, to w takim razie do osiągnięcia złożoności O(1)
> >wystarczy, aby wykonywał zawsze N iteracji niezależnie od tego, ile ich
> >rzeczywiście potrzeba. Ale, wybaczy pan, to jest computer science, a nie
> >computer engineering.

> Nei wiedzialem ze Pan scientysta.. Ale w dalszym czigu Pan nie
> postawil problemu prawidlowo. Widac jednak Pan izynier.

Owszem. I, jak inżynier, dążę najprostszą metodą do rozwiązania problemu, a
nie wyszukiwania wszystkich możliwych problemów.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

On Sun, 17 Sep 2006 22:28:14 +0000 (UTC), Sektor van Skijlen
<ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:

>Na pl.comp.lang.c A.L. skrobie:
>> >Rozumiem, że dla pana pewnie jeśli algorytm ma za zadanie pracować tylko dla
>> >zadanego maksymalnego N, to w takim razie do osiągnięcia złożoności O(1)
>> >wystarczy, aby wykonywał zawsze N iteracji niezależnie od tego, ile ich
>> >rzeczywiście potrzeba. Ale, wybaczy pan, to jest computer science, a nie
>> >computer engineering.
>
>> Nei wiedzialem ze Pan scientysta.. Ale w dalszym czigu Pan nie
>> postawil problemu prawidlowo. Widac jednak Pan izynier.
>
>Owszem. I, jak inżynier, dążę najprostszą metodą do rozwiązania problemu, a
>nie wyszukiwania wszystkich możliwych problemów.

Inzynier z Pana tez do kitu. Powinien Pan postawic problem
nastepujaco: "znalezc algorytm ktory bedzie rowiazywal zadanie
stosujac minimalna liczbe operacji (i tu Pan powinien napisac ktore
operacje sa najbardziej kosztowne i ich ilosc powinna byc
minimalizowana) ktora to ilosc operacji bedzie niezalezna od
polozenaia bitu charakterystycznego

Inaczej ja moge Panu zaproponowac algorytm ktory bedzie mial stala
liczbe JAKISCH operacji, albo bedzie sie wykonywal dokaldnie 47
minut dla dowolnego polozenia bitu charakterystycznego.

A.L.

Na pl.comp.lang.c A.L. skrobie:
> On Sun, 17 Sep 2006 22:28:14 +0000 (UTC), Sektor van Skijlen
> <ethouris@guess.if.gmail.com.is.valid.or.invalid> wrote:

> >Na pl.comp.lang.c A.L. skrobie:
> >> >Rozumiem, że dla pana pewnie jeśli algorytm ma za zadanie pracować tylko dla
> >> >zadanego maksymalnego N, to w takim razie do osiągnięcia złożoności O(1)
> >> >wystarczy, aby wykonywał zawsze N iteracji niezależnie od tego, ile ich
> >> >rzeczywiście potrzeba. Ale, wybaczy pan, to jest computer science, a nie
> >> >computer engineering.
> >
> >> Nei wiedzialem ze Pan scientysta.. Ale w dalszym czigu Pan nie
> >> postawil problemu prawidlowo. Widac jednak Pan izynier.
> >
> >Owszem. I, jak inżynier, dążę najprostszą metodą do rozwiązania problemu, a
> >nie wyszukiwania wszystkich możliwych problemów.

> Inzynier z Pana tez do kitu. Powinien Pan postawic problem
> nastepujaco: "znalezc algorytm ktory bedzie rowiazywal zadanie
> stosujac minimalna liczbe operacji

To widocznie inżynierowie dzielą się też na inżynierów naukowych i na
inżynierów inżynierskich.

W sumie racja, że najsensowniej było określić, że potrzebuję najmniejszą
liczbę operacji, ale też określenie, że "w stałym czasie" też nie było
niefortunne - zakładałem po prostu, że każdy się domyśli, że ewentualna
liniowość będzie tutaj spowodowana numerem kolejnym od prawej bitu
charakterystycznego.

Oczywiście, każdy zapytał, ale i też oczywiście, każdy się domyślił :)

> (i tu Pan powinien napisac ktore
> operacje sa najbardziej kosztowne i ich ilosc powinna byc
> minimalizowana) ktora to ilosc operacji bedzie niezalezna od
> polozenaia bitu charakterystycznego

Ano właśnie - i o tym była mowa mówiąc "w stałym czasie". Było zatem więcej
tych niejawnych założeń, tzn.:

1. Zakładałem, że jak mówię "w stałym czasie", to każdy się domyśli, że
algorytm powinien mieć taką samą złożonośc obliczeniową niezależnie od
położenia bitu charakterystycznego.

2. Zakładałem, że jak proszę o algorytm, to ten, kto go wymyśli, postara się
wykonać zadanie jak najmniejszą ilością operacji, już z samego założenia.

> Inaczej ja moge Panu zaproponowac algorytm ktory bedzie mial stala
> liczbe JAKISCH operacji, albo bedzie sie wykonywal dokaldnie 47
> minut dla dowolnego polozenia bitu charakterystycznego.

Oczywiście tak też mogłoby być - takie rozwiązanie bym po postu odrzucił.
:)

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

Zapraszam po bardzo przyjemną funkcję pomagającą w tym zadaniu.
http://www.eprogramowanie.pl/blog/index.php/2006/10/01/jak-znalezc-wartosc-najstarszego-ustawionego-bitu-liczby-32-bitowej/#more-16

pozdrawiam
         Rafał Żurawski
---------------------------

http://www.e-programowanie.pl
BLOG: http://www.e-programowanie.pl/blog

---------------------------

Na pl.comp.lang.c rzur@poczta.onet.pl skrobie:
> Zapraszam po bardzo przyjemną funkcję pomagającą w tym zadaniu.
> http://www.eprogramowanie.pl/blog/index.php/2006/10/01/jak-znalezc-wartosc-najstarszego-ustawionego-bitu-liczby-32-bitowej/#more-16

Sory, ale to jest żałosne i smutne.

Po pierwsze, nie interesuje mnie rozwiązanie w asemblerze z przyczyn
zasadniczych.

Po drugie, to jest wersja wyszukująca w czasie liniowym; rozwiązanie, które
otrzymałem robi to w czasie stałym.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"

a porównałeś rzeczywiste czasy wykonania ?
czy tylko tak spekulujesz ?

Na pl.comp.lang.c rzur@poczta.onet.pl skrobie:
> a porównałeś rzeczywiste czasy wykonania ?
> czy tylko tak spekulujesz ?

Gościu, czy wiesz, czym się różni O(1) od O(N)?

Jeśli nie wiesz, to nie mamy o czym rozmawiać.


-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethouris(O)gmail.com>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"