C++ 中在 [0, n] 范围内仅具有 1 个设置位的数字的数量
给定一个数字，任务是计算从 0 到给定数字(假设 num 恰好具有一个设置位)的数字的数量
二进制数中的设置位用 1 表示。每当我们计算整数值的二进制数时，它都会形成 0 和 1 的组合。因此，在计算机术语中，数字 1 称为设置位。
输入 − int num = 15
输出 − 在 [0, 15] 范围内仅具有 1 个设置位的数字的数量为 − 4
解释 −给定的数字是 15，因此范围是 0-15。现在计算 4 位数字
− 的二进制数
0 -> 0000 = 0 设置位，1 -> 0001 = 1 设置位，2 -> 0010 = 1 设置位，3 -> 0011 = 2 设置位，4 -> 0100 = 1 设置位，5 -> 0101 = 2 设置位，6 -> 0110 = 2 设置位，7 -> 0111 = 3 设置位，8 -> 1000 = 1 设置位，1 -> 1001 = 2 设置位，10 -> 1010 = 2 设置位，11 -> 1011 = 3 个设置位，12 -> 1100 = 2 个设置位，13 -> 1101 = 3 个设置位，14 -> 1110 = 3 个设置位，15 -> 1111 = 4 个设置位。现在，我们将选择恰好有一个设置位的数字，即 1、2、4 和 8。
输入 − int num = 4
输出 − 在 [0, 15] 范围内只有 1 个设置位的数字数量为 − 3
解释 − 给定的数字是 4，因此范围是 0-4。现在计算 4 位二进制数
− 的数字
0 -> 0000 = 0 个设置位，1 -> 0001 = 1 个设置位，2 -> 0010 = 1 个设置位，3 -> 0011 = 2 个设置位，4 -> 0100 = 1 个设置位。现在，我们将选择恰好有一个设置位的数字，即 1、2 和 4。
以下程序中使用的方法如下
有多种方法可以解决给定的问题，即简单方法和有效方法。因此，我们首先看一下简单的方法。
输入数字并将其传递给函数进行进一步处理。
使用临时变量 count 来存储范围内的数字数量，并将位设置为 1
从 i 到 1 开始循环直到数字
在循环内部，使用‘设置一个临时变量__builtin_popcount(i)’，返回设置位数的函数。
检查 temp = 1 是否递增计数
返回 count
打印结果
高效方法
输入数字并将其传递给函数进行进一步处理。
使用临时变量 count 存储设置位为 1 的范围内数字的数量
开始循环 While 从 temp 直到 temp <= number
在循环内部，将计数递增 1 并将 temp 设置为 temp * 2
返回 count
打印结果
示例(简单方法)
#include <iostream>
using namespace std;
//函数用于计算在 [0, n] 范围内只有 1 个设置位的数字
int set_bits(int number){
int count = 0;
for (int i = 1; i <= number; i++){
int temp = __builtin_popcount(i);
if (temp == 1){
count++;
}
}
return count;
}
int main(){
int number = 15;
cout<<"Count of numbers having only 1 set bit in the range [0, "<<number<<"] are: "<<set_bits(number);
return 0;
}
输出
如果我们运行上述代码，它将生成以下输出 −
Count of numbers having only 1 set bit in the range [0, 15] are: 4
Example (Efficient approach)
#include <iostream>
using namespace std;
//函数用于计数在 [0, n] 范围内只有 1 个设置位的数字
int set_bits(int number){
int count = 0;
int temp = 1;
while(temp <= number){
count++;
temp = temp *2;
}
return count;
}
int main(){
int number = 15;
cout<<"Count of numbers having only 1 set bit in the range [0, "<<number<<"] are: "<<set_bits(number);
return 0;
}
输出
如果我们运行上述代码，它将生成以下输出 −
Count of numbers having only 1 set bit in the range [0, 15] are: 4
