可憎的数字

如果一个数字在其二进制展开中有奇数个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中文网其他相关文章！