-
Perhatikan program di bawah ini
var sum, i, j, n, c : integer; begin readln(n); sum := 0; for i := 2 to n do begin c := 0; j := i; while (j > 0) do begin if (j mod 2 = 1) then c := c + 1; j := j div 2; end; if (c = 1) then sum := sum + 1; end; writeln(sum); end.
Jika potongan program dijalankan dengan masukan n = 2013, maka program akan menuliskan keluaran …
Perulangan i untuk memeriksa dari 2 sampai n dan perulangan while j berguna untuk memeriksa jumlah bit 1 tiap bilangan tersebut, jika mod 2 = 1 dan kemudian dibagi 2. Jika bit 1 hanya berjumlah 1, maka nilai sum akan bertambah pula. Bilangan yang memiliki bit 1 pada biner hanyalah bilangan 2 pangkat (2n). Sehingga nilai sum akan sama dengan banyaknya bilangan 2 pangkat dari 2 sampai n.
Banyaknya bilangan 2 pangkat dari 2 sampai 2013 adalah 10, yaitu (2,4,8,16,32,64,128,256,512,1024).
Dengan cara lain dapat dihitung dengan menggunakan jumlah (digit) bit dari n – 1 (karena 1 tidak termasuk).
(2013)2 = 0b11111011101
Karena 2013 memiliki 11 bit, maka total bilangan dua pangkat di bawah 2013 selain 1 adalah 11-1 = 20.