给定一个整数 N>0，区间 [0， 2^N) 中有多少个整数正好有 N-1 个设置位？编写一个返回正确答案的简短函数

Question

我写了一些C++代码来解决这个问题：

#include <iostream>
#include <cmath>
using namespace std;
unsigned int countSetBits(unsigned int n) 
{   
int totalCount = 0, i;
int cond = n-1;
for(i=0;i<pow(2,n);i++){
unsigned int count = 0; 
while (i) { 
count += i & 1; 
i >>= 1; 
}  
if(count == cond){
totalCount++;
}
}
return totalCount; 
} 
int main()
{
int n=5;
cout<<countSetBits(5);
return 0;
}

尽管它编译成功，但它不会打印任何内容。 我不知道问题出在哪里...

Answer 1

笔和纸解决方案：

N=2  2^N-1 = 0b11    Possible integers with 1 bit set:
01
10

N=3  2^N-1 = 0b111   Possible integers with 2 bits set:
011
101
110

N=4  2^N-1 = 0b1111  Possible integers with 3 bits set:
0111
1011
1101
1110

所以，N似乎是答案。

Answer 2

问题是你正在修改该循环中for循环的"控制"变量(i)，因此i的值永远不会达到循环限制，它将永远运行。

若要解决此问题，请获取当前i值的副本并对其进行修改：

unsigned int countSetBits(unsigned int n)
{
int totalCount = 0, i;
int cond = n - 1;
int limit = pow(2, n); /// Calculate this ONCE, rather than on each loop!
for (i = 0; i < limit; i++) {
unsigned int count = 0;
int j = i; /// Take a copy of i here (otherwise it will keep getting reset to zero)...
while (j) { /// ...and do your test on the copy!
count += j & 1;
j >>= 1;
}
if (count == cond) {
totalCount++;
}
}
return totalCount;
}

如评论中所述，您还可以进行其他改进。但是我发布的代码更改至少解决了您的问题。

Answer 3

您可以在循环中修改i。内部 while 循环将始终i == 0，无论循环计数器是什么，因此 for 循环的条件永远不会为假。使用临时的。也不要使用pow来计算2的幂。2^N(1 << N).

您需要N+1位来表示2^N。(2^N)-1设置了N较低的位。在(2^N)-1中N可能的位可以取消设置，因此有N个数字N-1位设置为[0,2^N)。QED ;)

unsigned int countSetBits(unsigned int n)  { return n; }