Wyodrębnianie bitów za pomocą jednego mnożenia


301

Widziałem ciekawą technikę zastosowaną w odpowiedzi na inne pytanie i chciałbym ją trochę lepiej zrozumieć.

Otrzymujemy 64-bitową liczbę całkowitą bez znaku i jesteśmy zainteresowani następującymi bitami:

1.......2.......3.......4.......5.......6.......7.......8.......

W szczególności chcielibyśmy przenieść je na najwyższe osiem pozycji, w ten sposób:

12345678........................................................

Nie obchodzi nas wartość bitów wskazanych przez .i nie trzeba ich zachowywać.

Rozwiązanie było maskowania niepożądanych bitów i pomnożenie wyniku przez 0x2040810204081. To, jak się okazuje, załatwia sprawę.

Jak ogólna jest ta metoda? Czy tę technikę można wykorzystać do wyodrębnienia dowolnego podzbioru bitów? Jeśli nie, w jaki sposób można ustalić, czy metoda działa dla określonego zestawu bitów?

Wreszcie, jak przejść do znalezienia (a?) Poprawnego mnożnika, aby wyodrębnić dane bity?


29
Jeśli okaże się, że jeden interesujący, spójrz na tę listę: graphics.stanford.edu/~seander/bithacks.html Wiele z nich (ab) używa mnożenia / dzielenia szerszej liczby całkowitej, aby osiągnąć ciekawe wyniki. ( „Rewers bitów w bajcie z 4 Operacje” część pokazuje, jak radzić sobie z trick Bitshift / mnożenia, gdy nie ma wystarczającej ilości miejsca i trzeba maskować / pomnożyć dwukrotnie)
viraptor

@viraptor: Doskonały punkt. Jeśli rozumiesz ograniczenia tej metody, możesz naprawdę użyć mnożenia, aby wiele osiągnąć w zakresie manipulacji bitami.
Expedito

9
Co ciekawe, w AVX2 znajduje się instrukcja (która niestety nie jest jeszcze dostępna), która wykonuje dokładnie opisaną operację: software.intel.com/sites/products/documentation/studio/composer/…
JPvdMerwe

3
Innym miejscem do poszukiwania sprytnych algorytmów kręcących
bity

1
Um livro que conheço sobre o assunto (e gosto bastante) lub „Hacker's Delight” link
Salles

Odpowiedzi:


235

Bardzo interesujące pytanie i sprytna sztuczka.

Spójrzmy na prosty przykład manipulacji jednym bajtem. Używanie 8-bitowego bez znaku dla uproszczenia. Wyobraź sobie, że twój numer jest xxaxxbxxi chcesz ab000000.

Rozwiązanie składało się z dwóch kroków: trochę maskowania, a następnie pomnożenia. Maska bitowa to prosta operacja AND, która zamienia nieciekawe bity w zera. W powyższym przypadku twoja maska ​​byłaby 00100100i wynik 00a00b00.

Teraz najtrudniejsza część: przekształcenie tego w ab.......

Mnożenie to kilka operacji shift-and-add. Kluczem jest umożliwienie przelewowi „przesunięcia” bitów, których nie potrzebujemy i umieszczenia tych, które chcemy we właściwym miejscu.

Mnożenie przez 4 ( 00000100) powoduje przesunięcie wszystkiego, co pozostało o 2 i prowadzi doa00b0000 . Aby dostać się bw górę, musimy pomnożyć przez 1 (aby utrzymać a we właściwym miejscu) + 4 (aby przenieść b w górę). Suma ta wynosi 5 i w połączeniu z wcześniejszymi 4 otrzymujemy magiczną liczbę 20 lub 00010100. Oryginał był 00a00b00po zamaskowaniu; mnożenie daje:

000000a00b000000
00000000a00b0000 +
----------------
000000a0ab0b0000
xxxxxxxxab......

Dzięki takiemu podejściu możesz objąć większą liczbę i więcej bitów.

