Power of Two
Kamu mendapatkan bilangan bulat n. Kembalikan true jika n adalah pangkat dua, yang berarti n = 2^k untuk suatu bilangan bulat k ≥ 0, dan false jika tidak. Jadi, 1, 2, 4, dan 8 termasuk, sedangkan 0, 6, dan semua bilangan negatif tidak.
Fungsi
- ninteger
- bilangan bulat yang akan diuji, yang bisa bernilai nol atau negatif
- Mengembalikanboolean
- benar jika n sama dengan 2^k untuk suatu k ≥ 0, selain itu salah
Batasan
-231 ≤ n ≤ 231-1
Contoh
- Input
- n = 16
- Output
- true
- Penjelasan
- 16 = 2 × 2 × 2 × 2 = 2^4. Dalam biner, nilainya adalah
10000, dengan satu bit 1.
- Input
- n = 24
- Output
- false
- Penjelasan
- 24 = 8 × 3. Membaginya menjadi dua menghasilkan 12, 6, lalu 3, yang merupakan bilangan ganjil tetapi bukan 1. Dalam biner, 24 adalah
11000, dengan dua bit 1.
- Input
- n = 1
- Output
- true
- Penjelasan
- 1 = 2^0, jadi ini adalah pangkat dua. Bentuk binernya
1memiliki tepat satu bit 1.
Pertanyaan lanjutan
Dengan trik bit yang sama, bisakah kamu menguji apakah n adalah pangkat empat tanpa perulangan?
Petunjuk
Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.
Tuliskan beberapa pangkat dua dalam biner:
1,10,100,1000. Apa kesamaan semuanya yang tidak dimiliki 6 (110)?Pangkat dua memiliki tepat satu bit 1. Bandingkan
ndengann-1dalam biner: mengurangi 1 mengubah bit 1 terendah menjadi 0 dan setiap bit 0 di bawahnya menjadi 1.Jadi,
nadalah pangkat dua tepat ketika nilainya positif dan operasi AND antara nilai tersebut dengann-1menghasilkan 0. Periksa tandanya sebelum bit-bitnya, karena 0 dan bilangan negatif tidak pernah menjadi pangkat dua.
Solusi
Dalam biner, pangkat dua adalah satu bit 1 yang diikuti nol, seperti 10000 untuk 16. Kamu bisa memastikan bentuk itu dengan membagi n menjadi dua berulang kali hingga hasilnya ganjil, atau dalam satu langkah dengan n & (n-1), yang menghapus bit 1 paling rendah dan menghasilkan 0 hanya jika bit itu satu-satunya. Periksa nol dan bilangan negatif terlebih dahulu.
Bagi dengan 2 selama angkanya genap
Intuisi
Membagi 2^k dengan 2 tepat sebanyak k kali akan menghasilkan 1, dan setiap nilai dalam prosesnya genap. Bilangan dengan faktor ganjil lebih dari 1 akan berhenti dibagi dua pada bilangan ganjil yang bukan 1.
Kembalikan false untuk n ≤ 0 sebelum perulangan. Tidak ada pangkat dua yang bernilai nol atau negatif, dan 0 adalah genap serta jika dibagi dua tetap 0, sehingga perulangan tidak akan pernah berakhir. Setiap langkah membagi dua n, jadi input 32-bit membutuhkan paling banyak 31 langkah.
Algoritma
- Jika
n ≤ 0, kembalikan false. - Selama
ngenap, bagi dengan 2. - Kembalikan apakah
nsekarang 1.
def isPowerOfTwo(n):
if n <= 0:
return False
while n % 2 == 0:
n //= 2
return n == 1Hapus bit 1 terendah dengan n & (n-1)
Intuisi
Mengurangi 1 mengubah bit 1 terendah menjadi 0 dan setiap 0 di bawahnya menjadi 1, sementara bit yang lebih tinggi tetap sama. Pangkat dua tidak memiliki bit yang lebih tinggi: 16 adalah 10000, 15 adalah 01111, dan 16 & 15 bernilai 0. Bilangan positif lainnya memiliki bit 1 yang lebih tinggi dan muncul pada kedua bilangan, sehingga operasi AND tidak menghasilkan 0. Untuk 24, kamu mendapatkan 11000 & 10111, yang hasilnya adalah 10000.
Periksa n > 0 terlebih dahulu. 0 & -1 bernilai 0, dan dalam aritmetika 32-bit, -2^31 terdiri dari satu bit 1 diikuti 31 nol, jadi operasi AND saja akan menerima keduanya. Seluruh pengujian terdiri dari satu perbandingan, satu pengurangan, dan satu operasi AND.
Algoritma
- Jika
n ≤ 0, kembalikan false. - Hitung
n & (n-1), yaitundengan bit 1 terendahnya dihapus. - Kembalikan apakah hasilnya 0.
def isPowerOfTwo(n):
# One set bit: n - 1 flips it and every bit below, so the AND is 0.
return n > 0 and n & (n - 1) == 0
Jebakan dan kasus tepi
- Melewatkan pemeriksaan tanda. 0 lolos tes AND, dan pada bilangan bulat 32-bit,
-2^31juga lolos, karena hanya memiliki satu bit 1. Keduanya harus menghasilkan false. - Menjalankan perulangan pembagian dua pada 0. Nol adalah bilangan genap dan jika dibagi dua tetap menjadi 0, sehingga perulangan tidak pernah berakhir.
- Menghilangkan tanda kurung.
==memiliki prioritas lebih tinggi daripada&, sehingga dalam C, C++ dan JavaScript,n & n - 1 == 0berartin & ((n - 1) == 0)dan menghasilkan jawaban yang salah tanpa error. Tulis(n & (n - 1)) == 0. - Menggunakan logaritma. Dalam presisi ganda,
log(536870912) / log(2)bernilai 29.000000000000004, sehingga pemeriksaan bilangan bulat menganggap2^29bernilai false.
Pertanyaan yang sering diajukan3
Bagaimana cara memeriksa apakah suatu angka merupakan pangkat dua?
Kembalikan true saat n > 0 dan n & (n-1) sama dengan 0. Pangkat dua memiliki tepat satu bit 1, dan n & (n-1) menghapusnya. Tanpa operasi bit, bagi dua n selama nilainya genap, lalu periksa apakah hasil akhirnya 1.
Apa kompleksitas waktu dari Power of Two?
Pemeriksaan n & (n-1) berjalan dalam waktu dan ruang O(1). Perulangan halving berjalan dalam waktu O(log n), paling banyak 31 langkah untuk bilangan bulat 32-bit.
Apakah 1 merupakan pangkat dua? Apakah 0?
1 adalah pangkat dua, karena 2^0 = 1. 0 bukan pangkat dua: tidak ada eksponen bilangan bulat yang menghasilkan 0, dan bilangan ini sama sekali tidak memiliki bit 1. Bilangan negatif juga tidak pernah menjadi pangkat dua.
Soal serupa
Soal yang memakai ide yang sama. Mengerjakan dua atau tiga di antaranya membuat polanya melekat.
def isPowerOfTwo(n):
# Tulis kodemu di siniTes #1
Tes #2
Tes #3
Argumen
n = 16
Output yang diharapkan
true