Czy na maturze z informatyki można używać operatorów bitowych?

Dzień dobry

Zwracam się do Państwa z pytaniem, na które nie potrafię znaleźć odpowiedzi, mianowicie: czy można w realizacji zadań używać operatorów bitowych do operacji takich jak NOT (~), AND (&), OR (|), XOR (^)? Wykorzystałem je do realizacji zadania 3 z matury z roku 2023 i mamy wątpliwości, czy jest to dozwolone czy nie.

Logika stojąca za użyciem operatorów jest taka, że są to operatory logiczne w sensie definicji na Wikipedii, gdzie operatorem logicznym nazwany jest symbol bądź słowo służące do realizacji algebry Boole'a.

Jednocześnie w szkole zawsze mi mówiono, że operatory logiczne to operatory, które w C++ są znane jako && oraz ||, a w Pythonie and oraz or.

Z wyrazami szacunku
Maks

Odpowiedź wymaga rozróżnienia dwóch kwestii: czym różnią się operatory logiczne od bitowych oraz jakie ograniczenia nakłada treść konkretnego zadania. Ponieważ wyjaśnienie okazało się obszerniejsze niż zwykła odpowiedź mailowa, postanowiliśmy podzielić się nim również w naszej bazie wiedzy.

Zacznijmy od zadania 3 z Arkusz matury rozszerzonej z informatyki - 22 maja 2023, Formuła 2023

Przyjrzyjmy się zadaniu 3 „Liczba Pi” z Arkusz matury rozszerzonej z informatyki - 22 maja 2023, Formuła 2023. Dane znajdowały się w pliku pi.txt, zawierającym 10 000 cyfr po przecinku rozwinięcia dziesiętnego liczby π (po jednej cyfrze w wierszu). Należało napisać programy analizujące te dane i zapisać odpowiedzi do poszczególnych podpunktów.

Treść zadania 3 jest w Arkusz matury rozszerzonej z informatyki - 22 maja 2023, Formuła 2023:

To typowe zadanie z programowania: wczytujemy dane, przetwarzamy je i uzyskujemy wymagane wyniki. W jego poleceniu nie ma ograniczenia wykluczającego operatory bitowe. Nie ma więc podstaw, żeby uznać samo ich użycie za niedozwolone.

Możemy korzystać z możliwości wybranego języka programowania, pamiętając o wymaganiach zadania i dostępnego środowiska egzaminacyjnego. To ostatnie zastrzeżenie ma znaczenie zwłaszcza przy bibliotekach, do których wrócimy pod koniec artykułu. Język i środowisko wybieramy spośród możliwości określonych w komunikacie CKE w sprawie listy języków programowania na maturze z informatyki w 2027 roku i dostępnych w szkole.

Więcej o wyborze języka programowania przeczytasz tutaj: w jakich językach programowania można pisać maturę z informatyki oraz w artykule jaki język programowania wybrać na maturę.

Pozostaje jednak druga część pytania Maksa: czy operatory bitowe możemy traktować jak operatory logiczne?

Czym są operatory logiczne?

Operatory logiczne wykorzystujemy do budowania warunków. Koniunkcja pozwala wymagać jednoczesnego spełnienia dwóch warunków, alternatywa - spełnienia przynajmniej jednego, a negacja odwraca wartość logiczną pojedynczego warunku. W C++ odpowiadają im &&, || i !, natomiast w Pythonie and, or i not.

Załóżmy, że chcemy sprawdzić, czy liczba należy do przedziału od 1 do 9 włącznie. Musi być jednocześnie nie mniejsza niż 1 i nie większa niż 9. Potrzebujemy więc koniunkcji.

Z kolei liczba znajduje się poza tym przedziałem, gdy jest mniejsza niż 1 lub większa niż 9. Tutaj wykorzystamy alternatywę.

Przykład w C++:

Ten sam przykład w Pythonie:

W tych przykładach argumentami operatorów są wyniki porównań, czyli wartości logiczne. Właśnie do takiego łączenia i negowania warunków wykorzystujemy operatory logiczne w instrukcjach if czy pętlach while.

Czym są operatory bitowe?

