將一個十進制字符串轉化為十六進制字符串。
這個問題如果只是十進制轉化為十六進制，其實是比較容易的，只要了解短除法就可以解決了，但題目裡數是字符串，這就將題目的難度增高了。因為如果只是int型，那最多也就支持個10位數；但字符串卻可以上千位，所以我們使用短除法的時候會比較麻煩。
這裡我先將字符串轉成了int型，先把簡單的10位數的實現出來，來理順一下思路。下面是10進制數轉16進制的代碼：
int main(){
string s;
while (cin >> s){
int n = 0;
// 將字符串轉換為int類型
for (int i = s.length() - 1, j = 1; i >= 0; i--) {
n += (s[i] - '0') * j;
j *= 10;
}
// 運用短除法不斷除以16取余數，並將其加入字符串結果中
string result = ;
char _16[] = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
};
// 16進制，除以16
const int radix = 16;
while (n) {
int i = n % radix; // 余數
result = _16[i] + result; // 將余數對應的十六進制數字加入結果
n /= radix; // 除以16獲得商，最為下一輪的被除數
}
cout << result << endl;
}
}
從上述代碼我們可以得到一般思路：
輸入十進制字符串 s 開始循環至s為空 獲取s除16的余數 將余數放入結果集的第一位 s等於s除16的整數部分 下一輪循環 循環結束後返回結果好了，難點就出來了，第3步和第5步，歸結起來其實就很簡單了：如何實現一個字符串除以一個數。，也就是大數除法。
在實現大數除法的過程中，其實也會有大數的加、減、乘，所以這些都需要實現。
這些，我就沒有自己實現了（如果用的是Java就會很方便），在網上找的代碼，鏈接：
【新浪博客 - 封清揚iam】大整數加減乘除
所有代碼如下：
#include
#include
using namespace std;
/*
將10進制字符串轉化為16進制字符串
1. 轉化為int類型然後運用短除法得出結果
這種方法只能支撐10位數。。。
2. 使用大數運算
*/
inline int compare(string str1, string str2);
string DIVIDE_INT(string str1, string str2, int flag);
string DIV_INT(string str1, string str2);
string MOD_INT(string str1, string str2);
string MUL_INT(string str1, string str2);
string SUB_INT(string str1, string str2);
string ADD_INT(string str1, string str2);
int main(){
string s;
while (cin >> s){
// 運用短除法不斷除以16取余數，並將其加入字符串結果中
string result = ;
char _16[] = {
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'
};
// 16進制，除以16
const string radix = 16;
while (s != 0) {
string tmp = MOD_INT(s, radix); // 余數
int n = 0;
// 將字符串轉換為int類型
for (int i = tmp.length() - 1, j = 1; i >= 0; i--) {
n += (tmp[i] - '0') * j;
j *= 10;
}
result = _16[n] + result; // 將余數對應的十六進制數字加入結果
s = DIV_INT(s, radix); // 除以16獲得商，最為下一輪的被除數
}
cout << result << endl;
}
}
inline int compare(string str1, string str2) {
if (str1.size() > str2.size()) //長度長的整數大於長度小的整數
return 1;
else if (str1.size() < str2.size())
return -1;
else
return str1.compare(str2); //若長度相等，從頭到尾按位比較，compare函數：相等返回0，大於返回1，小於返回－1
}
string DIVIDE_INT(string str1, string str2, int flag) {//高精度除法
//flag = 1時,返回商; flag = 0時,返回余數
string quotient, residue; //定義商和余數
int sign1 = 1, sign2 = 1;
if (str2 == 0) { //判斷除數是否為0
quotient = ERROR!;
residue = ERROR!;
if (flag == 1) return quotient;
else return residue;
}
if (str1 == 0) { //判斷被除數是否為0
quotient = 0;
residue = 0;
}
if (str1[0] == '-') {
str1 = str1.erase(0, 1);
sign1 *= -1;
sign2 = -1;
}
if (str2[0] == '-') {
str2 = str2.erase(0, 1);
sign1 *= -1;
}
int res = compare(str1, str2);
if (res < 0) {
quotient = 0;
residue = str1;
}
else if (res == 0) {
quotient = 1;
residue = 0;
}
else {
string::size_type l1, l2;
l1 = str1.size(); l2 = str2.size();
string tempstr;
tempstr.append(str1, 0, l2 - 1);
//模擬手工除法
for (int i = l2 - 1; i < l1; i++) {
tempstr = tempstr + str1[i];
for (char ch = '9'; ch >= '0'; ch--) { //試商
string str;
str = str + ch;
if (compare(MUL_INT(str2, str), tempstr) <= 0) {
quotient = quotient + ch;
tempstr = SUB_INT(tempstr, MUL_INT(str2, str));
break;
}
}
}
residue = tempstr;
}
//去除結果中的前導0
quotient.erase(0, quotient.find_first_not_of('0'));
if (quotient.empty()) quotient = 0;
if ((sign1 == -1) && (quotient[0] != '0'))
quotient = - + quotient;
if ((sign2 == -1) && (residue[0] != '0'))
residue = - + residue;
if (flag == 1) return quotient;
else return residue;
}
string DIV_INT(string str1, string str2) {//高精度除法,返回商
return DIVIDE_INT(str1, str2, 1);
}
string MOD_INT(string str1, string str2) {//高精度除法,返回余數
return DIVIDE_INT(str1, str2, 0);
}
string SUB_INT(string str1, string str2) {//高精度減法
string MUL_INT(string str1, string str2);
int sign = 1; //sign 為符號位
string str;
int i;
if (str2[0] == '-')
str = ADD_INT(str1, str2.erase(0, 1));
else {
int res = compare(str1, str2);
if (res == 0) return 0;
if (res < 0) {
sign = -1;
string temp = str1;
str1 = str2;
str2 = temp;
}
string::size_type tempint;
tempint = str1.size() - str2.size();
for (i = str2.size() - 1; i >= 0; i--) {
if (str1[i + tempint] < str2[i]) {
str1[i + tempint - 1] = char(int(str1[i + tempint - 1]) - 1);
str = char(str1[i + tempint] - str2[i] + ':') + str;
}
else
str = char(str1[i + tempint] - str2[i] + '0') + str;
}
for (i = tempint - 1; i >= 0; i--)
str = str1[i] + str;
}
//去除結果中多余的前導0
str.erase(0, str.find_first_not_of('0'));
if (str.empty()) str = 0;
if ((sign == -1) && (str[0] != '0'))
str = - + str;
return str;
}
string MUL_INT(string str1, string str2) {//高精度乘法
int sign = 1; //sign 為符號位
string str;
if (str1[0] == '-') {
sign *= -1;
str1 = str1.erase(0, 1);
}
if (str2[0] == '-') {
sign *= -1;
str2 = str2.erase(0, 1);
}
int i, j;
string::size_type l1, l2;
l1 = str1.size(); l2 = str2.size();
for (i = l2 - 1; i >= 0; i--) { //實現手工乘法
string tempstr;
int int1 = 0, int2 = 0, int3 = int(str2[i]) - '0';
if (int3 != 0) {
for (j = 1; j <= (int)(l2 - 1 - i); j++)
tempstr = 0 + tempstr;
for (j = l1 - 1; j >= 0; j--) {
int1 = (int3 * (int(str1[j]) - '0') + int2) % 10;
int2 = (int3 * (int(str1[j]) - '0') + int2) / 10;
tempstr = char(int1 + '0') + tempstr;
}
if (int2 != 0) tempstr = char(int2 + '0') + tempstr;
}
str = ADD_INT(str, tempstr);
}
//去除結果中的前導0
str.erase(0, str.find_first_not_of('0'));
if (str.empty()) str = 0;
if ((sign == -1) && (str[0] != '0'))
str = - + str;
return str;
}
string ADD_INT(string str1, string str2) {//高精度加法
string SUB_INT(string str1, string str2);
int sign = 1; //sign 為符號位
string str;
if (str1[0] == '-') {
if (str2[0] == '-') {
sign = -1;
str = ADD_INT(str1.erase(0, 1), str2.erase(0, 1));
}
else {
str = SUB_INT(str2, str1.erase(0, 1));
}
}
else {
if (str2[0] == '-')
str = SUB_INT(str1, str2.erase(0, 1));
else {
//把兩個整數對齊，短整數前面加0補齊
string::size_type l1, l2;
int i;
l1 = str1.size(); l2 = str2.size();
if (l1 < l2) {
for (i = 1; i <= l2 - l1; i++)
str1 = 0 + str1;
}
else {
for (i = 1; i <= l1 - l2; i++)
str2 = 0 + str2;
}
int int1 = 0, int2 = 0; //int2 記錄進位
for (i = str1.size() - 1; i >= 0; i--) {
int1 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) % 10;
int2 = (int(str1[i]) - '0' + int(str2[i]) - '0' + int2) / 10;
str = char(int1 + '0') + str;
}
if (int2 != 0) str = char(int2 + '0') + str;
}
}
//運算後處理符號位
if ((sign == -1) && (str[0] != '0'))
str = - + str;
return str;
}
這道題是一道面試題，覺得應該只要能實現int型的那塊，並且講一些大數運算的思路就行了，不然代碼實在是太多了。。。
