Uji apakah suatu bilangan genap

Masalah

Anda ingin menguji apakah suatu bilangan genap.

Larutan

Nah, solusi yang umum dilakukan adalah dengan menguji nilai n modulo 2. Jika nol, maka bilangan tersebut genap, jika tidak maka ganjil. Tapi seberapa cepatnya?

Berikut cuplikan Pascal:

procedure Main();
var
  i: Integer;
  total: Integer = 0;
begin
  for i := 0 to MaxInt-1 do
    begin
      if i mod 2 = 0 then
        total += 1;
    end;

  WriteLn(total);
end;

Kompilasi dan jalankan:

$ fpc -O3 main.pas
$ time ./main
1073741824
./main  16,61s user 0,00s system 99% cpu 16,634 total

16 detik! Itu banyak… Mari kita coba pendekatan alternatif. Mari kita lakukan operasi bitwise. Anda dapat menggunakan operator AND bitwise and periksa bit terkecil dari bilangan bulat. Jika bit paling tidak signifikan adalah 0jumlahnya genap; jika itu 1jumlahnya ganjil.

procedure Main();
var
  i: Integer;
  total: Integer = 0;
begin
  for i := 0 to MaxInt-1 do
    begin
      if (i and 1) = 0 then      // <- HERE
        total += 1;
    end;

  WriteLn(total);
end;

$ fpc -O3 main.pas
$ time ./main
1073741824
./main  1,19s user 0,00s system 99% cpu 1,189 total

Jauh lebih baik 🙂 Tapi bagaimana dengan C? Mari kita mencobanya:

int main()
{
    int total = 0;

    for (int i = 0; i < 2147483647; ++i)
    {
        if (i % 2 == 0)                     // version 1
        // if ((i & 1) == 0)                // version 2
        {
            ++total;
        }
    }

    printf("%dn", total);

    return 0;
}

$ gcc -O3 main.c
$ time ./a.out
1073741824
./a.out  0,26s user 0,00s system 99% cpu 0,264 total

Saya mencoba kedua versi (modulo 2 dan bitwise AND) dan mendapatkan hasil yang sama. Saya pikir pengoptimal mengenali modulo 2 dan mengubahnya menjadi bitwise DAN.