如果一个数字在其二进制展开中有奇数个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。
因此,它不是一个可憎的数字。
解决方案
为了判断一个数是否是可恶的,我们必须知道设置的位数是奇数还是偶数。这里的主要任务是统计数字的二进制展开中设置的位数。可以采用以下技术来计算位数,然后检查结果是奇数还是偶数。
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
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 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