Własności operacji na bitach

[adambak]

Miałem taki oto problem: dla podanych liczb \(\displaystyle{ n}\) i \(\displaystyle{ k}\) ustalić czy liczba \(\displaystyle{ {n \choose k}}\) jest parzysta czy nie. Długo szukałem po różnych źródłach w internecie i znalazłem takie oto rozwiązanie:


Mając binarne postaci liczb \(\displaystyle{ n}\) i \(\displaystyle{ k}\), czyli nazwijmy kolejno: \(\displaystyle{ n _{2}}\) i \(\displaystyle{ k _{2}}\) najpierw ustalić postać liczby \(\displaystyle{ \neg n _{2}}\) (czyli sprawa prosta, negujemy każdy jej bit), a potem wykonać koniunkcję bitów liczb \(\displaystyle{ \neg n _{2}}\) oraz \(\displaystyle{ k}\) i zapisać wynik. Teraz jeśli otrzymana liczba, nazwijmy ją \(\displaystyle{ a _{2}}\), jest równa zero to wynik \(\displaystyle{ {n \choose k}}\) jest nieparzysty, jeśli jest różna od zera to jest parzysty..


Algorytm jest genialny, program napisałem i działa, ale nie lubię korzystać z czegoś czego nie rozumiem/nie umiem udowodnić. Ten algorytm to jakieś straszne czary, dlatego mam kilka pytań:

1) jak udowodnić jego poprawność? (czy w ogóle dowodzenie takich rzeczy jest w miarę w zasięgu normalnego człowieka?)

2) jak się ma liczba \(\displaystyle{ n _{2}}\) do \(\displaystyle{ \neg n _{2}}\), czy da się to wytłumaczyć jakoś w miarę przystępnie? czy istnieje jakaś analogia do systemu dziesiętnego, czy w systemie dziesiętnym też można przeprowadzić taką operację że z pierwszej liczby otrzymujemy drugą (rozumiem że ta operacja znacznie by się różniła)?

3) jak powstała liczba \(\displaystyle{ a _{2}}\), co to w ogóle jest, czy jest jakaś analogia do systemu dziesiętnego? czy dobrze myślę (nie mam w niczym poparcia, tak tylko rozważam), że liczba ta ma coś wspólnego z faktoryzacją \(\displaystyle{ {n \choose k}}\)?

[Zordon]

To istotnie jest dobry algorytm, jednak trudny do zrozumienia. Ja zaproponuję równie szybki, ale prostszy do udowodnienia:

Mamy \(\displaystyle{ \frac{n!}{k!(n-k)!}}\), czyli tak naprawdę chcemy wiedzieć ile dwójek występuje w rozkładzie na czynniki pierwsze liczby \(\displaystyle{ m!}\) dla jakiegoś m (u nas \(\displaystyle{ m=n,k,n-k}\)).
Oznaczmy tę liczbę dwójek w rozkładzie \(\displaystyle{ m!}\) przez \(\displaystyle{ g(m)}\). Wtedy można to policzyć tak:
\(\displaystyle{ g(m)=\lfloor \frac{m}{2} \rfloor+\lfloor \frac{m}{4} \rfloor+\lfloor \frac{m}{8} \rfloor+\lfloor \frac{m}{16} \rfloor+...+\lfloor \frac{m}{2^n} \rfloor+...}\)
Tę sumę zapisałem jako nieskończoną, ale jasne jest, że od pewnego miejsca będą już same zera (no jeśli \(\displaystyle{ 2^n>m}\)).

Teraz pytanie dlaczego to działa, to wynika z tego, że liczb parzystych wśród \(\displaystyle{ 1,...,m}\) jest \(\displaystyle{ \lfloor \frac{m}{2} \rfloor}\), liczb podzielnych przez 4 jest \(\displaystyle{ \lfloor \frac{m}{4} \rfloor}\), i tak dalej.

Teraz żeby sprawdzić, czy taki współczynnik dwumienny jest parzysty, liczymy \(\displaystyle{ g(n)-g(k)-g(n-k)}\) i sprawdzamy czy jest \(\displaystyle{ >0}\).

Złożoność rozwiązania to \(\displaystyle{ O(\log n)}\)

Aha, i co ważne to działa nie tylko dla dwójki. Twój algorytm też można uogólnić, ale znowu będzie to bardziej skomplikowane niż powyższe.

[adambak]

Faktycznie, piękne rozwiązanie. Dużo łatwiejsze, nie trzeba z żadnych dziwnych sztuczek korzystać, tylko od razu idzie logicznie, bardzo zrozumiałe. Identyczny czas, nawet nie musiałem optymalizować I/O. Dzięki