C++ 庸俗数

如果一个数在其二进制展开中有奇数个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) 10 = (110101) 2

设置位数 = 4.

因此它不是冤鬼数。

解决方案方法

为了确定一个数字是否是冤鬼数，我们必须知道设置位数是奇数还是偶数。这里的主要任务是计算数字的二进制展开中的设置位数。可以使用以下技术来计算位数，然后检查结果是奇数还是偶数。

原生方法

通过循环和右移运算符逐位遍历数字。
如果位值为1，则将计数增加一。
检查计数的最终值是奇数还是偶数。
显示答案。

伪代码

函数 no_of_set_bits()

初始化计数 = 0
while (n > 0)

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

返回计数

函数 is_odious()

如果（计数是奇数）

返回真

否则

返回假

函数 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位，并且我们要检查所有位是否为1。

空间复杂度：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()

初始化count=0
while（n > 0）

n=n &（n-1）

递增count

返回count

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