Jedno z zadanych przez Ciebie pytań brzmiało: „czy można tego dokonać za pomocą dowolnej liczby bitów?” Myślę, że odpowiedź brzmi „nie”, chyba że zezwolisz na kilka operacji maskowania lub kilka multiplikacji. Problemem jest kwestia „kolizji” - na przykład „bezpańskie b” w powyższym problemie. Wyobraź sobie, że musimy to zrobić z taką liczbąxaxxbxxcx . Zgodnie z wcześniejszym podejściem, pomyślałbyś, że potrzebujemy {x 2, x {1 + 4 + 16}} = x 42 (oooh - odpowiedź na wszystko!). Wynik:

00000000a00b00c00
000000a00b00c0000
0000a00b00c000000
-----------------
0000a0ababcbc0c00
xxxxxxxxabc......

Jak widać, nadal działa, ale „tylko”. Kluczową kwestią jest tutaj to, że między „bitami” jest wystarczająco dużo miejsca, aby wszystko wycisnąć. Nie mogłem dodać czwartego bitu zaraz po c, ponieważ dostałbym przypadki, w których dostaję c + d, bity mogą przenosić ...

Więc bez formalnego dowodu odpowiedziałbym na bardziej interesujące części twojego pytania w następujący sposób: „Nie, to nie zadziała dla dowolnej liczby bitów. Aby wyodrębnić N bitów, potrzebujesz (N-1) spacji między bitami, które chcesz wyodrębnij lub wykonaj dodatkowe kroki pomnożenia maski ”.

Jedyny wyjątek, jaki mogę wymyślić w przypadku reguły „musi mieć (N-1) zera między bitami”, to: jeśli chcesz wyodrębnić dwa bity sąsiadujące ze sobą w oryginale ORAZ chcesz zachować je w w tej samej kolejności, nadal możesz to zrobić. Dla celów reguły (N-1) liczą się one jako dwa bity.

Jest jeszcze jeden wgląd - zainspirowany odpowiedzią @Ternary poniżej (zobacz mój komentarz tam). Dla każdego interesującego bitu potrzebujesz tylko tyle zer po prawej stronie, ile potrzebujesz miejsca na bity, które muszą tam przejść. Ale potrzebuje też tylu bitów po lewej, co bitów wynikowych po lewej. Więc jeśli bit b kończy się w pozycji m n, to musi mieć m-1 zera po lewej, a nm zera po prawej. Jest to ważne ulepszenie pierwotnych kryteriów, zwłaszcza gdy bity nie są w tej samej kolejności w oryginalnym numerze, co będą po ponownym uporządkowaniu. Oznacza to na przykład 16-bitowe słowo

a...e.b...d..c..

Można zmienić na

abcde...........

nawet jeśli między e i b jest tylko jedna przestrzeń, dwie między d i c, trzy między pozostałymi. Co się stało z N-1? W tym przypadku a...estaje się „jednym blokiem” - są one mnożone przez 1, aby znaleźć się w odpowiednim miejscu, a więc „dostaliśmy e za darmo”. To samo dotyczy b i d (b potrzebuje trzech spacji w prawo, d potrzebuje tych samych trzech po lewej). Kiedy więc obliczamy magiczną liczbę, okazuje się, że istnieją duplikaty:

a: << 0  ( x 1    )
b: << 5  ( x 32   )
c: << 11 ( x 2048 )
d: << 5  ( x 32   )  !! duplicate
e: << 0  ( x 1    )  !! duplicate

Oczywiście, jeśli chcesz te liczby w innej kolejności, będziesz musiał je dalej rozmieścić. Możemy przeformułować(N-1) zasadę: „Zawsze zadziała, jeśli między bitami są przynajmniej (N-1) spacje; lub, jeśli znana jest kolejność bitów w wyniku końcowym, to jeśli bit b znajdzie się w pozycji m n, musi mieć zero m-1 po lewej stronie, a nm zero po prawej stronie. ”

@Ternary zwrócił uwagę, że ta reguła nie do końca działa, ponieważ może wystąpić przeniesienie z bitów, dodając „tuż po prawej stronie obszaru docelowego” - mianowicie, gdy wszystkie szukane bity są jednymi. Kontynuując przykład podałem powyżej z pięcioma ciasno upakowanymi bitami w 16-bitowym słowie: jeśli zaczniemy

a...e.b...d..c..

Dla uproszczenia wymienię pozycje bitów ABCDEFGHIJKLMNOP

Matematyka, którą zamierzaliśmy zrobić, była

ABCDEFGHIJKLMNOP