Operatory bitowe, stosowane do liczb całkowitych, wykonują operacje na poszczególnych bitach tych liczb. Nie sprawdzają po prostu, czy cała liczba oznacza prawdę albo fałsz. Przykładowo bitowe AND porównuje bity znajdujące się na odpowiadających sobie pozycjach i pozostawia jedynkę tylko tam, gdzie obie liczby mają jedynkę.

W C++ i Pythonie operatory &, | i ^ wykonują odpowiednio bitowe AND, OR i XOR. Dla każdej pary odpowiadających sobie bitów AND wymaga dwóch jedynek, OR przynajmniej jednej jedynki, a XOR dwóch różnych wartości.

Spójrzmy na liczby 6 i 3:

W pierwszym działaniu wspólna jedynka występuje tylko na środkowej pozycji, dlatego wynikiem jest 010, czyli liczba 2.

W drugim na każdej pozycji przynajmniej jedna z liczb ma jedynkę. Otrzymujemy więc 111, czyli 7.

W trzecim jedynki pojawiają się tam, gdzie bity są różne. Wynik to 101, czyli 5.

Do operatorów bitowych należy też ~, który odwraca bity: zera zamienia na jedynki, a jedynki na zera. Za chwilę pokażemy, dlaczego nie oznacza to tego samego co logiczne zaprzeczenie.

A co z przesunięciami bitowymi?

Na liczbach całkowitych możemy również wykonywać przesunięcia bitowe: << w lewo i >> w prawo. Dla przykładowej liczby 6 wygląda to tak:

Dla nieujemnej liczby całkowitej przesunięcie w prawo o jedną pozycję odpowiada dzieleniu całkowitemu przez dwa. Przesunięcie w lewo o jedną pozycję odpowiada mnożeniu przez dwa, przy czym w C++ trzeba uwzględnić zakres używanego typu.

Różnica w zastosowaniu jest więc zasadnicza: operatorami logicznymi budujemy warunki, a bitowymi przetwarzamy poszczególne bity liczb.

To wyjaśnia też wątpliwość dotyczącą algebry Boole'a. Operacja bitowa rzeczywiście stosuje regułę AND, OR czy XOR do wartości 0 i 1. Robi to jednak osobno na kolejnych pozycjach. Wspólne podstawy matematyczne nie oznaczają, że operatory logiczne i bitowe w języku programowania są zamienne.

Dlaczego & czasami działa podobnie do &&, a | do ||?

Źródłem nieporozumienia może być to, że operatory bitowe da się zastosować również do wartości logicznych.

W C++ przy takim działaniu wartości typu bool są promowane do typu int: false staje się liczbą 0, a true liczbą 1. Dlatego bitowe AND i OR wykonane na dwóch wartościach logicznych mogą prowadzić do takiej samej decyzji w instrukcji if jak ich logiczne odpowiedniki.

Porównajmy wyniki:

W przypadku operatorów bitowych wykonujemy tutaj po prostu:

Zgodny wynik warunku nie oznacza jednak identycznego działania operatorów. Już typ wyniku w powyższym przykładzie jest inny.

Istotna jest również różnica w obliczaniu argumentów. Operator && nie oblicza prawej strony, gdy lewa jest fałszywa. Operator || nie oblicza prawej strony, gdy lewa jest prawdziwa. Operatory bitowe & i | nie zapewniają takiego pomijania drugiego argumentu.

Ma to praktyczne znaczenie. Warunek:

nie wykona dzielenia przez x, gdy x wynosi zero. Podmiana && na & pozbawia nas tego zabezpieczenia.

Nie możemy też przenieść obserwacji dotyczącej wartości 0 i 1 na dowolne liczby. Przykładowo:

Tutaj nawet wynik warunku będzie różny.

W Pythonie operatory &, | i ^ zastosowane do dwóch wartości bool zwracają wartości typu bool. Nadal nie stają się jednak zamiennikami operatorów logicznych, między innymi ze względu na brak pomijania drugiego argumentu. Dodatkowo operatory and i or w Pythonie użyte na innych typach mogą zwracać jeden z argumentów, a niekoniecznie True lub False.

Dlaczego ~ nie jest odpowiednikiem ! ani not?

