算法基础课题解合集

循环求解

因为一个 $int$ 类型的变量的长度是 $32$，所以我们可以循环 $32$ 次求它的每一位是几。

而求 $x$ 二进制下的第 $i$ 为则是 x >> i & 1 。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

int main() {
    for (cin >> n; cin >> n;) {
        int res = 0;
        for (int i = 0; i <= 31; i ++)
            if (n >> i & 1) res ++;
        cout << res << " ";
    }
    return 0;
}

$lowbit$ 求解

关于 $lowbit$

$lowbit(x)$ 表示 $x$ 的最后一位 $1$，比如 $10$ 的二进制表示是 $1010$，那$lowbit(x)$就应该是 $(10)_2$ 也就是 $2$。

$lowbit$ 的求法

其实很简单，只要返回x&(-x)就行了。可又为什么呢？

是因为$C++$中的负数使用补码表示的，而补码等于反码（就是把$x$的二进制中的每一位都取反）$+1$，所以x&(-x)=x&(~x+1)。

要证明x&(~x+1)的正确性，可以先看下图：

很明显，红色数字左边的原码与补码都是相反的，而红色数字右边的原码与补码都是$0$，所以最后只有红色数字一个$1$，故x&(-x)是成立的。

本题思路

如果 $x$ 不为 $0$ 的话，就减去 $lowbit(x)$，最后输出进行了几次 $lowbit$ 即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n;

int main() {
    for (cin >> n; cin >> n;) {
        int res = 0;
        while (n) n -= n & -n, res ++;
        cout << res << " ";
    }
    return 0;
}

好啦，这篇题解到这里就结束啦！感谢观看！！！

$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\quad$$\mathcal{writer\enspace by \enspace acwing}$ : $\mathfrak{天元之弈}$