每日算法系列【EOJ 3031】二进制倒置
题目描述
给定一个整数 、将
的 334 位二进制表示形式（不包括开头可能的值为 0 的位，
表示为 1 位 0）前后倒置，输出倒置后的二进制数对应的整数。
例如： ，其二进制表示为（330 个 0）1010 ，倒置后为 0101 ，对应输出就是 5 。
题目链接
https:// acm.ecnu.edu.cn/problem /3031/
题解
这题考查的主要是大数的进制转换，其他没有什么算法技巧，但是对代码实现要求还是挺高的，适合用来锻炼你的耐心和代码风格。
整体思路非常简单，不就是先把输入的 10 进制数 转化成 2 进制数
，再把
所有位颠倒过来，最后再把
转化成 10 进制输出就行了。
所以整体代码拆分成了三步，先从 10 进制转 2 进制，再颠倒 2 进制，最后从 2 进制转 10 进制。
为了代码的普适性，我这里直接实现了从任意 进制 转化为任意
进制的算法，这样更加方便调用。
这就涉及到了大数的任意进制转换问题，假设 是
进制数，我们要把它转化为
进制的
（初始时为空）。那么转化步骤如下：
- 求
，并把余数接在
的最高位。
- 令
。
- 重复步骤 1 ，直到
。
部分代码如下：
while (n > 0) {
y.push_back(mod(x, a, b));
div(x, a, b);
n = x.size();
if (n == 1 && !x[0]) break;
}
看起来非常简单，但是步骤 1 和 2 都涉及到了大数的求余和大数的除法算法，所以我们还得实现这两个算法。
大数求余只要从 最高位开始计算
的大小，并同时对
求余，然后由于求余的加法和乘法定理，我们可以始终保持
，这样就能用一个
int 类型保存余数了。
部分代码如下：
int mod(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
q = (q * a + x[i]) % b;
}
return q;
}
大数除法类似，从 最高位开始除
，并注意要把余数带到下一位，最后还得去掉前导 0 。
部分代码如下：
void div(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
x[i] += q * a;
q = x[i] % b;
x[i] /= b;
}
for (int i = n-1; i > 0; --i) {
if (x[i]) break;
x.pop_back();
}
}
代码
c++
#include <bits/stdc++.h> using namespace std;
// string转化为vector<int>，倒序存储 vector<int> s2i(string& s) {
vector<int> x;
int idx = 0, n = s.size();
for (; idx < n; ++idx) {
if (s[idx] != '0') break;
}
if (idx == n) idx = n - 1;
for (int i = n-1; i >= idx; --i) {
x.push_back(s[i]-'0');
}
return x;
}
// a进制下x%b，x倒序存储 int mod(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
q = (q * a + x[i]) % b;
}
return q;
}
// a进制下x/b，x倒序存储 void div(vector<int>& x, int a, int b) {
int n = x.size(), q = 0;
for (int i = n-1; i >= 0; --i) {
x[i] += q * a;
q = x[i] % b;
x[i] /= b;
}
for (int i = n-1; i > 0; --i) {
if (x[i]) break;
x.pop_back();
}
}
// a进制下s转化为b进制string string convert(string s, int a, int b) {
vector<int> x = s2i(s);
int n = x.size();
vector<int> y;
while (n > 0) {
y.push_back(mod(x, a, b));
div(x, a, b);
n = x.size();
if (n == 1 && !x[0]) break;
}
int m = y.size();
string res = "";
for (int i = m-1; i >= 0; --i) {
res += '0' + y[i];
}
return res;
}
int main() {
int T;
cin >> T;
string x;
for (int t = 0; t < T; ++t) {
cin >> x;
string x2 = convert(x, 10, 2);
reverse(x2.begin(), x2.end());
string res = convert(x2, 2, 10);
cout << "case #" << t << ":" << endl;
cout << res << endl;
}
return 0;
}
python
x = int(input())
for i in range(x):
print("case #%d:" %i)
print(int(str(bin(int(input())))[2::][::-1], 2))
算法码上来 文章被收录于专栏
公众号「算法码上来」。godweiyang带你学习算法，不管是编程算法，还是深度学习、自然语言处理算法都一网打尽，更有各种计算机新鲜知识和你分享。别急，算法码上来。
投递得物app等公司10个岗位 >