Szczególnie łatwo popełnić błąd przy negacji. Skoro & czasami daje w warunku taki sam efekt jak &&, można odruchowo założyć, że ~ zadziała jak logiczne NOT. Tak nie jest.

W typowym współczesnym środowisku C++ otrzymamy:

Przy ~true wartość logiczna zostaje najpierw promowana do liczby całkowitej 1. Następnie operator odwraca bity tej liczby. Nie odwraca jedynie wartości logicznej z prawdy na fałsz.

Podobną różnicę zobaczymy w Pythonie, wykonując działania na liczbach całkowitych:

Obie liczby -2 i -1 są niezerowe, więc w warunku zostaną potraktowane jako prawda. Zastosowanie ~ zamiast negacji logicznej może zatem całkowicie zmienić działanie programu.

Do zanegowania warunku używamy więc ! w C++ albo not w Pythonie, a nie ~.

Czy zatem operatorów bitowych można używać w każdym zadaniu maturalnym?

Nie można tego uogólnić. Wróćmy do tego samego arkusza, ale tym razem do zadania 2.1, należącego do zadania „Liczby binarne”.

Polecenie i uwaga z Arkusz matury rozszerzonej z informatyki - 22 maja 2023, Formuła 2023:

Polecenie brzmi:

Zapisz w pseudokodzie lub w wybranym języku programowania algorytm, który dla danej dodatniej całkowitej liczby n obliczy liczbę bloków w jej zapisie binarnym.

Blok oznacza tutaj niepusty, maksymalny fragment złożony z jednakowych cyfr. Na przykład liczba 13 ma zapis binarny 1101, w którym wyróżniamy trzy bloki:

Na pierwszy rzut oka operatory bitowe mogłyby być przydatne. Można przecież odczytywać ostatni bit liczby za pomocą n & 1, a następnie przechodzić do kolejnych bitów przez przesunięcie n >> 1.

Jednak pod poleceniem znajduje się następująca uwaga:

Uwaga: W zapisie algorytmu możesz korzystać tylko z instrukcji sterujących, operatorów arytmetycznych: dodawania, odejmowania, mnożenia, dzielenia, dzielenia całkowitego i reszty z dzielenia; operatorów logicznych, porównań, instrukcji przypisania lub samodzielnie napisanych funkcji i procedur wykorzystujących powyższe operacje. Zabronione jest używanie funkcji wbudowanych oraz operatorów innych niż wymienione, dostępnych w językach programowania, w tym zwłaszcza funkcji zamiany między systemami pozycyjnymi i konwersji między typami danych.

To zamknięta lista dozwolonych operacji. Słowa „możesz korzystać tylko” oraz zakaz używania innych operatorów oznaczają, że nie wystarczy znaleźć dowolnego sposobu uzyskania poprawnego wyniku.

Na liście znajdują się operatory logiczne. Możemy więc łączyć warunki za pomocą koniunkcji i alternatywy oraz stosować negację. Nie wymieniono natomiast operatorów bitowych.

Z odczytania tej uwagi zgodnie z rozróżnieniem operatorów logicznych i bitowych wynika, że w rozwiązaniu zadania 2.1 nie należy wykorzystywać takich operacji jak n & 1 czy n >> 1. Uzasadnienie, że bitowe AND również odwołuje się do algebry Boole'a, nie znosi ograniczenia z polecenia.

Naruszenie ograniczeń może kosztować punkty, mimo poprawnego wyniku obliczeń. Nie należy jednak bez analizy konkretnego rozwiązania przesądzać dokładnej punktacji. To coś innego niż stwierdzenie, że każdy napotkany operator bitowy automatycznie oznacza zero punktów.

Problemem nie jest sama „konwersja na system binarny”

Warto doprecyzować jeszcze jeden argument. Operatory bitowe nie są funkcjami zamieniającymi liczbę na jej tekstowy zapis binarny. Przykładowo n & 1 wykonuje działanie na liczbach i zwraca wynik liczbowy, a nie napis złożony z zer i jedynek.

Nie trzeba więc podciągać operatorów bitowych pod zakaz funkcji konwersji. W tym zadaniu wystarczającym powodem jest to, że nie należą do wymienionego zestawu operacji.

