Rumah > Artikel > pembangunan bahagian belakang > Nombor yang keji
Sesuatu nombor dianggap ganjil jika mempunyai nombor ganjil satu dalam pengembangan binarinya. 10 nombor ganjil pertama ialah 1,2,4,7,10,11,13,14,16,19,21. Menariknya, semua kuasa 2 adalah nombor ganjil kerana ia hanya mempunyai set 1 bit.
Artikel berikut membincangkan secara terperinci dua kaedah untuk menentukan sama ada nombor adalah nombor yang dibenci.
Tujuan soalan ini adalah untuk menyemak sama ada nombor yang diberikan adalah nombor keji, iaitu nombor positif dengan bilangan bit set ganjil dalam pengembangan binarinya.
Input: 34
Output: Non-Odious Number
Perwakilan binari 34 ialah 10010.
Tetapkan bilangan digit = 2.
Oleh kerana nombor 1 adalah nombor genap, 34 bukanlah nombor yang mengerikan.
Input: 1024
Output: Odious Number
Perwakilan binari 1024 ialah 10000000000.
Tetapkan bilangan digit = 1.
Memandangkan 1024 adalah kuasa 2, hanya terdapat 1 bit tetapan. Jadi ia adalah nombor yang menakutkan.
Input: 53
Output: Non-Odious Number
(53)10 = (110101)2
Tetapkan bilangan digit = 4.
Jadi, ia bukan nombor yang keji.
Untuk menentukan sama ada sesuatu nombor itu dibenci, kita mesti tahu sama ada bilangan digit yang ditetapkan ialah nombor ganjil atau genap. Tugas utama di sini ialah mengira bilangan digit yang ditetapkan dalam pengembangan binari nombor tersebut. Teknik berikut boleh digunakan untuk mengira bilangan digit dan kemudian menyemak sama ada keputusannya ganjil atau genap.
Terjemahan bahasa Cina bagiGunakan operator gelung dan anjakan kanan untuk meneliti semua digit nombor satu demi satu.
Jika nilai bit ialah 1, tambahkan kiraan sebanyak satu.
Semak sama ada nilai akhir kiraan adalah ganjil atau genap.
Tunjukkan jawapan.
Fungsi no_of_set_bits()
Kiraan permulaan = 0
apabila (n > 0)
if ((n & 1) > 0) Increment count Right Shift n
Kira pulangan
Fungsi adalah_odious()
Jika (kira adalah nombor ganjil)
kembali benar
Lain-lain
kesilapan pemulangan
Fungsi utama()
Memulakan n
Panggilan fungsi no_of_set_bits()
Fungsi panggilan adalah_odious()
Cetak
Program ini menyemak sama ada sesuatu nombor itu menyinggung atau tidak. Ia menyemak bit paling kanan dalam setiap lelaran gelung dengan mengalihkan nilai ke kanan dengan n pada akhir setiap lelaran dalam fungsi no_of_set_bits().
#include<iostream> using namespace std; // this function counts the number of set bits by analyzing the rightmost bit using a while loop till n > 0. // it performs logical & operation between 1 and n to determine if the rightmost bit is set or not. // if it is set, count is incremented by 1 // right shift the value of n to make the bit left of the rightmost bit, the new rightmost bit. int no_of_set_bits(int n){ int count = 0; while (n > 0){ // if the rightmost bit is 1: increment count if ((n & 1) > 0){ count++; } // right shift the value of n to examine the next bit n = n >> 1; } return count; } // this function determines if count of set bits is odd or even // odd -> odious bool is_odious(int count){ // if count is odd return true if (count % 2 != 0){ return true; } return false; } // main function int main(){ int n = 27; int countBits = no_of_set_bits(n); if (is_odious(countBits)){ cout << n << " is Odious Number"; } else { cout << n << " is Non-Odious Number"; } return 0; }
27 is Non-Odious Number
Kerumitan masa: O(log(n)), memandangkan pengembangan binari n memerlukan bit log2n, kami menyemak semua bit untuk menyemak yang mana yang ditetapkan.
Kerumitan ruang: O(1), kerana tiada ruang tambahan digunakan.
Algoritma ini boleh digunakan untuk mengira set nombor digit dalam nombor dengan cara yang lebih cekap. Fungsi is_odious() kemudiannya boleh digunakan untuk menentukan sama ada nombor itu menyinggung perasaan.
Prinsip asas kaedah ini ialah mengosongkan bit set paling kanan berulang kali sambil menjejaki bilangan lelaran yang diperlukan untuk mencapai sifar. Langkah-langkah yang terlibat ialah -
Mulakan kiraan kepada 0
Apabila nombor lebih besar daripada sifar, lakukan bitwise & antara nombor dan pelengkap 2nya untuk menyahset bit set paling kanan.
Kiraan ditambah setiap lelaran gelung.
Semak sama ada kiraan akhir adalah ganjil.
Tunjukkan hasil.
Biar nombor itu 10. Peluasan binari 10 ialah 1010. Ia boleh diperhatikan bahawa ia mempunyai 2 bit tetapan.
Lelaran gelung 1 -
n = 10 n & (n-1) = 10 & 9 1010 (n) 1001 (n - 1) 1000 (n = 8)
Lelaran gelung 2 -
n = 8 n & (n-1) = 8 & 7 1000 (n) 0111 (n-1) 0 (n = 0)
Bilangan lelaran = bilangan tetapan = 2.
Fungsi no_of_set_bits()
Kiraan permulaan = 0
apabila (n > 0)
n = n & (n-1)
Tingkatkan bilangan
Kira pulangan
Fungsi adalah_odious()
Sama seperti kaedah sebelum ini
Fungsi utama()
Sama seperti kaedah sebelum ini
Program ini mengira bilangan bit set dengan mengira bilangan lelaran yang diperlukan untuk menyahset semua bit set. Untuk membatalkan bit, kami melakukan operasi AND bitwise pada n dan n-1. Ini kerana perwakilan binari n-1 membalikkan bit set paling kanan n dan semua bit yang mengikutinya.
#include<iostream> using namespace std; // this function counts the number of set bits by unsetting the rightmost set bit using a while loop till n > 0. // it performs logical & operation between n and n - 1 to unset the rightmost set bit. // count is incremented in every iteration int no_of_set_bits(int n){ int count = 0; while (n > 0){ // update the value of n to unset the current rightmost set bit n = n & (n - 1); count++; } return count; } // this function determines if count of set bits is odd or even // odd -> odious bool is_odious(int count){ // if count is odd return true if (count % 2 != 0){ return true; } return false; } // main function int main(){ int n = 27; int countBits = no_of_set_bits(n); // function call if (is_odious(countBits)){ cout << n << " is Odious Number"; } else { cout << n << " is Non-Odious Number"; } return 0; }
27 is Non-Odious Number
Kerumitan Masa - O(log(x)), dengan x ialah bilangan digit yang ditetapkan dalam nombor itu. Jika terdapat hanya 1 set bit, gelung akan dijalankan sekali.
Kerumitan ruang - O(1) kerana tiada ruang tambahan digunakan.
Walaupun kaedah pertama agak mudah difahami, ia memerlukan lelaran log(n) untuk menghasilkan hasil akhir. Kaedah kedua, sebaliknya, menggunakan lelaran log(x), di mana x ialah bilangan digit yang ditetapkan dalam pengembangan binari nombor itu. Oleh itu, ia meningkatkan prestasi.
Artikel ini membincangkan dua cara untuk menyemak sama ada nombor itu menjijikkan. Ia juga memberikan kita konsep kaedah, contoh, algoritma yang digunakan, penyelesaian program C++ dan analisis kerumitan setiap kaedah. Ia juga membandingkan kedua-dua kaedah untuk menentukan yang lebih berkesan.
Atas ialah kandungan terperinci Nombor yang keji. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!