a000e0b000d00c00
0b000d00c0000000
000d00c000000000
00c0000000000000 +
----------------
abcded(b+c)0c0d00c00

Do tej pory uważaliśmy, że cokolwiek poniżej abcde(pozycje ABCDE) nie będzie miało znaczenia, ale w rzeczywistości, jak wskazał @Ternary, jeśli b=1, c=1, d=1wtedy (b+c)pozycja Gspowoduje trochę przeniesienia do pozycji F, co oznacza, że (d+1)pozycja Fspowoduje przeniesienie nieco do pozycjiE - i nasze wynik jest zepsuty. Zwróć uwagę, że miejsce po prawej stronie najmniej znaczącego elementu zainteresowania (c w tym przykładzie) nie ma znaczenia, ponieważ mnożenie spowoduje wypełnienie zerami od jednego najmniej znaczącego bitu.

Musimy więc zmodyfikować naszą zasadę (m-1) / (nm). Jeśli jest więcej niż jeden bit, który ma „dokładnie (nm) nieużywane bity po prawej stronie (nie licząc ostatniego bitu we wzorze -„ c ”w powyższym przykładzie), musimy wzmocnić regułę - i musimy zrób to iteracyjnie!

Musimy spojrzeć nie tylko na liczbę bitów, które spełniają kryterium (nm), ale także na te, które są w (n-m + 1) itd. Nazwijmy ich liczbę Q0 (dokładnie n-mdo następnego bitu), Q1 ( n-m + 1), do Q (N-1) (n-1). W takim razie ryzykujemy, że nie

Q0 > 1
Q0 == 1 && Q1 >= 2
Q0 == 0 && Q1 >= 4
Q0 == 1 && Q1 > 1 && Q2 >=2
... 

Jeśli spojrzysz na to, możesz zauważyć, że jeśli napiszesz proste wyrażenie matematyczne

W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1)

a wynik jest taki W > 2 * N, że musisz podnieść kryterium RHS o jeden bit do (n-m+1). W tym momencie operacja jest bezpieczna, dopóki W < 4; jeśli to nie zadziała, zwiększ jeszcze jedno kryterium itp.

Myślę, że postępowanie zgodnie z powyższym da ci długą drogę do odpowiedzi ...


1
Świetny. Jeszcze jeden subtelny problem: test m-1 / nm czasami kończy się niepowodzeniem z powodu bitów przenoszących. Spróbuj ... b..c ... d - kończysz z b + c w piątym bicie, który, jeśli oba są 1, tworzy bit przenoszenia, który blokuje d (!)
Ternary

1
wynik: n-1 bitów przestrzeni zabrania konfiguracji, które powinny działać (tj. ... b..c ... d), a m-1 / nm pozwala na te, które nie działają (a ... b..c ...re). Nie byłem w stanie wymyślić prostego sposobu na scharakteryzowanie, które będą działać, a które nie.
Ternary

Jesteś dobry! Problem przenoszenia oznacza, że ​​potrzebujemy nieco więcej miejsca po prawej stronie każdego bitu jako „ochrony”. Na pierwszy rzut oka, jeśli są co najmniej dwa bity, które mają dokładnie minimalną nm po prawej stronie, musisz zwiększyć przestrzeń o 1. Bardziej ogólnie, jeśli istnieje P takich bitów, potrzebujesz dodatkowych bitów log2 (P) prawo każdego, który miał minimum (mn). Wydaje Ci się, że jesteś odpowiedni?
Floris

Ten ostatni komentarz był zbyt uproszczony. Myślę, że moja ostatnio edytowana odpowiedź pokazuje, że log2 (P) nie jest właściwym podejściem. Własna odpowiedź @ Ternary (poniżej) pokazuje elegancko, jak rozpoznać konkretną kombinację bitów, jeśli nie masz gwarantowanego rozwiązania - uważam, że powyższa praca bardziej szczegółowo ją omawia.
Floris

1
Prawdopodobnie jest to zbieg okoliczności, ale odpowiedź została zaakceptowana, gdy liczba entuzjastów osiągnęła 127. Jeśli przeczytałeś do tej pory, uśmiechniesz się ze mną ...
Floris

154

