题目描述

给定一个整数 、将 的 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))