Saya menemukan sebuah lowongan menarik, yaitu setiap kandidatnya diharuskan mengerjakan sebuah soal dan jawabannya dikirimkan beserta surat lamaran.
A complement of a number is defined as inversion (if the bit value = 0, change it to 1 and vice-versa) of all bits of the number starting from the leftmost bit that is set to 1.
For example, if N = 5, N is 101 in binary. The complement of N is 010, which is 2 in decimal. Similarly if N = 50, then complement of N is 13
Complete the function getIntegerComplement(). This function takes N as it’s parameter. The function should return the complement of N.Constraints :
0 ≤ N ≤ 100000.
Sample Test Cases:Input #00:
50Output #00:
13Explanation:
50 in decimal form equals: 110010.
Inverting the bit sequence: 001101. This is 13 in decimal
Input #01:
100Output #01:
27Explanation:
The bit sequence for 100 equals 1100100.
Inverting the sequence we get 0011011 which is 27 in decimal.
Tidak ada keterangan harus menggunakan bahasa pemrograman tertentu. Saya coba kerjakan dengan PHP dengan syarat tidak menggunakan fungsi bawaan PHP decbin() atau sebaliknya bindec(). Kita disuruh mencari complement bit dari masukan berupa bilangan desimal.
Pertama kali kita harus mengkonversi bilangan tersebut menjadi bentuk biner (secara visual, karena pada dasarnya komputer hanya mengenal bilangan biner). Konversi dari desimal ke biner dapat dilakukan dengan menyimpan hasil bagi bilangan desimal dengan angka 2 dan menuliskannya secara terbalik dari hasil yang terakhir sampai hasil yang pertama. Kemudian hasilnya diubah satu persatu dari yang semula 0 ke 1 dan sebaliknya.
<?php
while ($input != 0) {
$sisa[$i] = ~($input % 2) + 2;
$input = floor($input / 2);
$i++;
}
Kode di atas untuk memperoleh sisa hasil bagi, sekaligus dicari complement-nya. Namun kenapa harus ditambah 2? Karena komputer hanya mengenal bilangan biner, jadi kita harus menyesuaikan cara berpikir komputer. Kemudian komputer juga menggunakan two’s complement untuk operasi bilangan binernya. Sehingga angka 0 setelah di-complement akan menghasilkan -1 dan angka 1 akan menghasilkan -2. Hal ini tentu saja tidak sesuai harapan. Jadi ditambahkan dengan angka 2 sehinggan 0 -> -1 + 2 = 1 dan 1 -> -2 + 2 = 0.
Penjelasannya adalah sebagai berikut. Misalnya pada komputer 8 bit, angka 0 bagi komputer adalah 0000 0000, jika dibalik menjadi 1111 1111. Bilangan biner 1111 1111 adalah two’s complement dari angka 1. Buktinya angka 1 biner 0000 0001 dibalik menjadi 1111 1110 lalu ditambah 1 = 1111 1111. Jadi pernyataan ~0 akan menghasilkan two’s complement dari 1. Operator tilde (~) hanya berfungsi membalik bit, interpretasi angkanya tetap bergantung kepada komputer.
Tugas selanjutnya adalah mengkonversi lagi bilangan biner ke desimal. Caranya adalah dengan mengalikan tiap-tiap bit (dimulai dari LSB) dengan 2^0, 2^1, dst sampai ke MSB (most-significant bit), kemudian semua hasilnya dijumlahkan. Bilangan biner yang disimpan pada array sisa[] di atas urut dari LSB ke MSB (tidak diminta tampilannya jadi tidak perlu dibalik-balik urutannya).
<?php
foreach($sisa as $key => $value) {
if ($key == 0) {
$output = $value * 1;
continue;
}
$output += $value * pangkat($key);
}
echo $output;
Sebenarnya di PHP sudah ada fungsi pangkat, tapi kita buat sendiri aja toh sederhana ini. Sekaligus mengurangi ketergantungan terhadap satu bahasa.
<?php
function pangkat($a) {
if ($a == 1)
return 2;
else
return 2 * pangkat($a - 1);
}
Fungsi di atas rekursif. Parameternya adalah indeks dari array sisa[], jadi kalau indeks 3 berarti 2 * 2 * 2. Berikut ini ada listing lengkapnya.
<?php
$input = 50;
$output = 0;
$sisa[] = 0;
$i = 0;
if ($input >= 0 && $input <= 100000) {
if ($input == 0)
echo 1;
else {
while ($input != 0) {
$sisa[$i] = ~($input % 2) + 2;
$input = floor($input / 2);
$i++;
}
foreach($sisa as $key => $value) {
if ($key == 0) {
$output = $value * 1;
continue;
}
$output += $value * pangkat($key);
}
echo $output;
}
}
function pangkat($a) {
if ($a == 1)
return 2;
else
return 2 * pangkat($a - 1);
}