skip to Main Content

Określanie parzystości liczby

Często operacja modulo (wynikiem takiej operacji jest reszta z dzielenia) jest wykonywana na wartości 2. Pozwala to określić czy badana liczba jest parzysta.

Ostatnio uświadomiłem sobie, że sprawdzenie czy liczba jest parzysta można wykonać przez operację bitową. Wynika to z faktu że liczby nieparzyste posiadają pierwszy bit (od prawej strony) ustawiony na 1.

Pobawiłem się w badacza, napisałem program który wygląda tak (działa tylko na Windows):

Kolejne etapy działania programu:

  1. Wypełnianie tablicy 100 (lub więcej zależy od ARRAY_SIZE) elementami, który mają pseudolosowy (bardzo pseudo) charakter. obliczany za pomocą INT_MAX – rand()
  2. Jednostką liczącą upływający czas pomiędzy dwoma okresami jest GetTickCount() funkcja znajdująca się w Windows.h (a konkretniej w winbase.h). Funkcja time() ma charakter sprawdzenia czy poprzednia dobrze działa.
  3. Potem wykonują się dwie zagnieżdżone pętle, zewnętrzna duża do wartości NUMBER_TIRES i wewnętrzna przechodząca po elementach tablicy.
  4. W zależności od parzystości, lub nie jest ustawiana 1 lub 0 w zmiennej k. Ma na celu przeciw działanie ewentualnej optymalizacji programu, która by usunęła pętlę skoro one nic nie robią.
Wyniki
Zakładałem że operacja bitowa będzie szybsza od modulo z powodu, że jest nie taka typowa dla tego zagadnienia :).
Jednak wyniki są takie (liczba prób 100000000, rozmiar tablicy 100) : 
  • Czas operacji bitowej to: 49920 milisekund (około 50 sekund)
  • Czas operacji modulo to: 48891 milisekund (około 49 sekund)
  • Różnica czasu to 1029 milisekund na korzyść operacji modulo (około 1 sekundy)

Paweł Sołtysiak

Programista, domowy kucharz i "amator amerykańskiej polityki".
Zbieram informacje z całej sieci, po odrzuceniu chwastów i dodaniu swojej opinii publikuje na blogu.

  • Ekhm… W procesie optymalizacji kompilator sam zamienia modulo, w których występują potęgi dwójki, na operacje bitowe…

Back To Top