Z tego samego powodu nie należy stosować reguły: „jeżeli nie ma zakazu konwersji, to na pewno wolno używać operatorów bitowych”. Zawsze czytamy całe polecenie i wszystkie jego ograniczenia.

Jak rozwiązać zadanie 2.1 bez operatorów bitowych?

Operatory bitowe nie są tutaj konieczne. Przykładowe rozwiązanie CKE wykorzystuje resztę z dzielenia przez dwa, dzielenie całkowite przez dwa oraz porównywanie kolejnych cyfr binarnych.

Poniżej zapis tej metody w Pythonie:

Zaczynamy od jednego bloku, ponieważ dodatnia liczba ma niepusty zapis binarny. Reszta z dzielenia przez dwa daje ostatnią cyfrę tego zapisu. Dzielenie całkowite przez dwa pozwala przejść do następnej.

Pętla analizuje więc cyfry od prawej do lewej. Za każdym razem, gdy kolejna cyfra różni się od poprzedniej, zwiększamy liczbę bloków. To właśnie mechanizm zastosowany w rozwiązaniu z zasad oceniania.

Nie potrzebujemy gotowej funkcji konwersji, napisu z zapisem binarnym ani operatorów bitowych. Wystarczają operacje dopuszczone w uwadze.

Najważniejsza zasada: liczy się treść konkretnego podpunktu

Przy rozwiązywaniu zadania maturalnego trzeba sprawdzić nie tylko, co mamy obliczyć, lecz także w jaki sposób wolno nam to zrobić.

Wskazanie „zapisz algorytm w wybranym języku programowania” nie oznacza automatycznie przyzwolenia na wszystkie możliwości tego języka. Polecenie może ograniczać dostępne operatory, funkcje albo sposób realizacji rozwiązania.

Jednocześnie ograniczenia umieszczonego przy jednym podpunkcie nie należy przenosić na cały arkusz. Nasze dwa przykłady pokazują tę różnicę: w zadaniu 3 nie wskazano analogicznego ograniczenia, natomiast w zadaniu 2.1 zapisano zamkniętą listę dozwolonych operacji.

Poprawność obliczeń i zgodność z poleceniem to dwa osobne wymagania. Informator CKE również podkreśla znaczenie zgodności rozwiązania z poleceniem i warunkami zadania, a nie wyłącznie zgodności odpowiedzi z oczekiwanym wynikiem.

A co z bibliotekami i dowolnością programowania?

Gdy zadanie nie wprowadza dodatkowych ograniczeń, możemy korzystać ze zwykłych możliwości wybranego języka, w tym jego funkcji i biblioteki standardowej dostępnych w środowisku egzaminacyjnym. Nie należy jednak rozumieć tego jako zgody na korzystanie z dowolnego oprogramowania.

Nie można samodzielnie doinstalowywać brakujących bibliotek ani żądać ich instalacji przez operatora pracowni.

Zdający nie może samodzielnie instalować, a także żądać zainstalowania przez operatora pracowni informatycznej dodatkowego oprogramowania, w tym dodatkowych modułów dla środowisk programowania, na komputerze przydzielonym mu do egzaminu.

Dlatego w przygotowaniach warto opierać rozwiązania na standardowej bibliotece języka i sprawdzonym środowisku egzaminacyjnym. Nie zakładaj, że pakiet zainstalowany na Twoim domowym komputerze będzie dostępny również na maturze. Importowanie modułu należącego do biblioteki standardowej Pythona to inna sytuacja niż doinstalowywanie zewnętrznego pakietu.

Oddawany program powinien działać w wymaganym środowisku i pozwalać odtworzyć uzyskane wyniki. Pamiętaj też o przekazaniu wszystkich wymaganych plików: w zadaniach praktycznych CKE wymaga komputerowej realizacji rozwiązania, a nie wyłącznie gotowych odpowiedzi.

Odpowiadając więc na pytanie Maksa: samo użycie operatorów bitowych nie jest ogólnie zabronione na maturze. Nie wolno jednak utożsamiać ich z operatorami logicznymi ani pomijać ograniczeń konkretnego polecenia. Najpierw ustalamy, jak działa użyty operator, a następnie sprawdzamy, czy dane zadanie pozwala z niego skorzystać.