位运算与进制转换
0. 引言
写这篇博客时，是2026.2.14虽然是2026年的情人节，但是这丝毫不影响我敲代码。正如我博客标题中写的，未曾起舞的日子，是刻骨铭心的练习。其实还有一句话我想送给大家，你若花开，蝶自来。没找到对象，我们就去多去提升自己，开始学护肤，开始锻炼，开始学习技能，开始思考代码。我相信众里寻他千百度，蓦然回首，那人却在灯火阑珊处。比起找对象，先让自己变得让自己喜欢，这样别人才会来喜欢你。
1. 位运算
1.1 基本概念
1.1.1 位运算符
首先我们学习位运算的基本概念
| 位运算符 | 含义 | 语法 | 效果 |
|---|---|---|---|
| << | 左移 | a << x |
a左移x位 |
| >> | 右移 | a >> x |
a右移x位 |
| & | 位与 | a & b |
11得1，其他均为0 |
| | | 位或 | a | b |
00得0，其他均为1 |
| ^ | 位异或 | a ^ b |
相同为0，不同为1 |
| ~ | 位取反 | ~a |
0变1，1变0 |
1.1.2 位运算与二进制
求 \(n\) 转为二进制的第 \(k\) 位
n >> k & 1
将 \(n\) 输出为二进制
for(int k = 32; k >= 0; k--) cout << (n >> k & 1);
1.2 lowbit()的使用
返回 \(x\) 的最后一位 \(1\)
lowbit(int x){return x & -x;
}
1.2.1 lowbit()详解：
\(-x= \sim x +1\)
例如
\(x=10100101010000\)
\(\sim x= 01011010101111\)
\(\sim x + 1= 0101101 0110000\)
\(x \&-x=00000000010000\)
1.2.2 例题
求一个数转换为二进制后 \(1\) 的个数
#include<bits/stdc++.h>
using namespace std;int lowbit(int x){return x & -x;
}int main(){int n;cin >> n;int ans = 0;while(n){n -= lowbit(n);ans++;}cout << ans << endl;return 0;
}
2. 进制转化(进制 \(\le 10\) )
一般来说进制转化遵循一下的思路
2.1 \(P\) 进制转 \(10\) 进制
对于任意一个 \(a_{n}a_{n-1} \dots a_3a_{2}a_1\) 的 \(P\) 进制的数我们可以通过如下公式转化为 \(10\) 进制的数 \(y\)
\[y=a_0*P^0+a_1*P^1+a_2*P^2+a_3*P^3+\dots +a_{n-1}*P^{n-1} + a_n*P^n
\]
代码实现
#include<bits/stdc++.h>
using namespace std;
int main(){int x;cin >> x >> p;int y = 0, product = 1;while(x){y += (x % 10) * product;x = x / 10;produce *= p; }cout << y <<endl;return 0;
}
2.2 \(10\) 进制转 \(Q\) 进制
在 \(10\) 进制转化为 \(Q\) 进制中，我们常常用到短除法例如 \(15\) 转 \(2\) 进制中
最终 \(15=(1111)_2\)
#include<bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;
int z[N];int main(){int n, q;cin >> n >> q;int num = 0;do{z[num++] = n % q;n = n / 10;}while(n)for(int i = num - 1; i >= 0; i--){cout << z[i];}return 0;
}