题解 | 10进制 VS 2进制

采用大数除法来实现进制转换,容易错的一个误区在于不用执着于利用字符串的最后一位进行求余,当你从m进制转换为n进制且n > m时不能这么做, 只能通过大数除法做除留余数进行进制转换.

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
// 实行M/N的除法,同时利用remainder保留余数 
string divString(string num, int m, int n, int &remainder) {
	string ans;
	int x = 0;
	// 模拟除法过程 
	for (int i = 0; i < num.size(); i++) {
		int cur = 0;
		if ('0' <= num[i] && num[i] <= '9')
			cur = num[i] - '0' + x * m;
		else
			cur = num[i] - 'A' + 10 + x * m;
		// 不够则上商0 
		if (cur / n < 10) ans += cur / n + '0';
		else ans += cur / n - 10 + 'A';
		// 求余,余数进入下一轮运算 
		x = cur % n;
	}
	// 保留余数 
	remainder = x;
	int pos = 0;
	// 清理前缀0 
	while (ans[pos] == '0' && pos < ans.size()) pos++;
	if (pos == ans.size()) return "0";
	else return ans.substr(pos);
}
int main() {
	string num;
	while (cin >> num) {
		string str = num;
		string ans = "";
		int remainder = 0;
		// 不断除n直至除尽 
		while (str != "0") {
			str = divString(str, 10, 2, remainder);
			// 将原字符串转换为n进制,不采取insert是为了让其逆序 
			ans += remainder + '0';
		}
		str = ans;
		ans = "";
		// 再次将逆序的字符串转换回m进制 
		while (str != "0") {
			str = divString(str, 2, 10, remainder);
			ans.insert(0, 1, remainder + '0');
		}
		cout << ans << endl;
	}
	return 0;
}