Rzeczywiście bardzo interesujące pytanie. Wchodzę z moimi dwoma centami, to znaczy, że jeśli potrafisz określić takie problemy w zakresie logiki pierwszego rzędu w teorii bitvectora, to dowody twierdzeń są twoim przyjacielem i mogą potencjalnie zapewnić ci bardzo szybko odpowiedzi na twoje pytania. Ponownie określmy zadany problem jako twierdzenie:

„Istnieje kilka 64-bitowych stałych„ maska ​​”i„ multiplikacja ”, tak że dla wszystkich 64-bitowych wektorów bitowych x, w wyrażeniu y = (x & mask) * multiplicand, mamy to y.63 == x.63 , y.62 == x.55, y.61 == x.47 itd. ”

Jeśli to zdanie jest w rzeczywistości twierdzeniem, to prawdą jest, że niektóre wartości stałych „mask” i „multiplicand” spełniają tę właściwość. Sformułujmy to w kategoriach czegoś, co może zrozumieć przysłowie twierdzeń, a mianowicie danych wejściowych SMT-LIB 2:

(set-logic BV)

(declare-const mask         (_ BitVec 64))
(declare-const multiplicand (_ BitVec 64))

(assert
  (forall ((x (_ BitVec 64)))
    (let ((y (bvmul (bvand mask x) multiplicand)))
      (and
        (= ((_ extract 63 63) x) ((_ extract 63 63) y))
        (= ((_ extract 55 55) x) ((_ extract 62 62) y))
        (= ((_ extract 47 47) x) ((_ extract 61 61) y))
        (= ((_ extract 39 39) x) ((_ extract 60 60) y))
        (= ((_ extract 31 31) x) ((_ extract 59 59) y))
        (= ((_ extract 23 23) x) ((_ extract 58 58) y))
        (= ((_ extract 15 15) x) ((_ extract 57 57) y))
        (= ((_ extract  7  7) x) ((_ extract 56 56) y))
      )
    )
  )
)

(check-sat)
(get-model)

A teraz zapytajmy przysłowie twierdzenia Z3, czy jest to twierdzenie:

z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2

Wynik to:

