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.

Pernyataan Masalah

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.

Contoh Nombor Jijik

Input: 34

Output: Non-Odious Number

Arahan

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

Arahan

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

Arahan

(53)₁₀ = (110101)₂

Tetapkan bilangan digit = 4.

Jadi, ia bukan nombor yang keji.

Penyelesaian

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.

Pendekatan Naif

Pendekatan Naif

• Gunakan 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.

pseudokod

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

Contoh: program C++

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;
}

Output

27 is Non-Odious Number

Analisis masa dan ruang

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.

Kaedah Algoritma Brian Kernighan

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.

Contoh

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.

pseudokod

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

Contoh: program C++

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;
}

Output

27 is Non-Odious Number

Analisis ruang-masa

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.

Bandingkan kaedah di atas

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.

Kesimpulan

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!