#include <iostream>
using namespace std;
int countBits(int x) {
int c = 0;
while (x) { x &= (x - 1); c++; }
return c;
}
int main() {
int n = 15, ans = 0;
for (int i = 1; i <= n; i++) ans += countBits(i);
cout << ans << endl;
return 0;
}
- (1) 函数 countBits(x) 的功能是______。（5 分）
- (2) 当 n = 15 时，程序输出结果是______。（5 分）
- (3) 该函数的时间复杂度与 x 的什么有关？请简要说明。（4 分）
答案解析
（1）统计整数二进制表示中 1 的个数。（2）1~15 各数二进制 1 的个数之和 = 1+1+2+1+2+2+3+1+2+2+3+2+3+3+4 = 32。（3）与 x 中"1 的个数"成正比（每次消一个 1），最坏 O(log x)。