sat
(model
  (define-fun mask () (_ BitVec 64)
    #x8080808080808080)
  (define-fun multiplicand () (_ BitVec 64)
    #x0002040810204081)
)

Bingo! Odtwarza wynik podany w oryginalnym poście w 0,06 sekundy.

Patrząc na to z bardziej ogólnej perspektywy, możemy postrzegać to jako przykład problemu syntezy programu pierwszego rzędu, który jest rodzącym obszarem badań, na temat którego opublikowano niewiele artykułów. Poszukiwanie "program synthesis" filetype:pdfpowinno zacząć.


2
Jestem pod wrażeniem! Nie wiedziałem, że „logika pierwszego rzędu nad teorią bitvectora” była nawet prawdziwym przedmiotem, który ludzie studiowali - nie mówiąc już o tym, że może dać tak interesujące wyniki. Dziękuję bardzo za podzielenie się tym.
Floris

@AndrewBacker: Czy ktoś mógłby mi wyjaśnić, w jakim sensie jest tak zwana rzecz „SO-as-a-job”? To znaczy, że nie płacą nic. Nie możesz żyć tylko z przedstawicielem SO. Może może dać ci pewne punkty w wywiadach. Może. Jeśli miejsce pracy jest wystarczająco dobre, aby rozpoznać wartość przedstawiciela SO, a to nie jest dane ...
Przywróć Monikę

3
Pewnie. SO to także gra dla wielu osób (wszystko z punktami). Po prostu ludzka natura, jak polowanie w / r / new, abyś mógł opublikować pierwszy komentarz i zdobyć karmę. Nie ma w tym nic złego, o ile odpowiedzi są nadal dobre. Po prostu cieszę się, że mogę głosować czyjś czas i wysiłek, kiedy prawdopodobnie zauważą, że ktoś to zrobił. Zachęcanie to dobra rzecz :) I ... to był naprawdę stary komentarz i nadal jest prawdziwy. Nie rozumiem, jak to nie jest jasne.
Andrew Backer,

88

Każdy 1-bit w multiplikatorze służy do skopiowania jednego z bitów do jego właściwej pozycji:

  • 1jest już w prawidłowej pozycji, więc pomnóż przez 0x0000000000000001.
  • 2 należy przesunąć o 7 bitów w lewo, więc mnożymy przez 0x0000000000000080 (bit 7 jest ustawiony).
  • 3należy przesunąć o 14 bitów w lewo, więc mnożymy przez 0x0000000000000400(bit 14 jest ustawiony).
  • i tak dalej
  • 8należy przesunąć o 49 bitów w lewo, więc mnożymy przez 0x0002000000000000(bit 49 jest ustawiony).

Mnożnik jest sumą mnożników dla poszczególnych bitów.

Działa to tylko dlatego, że bity, które mają być zebrane, nie są zbyt blisko siebie, tak że zwielokrotnienie bitów, które nie pasują do siebie w naszym schemacie, albo wykracza poza 64-bitowy, albo w dolnej części, na której nie ma znaczenia.

Zauważ, że pozostałe bity w pierwotnym numerze muszą być 0. Można to osiągnąć poprzez maskowanie ich operacją AND.


2
Świetne wyjaśnienie! Twoja krótka odpowiedź pozwoliła szybko znaleźć wartość „magicznej liczby”.
Expedito

4
To naprawdę najlepsza odpowiedź, ale nie byłaby tak pomocna bez przeczytania (pierwszej połowy) odpowiedzi @ floris.
Andrew Backer

29

(Nigdy wcześniej tego nie widziałem. Ta sztuczka jest świetna!)

Rozbuduję trochę twierdzenie Florisa, że ​​podczas wydobywania nbitów potrzebujeszn-1 odstępu między dowolnymi nieciągłymi bitami:

Moją początkową myślą (za chwilę zobaczymy, jak to nie do końca działa) było to, że możesz zrobić lepiej: jeśli chcesz wyodrębnić nbity, będziesz mieć kolizję podczas wydobywania / przesuwania bitu, ijeśli masz kogoś (nie -konsekwentne z bitem i) w i-1bitach poprzedzających lub n-ibitach późniejszych.

Podam kilka przykładów ilustrujących:

...a..b...c... Działa (nikt w 2 bitach później a , trochę wcześniej i trochę później bi nikt nie jest w 2 bitach później c):

  a00b000c
+ 0b000c00
+ 00c00000
= abc.....

...a.b....c... Nie działa, ponieważ b działa, znajduje się w 2 bitach później a(i zostaje wciągnięty w miejsce kogoś innego, gdy się zmieniamy a):

  a0b0000c
+ 0b0000c0
+ 00c00000
= abX.....

...a...b.c... Nie działa, ponieważ b działa, znajduje się w 2 bitach poprzedzających c(i zostaje zepchnięty w miejsce kogoś innego podczas zmiany c):

  a000b0c0
+ 0b0c0000
+ b0c00000
= Xbc.....

...a...bc...d... Działa, ponieważ kolejne bity przesuwają się razem:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Ale mamy problem. Jeśli użyjemy n-izamiastn-1 , moglibyśmy mieć następujący scenariusz: co gdybyśmy mieli kolizję poza częścią, na której nam zależy, coś, co chcielibyśmy ukryć na końcu, ale którego bity przenoszące ostatecznie zakłócają ważny, nie maskowany zakres ? (i uwaga: n-1wymaganie upewnia się, że tak się nie stanie, upewniając się, że i-1bity po naszym nie zamaskowanym zakresie są czyste, gdy zmieniamyi th th)

...a...b..c...d...Potencjalna awaria bitów przenoszących cwystępujen-1 później b, ale spełnia n-ikryteria:

  a000b00c000d
+ 0b00c000d000
+ 00c000d00000
+ 000d00000000
= abcdX.......

Dlaczego więc nie wrócimy do tego ”n-1 wymogu kawałków przestrzeni”? Ponieważ możemy zrobić lepiej :

...a....b..c...d.. Nie powiedzie się „n-1 test bitów przestrzeni”, ale działa na naszą sztuczkę wyodrębniania bitów:

+ a0000b00c000d00
+ 0b00c000d000000
+ 00c000d00000000
+ 000d00000000000
= abcd...0X......

Nie mogę znaleźć dobrego sposobu na scharakteryzowanie tych pól, które tego nie robią ma n-1miejsca między ważnymi bitami, ale nadal działałyby dla naszej operacji. Ponieważ jednak wiemy z góry które bity jesteśmy zainteresowani, możemy sprawdzić nasz filtr, aby upewnić się, że nie występują kolizje bitów przenoszących:

Porównaj (-1 AND mask) * shiftz oczekiwanym wynikiem wszystkich,-1 << (64-n) (dla wersji 64-bitowej bez znaku)

Przesunięcie / pomnożenie magii w celu wyodrębnienia naszych bitów działa tylko wtedy, gdy oba są równe.


Podoba mi się - masz rację, że na każdy bit potrzebujesz tylko tyle zer po prawej stronie, ile potrzebujesz miejsca na bity, które muszą tam iść. Ale potrzebuje też tylu bitów po lewej, co bitów wynikowych po lewej. Więc jeśli nieco bkończy się w pozycji mo n, to musi mieć m-1zera do jego lewej strony i n-m-1zer na jej prawej stronie. Jest to ważne ulepszenie pierwotnych kryteriów, zwłaszcza gdy bity nie są w tej samej kolejności w oryginalnym numerze, co będą po ponownym uporządkowaniu. To jest fajne.
Floris

13

Oprócz doskonałych odpowiedzi na to bardzo interesujące pytanie, warto wiedzieć, że ta sztuczka polegająca na multiplikacji bitowej jest znana w społeczności szachów komputerowych od 2007 roku, pod nazwą Magic BitBoards .

Wiele komputerowych silników szachowych używa kilku 64-bitowych liczb całkowitych (zwanych bitboardami) do reprezentowania różnych zestawów sztuk (1 bit na zajmowany kwadrat). Załóżmy, że przesuwany element (wieża, biskup, królowa) na pewnym polu początkowym może przejść do co najwyżej Kkwadratów, jeśli nie było żadnych blokujących elementów. Używanie Kbitów -i tych rozproszonych bitów z bitboardem zajmowanych kwadratów daje określone K-bitowe słowo osadzone w 64-bitowej liczbie całkowitej.

Magicznego mnożenia można użyć do odwzorowania tych rozproszonych Kbitów na niższe Kbity 64-bitowej liczby całkowitej. Te niższe Kbity można następnie wykorzystać do indeksowania tabeli wstępnie obliczonych bitboardów, które reprezentują dozwolone kwadraty, do których może faktycznie przenieść się kawałek na jego pierwotnym kwadracie (dbając o blokowanie elementów itp.)

Typowy silnik szachowy wykorzystujący to podejście ma 2 tabele (jeden dla wież, jeden dla biskupów, królowe używające kombinacji obu) z 64 wpisami (jeden dla kwadratu początkowego), które zawierają takie wstępnie obliczone wyniki. Zarówno najwyżej oceniane zamknięte źródło ( Houdini ), jak i silnik szachowy typu open source ( Sztokfisz ) obecnie stosują to podejście ze względu na bardzo wysoką wydajność.

Znalezienie tych magicznych mnożników odbywa się albo za pomocą wyczerpującego wyszukiwania (zoptymalizowanego z wczesnymi odcięciami), albo za pomocą prób i błędów (np. wielu losowych 64-bitowych liczb całkowitych). Podczas generowania ruchów nie użyto żadnych wzorów bitów, dla których nie można było znaleźć stałej magicznej. Jednak bitowe efekty przenoszenia są zwykle konieczne, gdy bity do mapowania mają (prawie) sąsiednie indeksy.

AFAIK, bardzo ogólne podejście do SAT-Solvera autorstwa @Syzygy, nie było używane w szachach komputerowych i nie wydaje się też, aby istniała formalna teoria dotycząca istnienia i wyjątkowości takich magicznych stałych.


Myślałem, że każdy, kto ma pełne formalne wykształcenie CS, skoczyłby na podejście SAT bezpośrednio po zobaczeniu tego problemu. Być może ludzie CS uważają szachy za nieciekawe? :(
Przywróć Monikę

@KubaOber Jest to na odwrót: w szachy komputerowe dominują bit-twiddlers, którzy programują w C lub asemblerze i nienawidzą wszelkiego rodzaju abstrakcji (C ++, szablony, OO). Myślę, że to odstrasza prawdziwych facetów CS :-)
TemplateRex,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.