🚀 go-pugleaf

Próbowałem to sam kiedyś rozwiązać i raczej zrezygnuję i tak z tej metody, ale
sprawa mnie trochę zaciekawiła. Uprzedzam, że problem może być niemożliwy do
rozwiązania.

Sprawa polega na tym:

Mamy dwie wartości zestawów bitowych o dokładnie ustalonej ilości bitów.
Powiedzmy, że 16, to nie ma znaczenia.

Jedna z nich jest maską bitową, w której są ustawione określone bity.

Druga z nich jest wartością, którą należy zweryfikować, czy "pasuje" do maski.
Wartość zawiera informację tylko o jednym bicie, należy jedynie określić, czy
ów bit charakterystyczny znajdujący się w wartości, zawiera się również w
masce. Inaczej mówiąc, jeśli bylibyśmy w stanie z wartości wyciągnąć bit
charakterystyczny, to wtedy wystarczyłoby zrobić operację AND z maską i wynik
zerowy lub niezerowy oznacza nam, że bit charakterystyczny tej wartości
zawiera się w masce lub nie.

Bit charakterystyczny w wartości jest jednak reprezentowany w trochę
zamieszany sposób.

Przykładowo, załóżmy że długość ciągu bitów jest 16, a bitem
charakterystycznym jest bit 10 (czyli szósty od lewej:). Wtedy wartość do
sprawdzenia wygląda tak:

Pierwsze 5 bitów od lewej są zerami. Bit szósty od lewej (czyli ten właśnie
bit 10) jest ustawiony. Natomiast bity 9-0 mają nieokreślone wartości (tzn.
niezależnie od wartości tych bitów, przy tych założeniach wartość ma wciąż ten
sam bit charakterystyczny. Czyli np.:

              |
Wartość: 0000010011001011
Maska:   0100011000001000

Dla takiej maski uważamy, że bit charakterystczny wartości znajduje się w
masce.

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.

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


Pozdrawiam,

-- 
//  _    ___         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"