可憎的數字

如果一個數字在其二進位展開式中有奇數個1，則被認為是奇異數。前10個奇異數是1,2,4,7,10,11,13,14,16,19,21。有趣的是，所有2的冪都是奇異數，因為它們只有1個位元被設定。

下面的文章詳細討論了兩種判斷一個數字是否為可惡數字的方法。

問題陳述

這個問題的目的是檢查給定的數字是否是一個可惡的數字，即它是一個在其二進制展開中具有奇數個設定位的正數。

令人厭惡的數字範例

Input: 34

Output: Non-Odious Number

說明

34的二進位表示是10010。

設定位數 = 2。

由於1的數量是偶數，34不是一個可怕的數字。

Input: 1024

Output: Odious Number

說明

1024的二進位表示為10000000000。

設定位數 = 1。

由於1024是2的冪，所以只有1個設定位。因此它是一個可怕的數字。

Input: 53

Output: Non-Odious Number

說明

(53)₁₀ = (110101)₂

設定位數 = 4。

因此，它不是一個可憎的數字。

解決方案

為了判斷一個數字是否是可惡的，我們必須知道設定的位數是奇數還是偶數。這裡的主要任務是統計數字的二進制展開中設定的位數。可以採用以下技術來計算位數，然後檢查結果是奇數還是偶數。

Naive Approach

的中文翻譯為：

天真的方法

• 使用迴圈和右移運算子逐一遍曆數字的所有位元。

• 如果位元值為1，則將計數增加一。

• 檢查 count 的最終值是奇數還是偶數。

• 顯示答案。

虛擬程式碼

函數 no_of_set_bits()

• 初始化計數 = 0

• #當 (n > 0)

if ((n & 1) > 0)
   Increment count
Right Shift n

• 返回計數

函數 is_odious()

• 如果 (count 是奇數)

返回真

• 其他

回傳錯誤

函數main()

• 初始化 n

• 函數呼叫 no_of_set_bits()

• #呼叫函數 is_odious()

• 列印輸出

範例：C 程式

該程式檢查一個數字是否令人厭惡。它透過在函數 no_of_set_bits() 中每次迭代結束時右移 n 的值來檢查循環每次迭代中最右邊的位元。

#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

時間與空間的分析

時間複雜度：O(log(n))，因為 n 的二進位展開需要 log2n 位，我們檢查所有位元以檢查設定的位元。

空間複雜度：O(1)，因為沒有使用額外的空間。

Brian Kernighan 的演算法方法

此演算法可用於以更有效的方式計算數字的設定位數。然後可以使用函數 is_odious() 來確定該數字是否令人厭惡。

這種方法的基本原理是重複清除數字最右邊的設定位，同時追蹤需要多少次迭代才能達到零。涉及的步驟是 -

• 將計數初始化為0

• #當數字大於零時，在數字與其 2 的補碼之間執行位元 & 以取消設定最右邊的設定位。

• 每次循環迭代都會增加計數。

• 檢查最終計數是否為奇數。

• 顯示結果。

範例

設數字為10。10的二進位展開為1010。可以觀察到它有2個設定位。

循環迭代 1 -

#

n = 10
n & (n-1) =  10 & 9
1010   (n)
1001   (n - 1)
1000   (n = 8)

循環迭代 2 -

#

n = 8
n & (n-1) = 8 & 7
1000    (n)
0111	(n-1)
0       (n = 0) 

迭代次數 = 設定位數 = 2。

虛擬程式碼

函數 no_of_set_bits()

• 初始化計數 = 0

• #當 (n > 0)

n = n & (n-1)

增加計數

• 返回計數

函數 is_odious()

與先前的方法相同

函數main()

與先前的方法相同

範例：C 程式

這個程式透過計算需要取消所有設定位所需的迭代次數來計算設定位的數量。為了取消位，我們對n和n-1執行位與操作。這是因為n-1的二進位表示會翻轉n的最右邊的設定位以及其後面的所有位。

#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

時空分析

時間複雜度 - O(log(x))，其中 x 是數字中設定的位數。如果只有 1 個設定位，則循環將運行一次。

空間複雜度 - O(1)，因為沒有使用額外的空間。

比較上述方法

雖然第一種方法相當容易理解，但需要 log(n) 次迭代才能產生最終結果。另一方面，第二種方法採用 log(x) 迭代，其中 x 是數字的二進位展開中設定的位數。因此，它提高了性能。

結論

本文討論了兩種檢查數字是否令人厭惡的方法。它還為我們提供了該方法的概念、範例、使用的演算法、C 程式解決方案以及每種方法的複雜性分析。它還對兩種方法進行了比較，以確定哪種方法更有效。

以上是可憎的數字的詳細內容。更多資訊請關注PHP中文網其他相關文章！