数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究讨厌数
如果一个数的二进制表示中 1 的个数为奇数，则该数被认为是讨厌数。前 10 个讨厌数是 1、2、4、7、10、11、13、14、16、19、21。有趣的是，所有 2 的幂都是讨厌数，因为它们只有一个置位位。
以下文章详细讨论了两种方法来判断一个数是否为讨厌数。
问题陈述
此问题旨在检查给定的数字是否为讨厌数，即它是一个正数，其二进制展开式中设置位的数量为奇数。
讨厌数的示例
Input: 34
Output: Non-Odious Number
解释
34 的二进制表示为 10010。
设置位的数量 = 2。
由于 1 的数量为偶数，因此 34 不是讨厌数。
Input: 1024
Output: Odious Number
解释
1024 的二进制表示为 10000000000。
设置位的数量 = 1。
由于 1024 是 2 的幂，因此只有一个置位位。因此，它是一个讨厌数。
Input: 53
Output: Non-Odious Number
解释
(53)10 = (110101)2
设置位的数量 = 4。
因此，它不是讨厌数。
解决方案方法
为了确定一个数是否为讨厌数，我们必须知道设置位的数量是奇数还是偶数。这里的主要任务是计算数字二进制展开式中设置位的数量。可以使用以下技术来计算位数，然后检查结果是奇数还是偶数。
朴素方法
使用循环和右移运算符，逐个遍历数字的所有位。
如果位值为 1，则将计数增加 1。
检查计数的最终值是奇数还是偶数。
显示答案。
伪代码
函数 no_of_set_bits()
初始化 count = 0
当 (n > 0)
if ((n & 1) > 0) Increment count Right Shift n
返回 count
函数 is_odious()
如果 (count 为奇数)
返回 true
否则
返回 false
函数 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()
初始化 count = 0
当 (n > 0)
n = n & (n-1)
增加计数
返回 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;
}
输出
27 is Non-Odious Number
时间和空间分析
时间复杂度 - O(log(x))，其中 x 是数字中设置位的数量。如果只有一个设置位，则循环将运行一次。
空间复杂度 - O(1)，因为没有使用额外的空间。
比较以上方法
虽然第一种方法很容易理解，但它需要 log(n) 次迭代才能产生最终结果。另一方面，第二种方法需要 log(x) 次迭代，其中 x 是数字二进制展开式中设置位的数量。因此，它提高了性能。
结论
本文讨论了两种检查数字是否为讨厌数的方法。它还为我们提供了方法的概念、示例、使用的算法、C++ 程序解决方案以及每种方法的复杂度分析。它还比较了这两种方法，以找出哪种方法更有效。
287 次浏览
