Pangkat 2
Pelajaran 9 dari 17 dalam kursus Manipulasi Bit di Coddy.
Jika kamu sudah cukup sering bermain dengan bilangan biner, hingga saat ini kamu pasti menyadari bahwa setiap pangkat 2 hanya memiliki 1 bit set (bit set merujuk pada '1'). Contohnya, (2)10 = (10)2 , (4)10 = (100)2 , (8)10 = (1000)2 dan seterusnya.
Dalam pelajaran ini, kita akan membahas masalah berikut:
Tentukan apakah suatu bilangan merupakan pangkat 2 atau bukan menggunakan manipulasi bit.
Oke! Jadi, bagaimana pengamatan di atas bisa membantu kita? Mari kita cari tahu.
- Misalkan (8)10 diberikan kepada kita dan kita tahu bahwa bilangan ini adalah pangkat 2.
- Jika kita menguranginya dengan 1, kita mendapatkan (7)10 yang setara dengan (0111)2.
- Jika kita melakukan operasi AND ( & ) pada 7 dan 8, kita mendapatkan 0.
- Menarik, bukan? Mari kita periksa bilangan lain yang juga merupakan pangkat 2. Ambil (32)10 yang setara dengan (100000)2, lalu kurangi dengan 1, yaitu (31)10 = (011111)2. Kita mendapatkan 0 lagi!
- Jadi, untuk menggeneralisasi hal ini, dapatkah kita mengatakan bahwa untuk bilangan yang kita sebut x, agar menjadi pangkat 2, ( x & (x-1) ) akan selalu bernilai '0'?
Dengan menggunakan pengamatan ini, kita dapat menyelesaikan soal dengan mudah tanpa perlu menggunakan library matematika dan fungsi pangkatnya. Kita juga tidak perlu menggunakan perulangan. Kita baru saja menyelesaikannya dengan kompleksitas waktu O(1)! Keren, bukan? Begitulah manipulasi bit dapat membantu kita mengoptimalkan program hingga tingkat yang baik sekaligus membuat kode tidak terlalu rumit.
Tantangan
MudahDiberikan sebuah angka, tentukan apakah angka tersebut genap menggunakan manipulasi bit.
Coba sendiri
#include <iostream>
using namespace std;
bool IsPowerOf2(int num) {
// Tulis kodemu di sini
}Semua pelajaran di Manipulasi Bit
Latihan sendiri: Compiler C++ online
Periksa konversi: Konverter Basis Bilangan