newcoder 清华 10进制 VS 2进制

发表于 | 分类于

清华复试上机 10进制 VS 2进制 题解

题目描述

​ 对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们乘B为A的二进制逆序数。 例如对于十进制数173，它的二进制形式为10101101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数。

输入描述:

1
一个1000位(即10^999)以内的十进制数。

输出描述:

1
输入的十进制数的二进制逆序数。

​ 这是本人目前刷题到现在最讨厌的题型，大整数的各种操作。因为超过了long long 的表示范围，所以只能用字符串或者int数组来存储数据，然后逐位操作。

​ 这里使用string类型来存储大整数滴~

​ 需要实现的功能函数有：字符串的除法、加法和乘法。思路都非常简单一致，就是按照运算规则，从高位到低位(除法)、从低位到高位(加法、乘法)逐位来进行运算。

​ 字符串的除法(因为是转换成二进制，所以是计算除以2的情况)：

1
2
3
4
5
6
7
8
9
10
11
12
string div(string s) {
    string ret = "";
    int now = 0;
    for(int i = 0; i < s.length(); i++) {//从高位到低位
        now = now * 10 + (s[i] - '0');
        if(ret == "" && now / 2 == 0) continue;//除去先导0
        ret = ret + char('0' + now / 2);
        now %= 2;
    }
    if(ret == "") ret = "0";
    return ret;
}

​ 字符串的加法：

1
2
3
4
5
6
7
8
9
10
string add(string s) {
    int c = 1, tmp;
    for(int i = s.length() - 1; i >= 0; i--) {
        tmp = (s[i] - '0') + c;
        s[i] = char(tmp % 10 + '0');
        c = tmp / 10;//c现在用来保存进位
        if(c == 0) return s;//如果进位停止则说明之后的数字不会发生变化，直接返回
    }
    return "1" + s;//最多进一位1
}

​ 字符串的乘法(*2)：

1
2
3
4
5
6
7
8
9
10
string mul(string s) {
    int c = 0, tmp;
    for(int i = s.length() - 1; i >= 0; i--) {
        tmp = (s[i] - '0') * 2 + c;
        s[i] = char(tmp % 10 + '0');
        c = tmp / 10;
    }
    if(c) s = char(c + '0') + s;
    return s;
}

​ 整体的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
string div(string s) {
    string ret = "";
    int now = 0;
    for(int i = 0; i < s.length(); i++) {
        now = now * 10 + (s[i] - '0');
        if(ret == "" && now / 2 == 0) continue;
        ret = ret + char('0' + now / 2);
        now %= 2;
    }
    if(ret == "") ret = "0";
    return ret;
}
string add(string s) {
    int c = 1, tmp;
    for(int i = s.length() - 1; i >= 0; i--) {
        tmp = (s[i] - '0') + c;
        s[i] = char(tmp % 10 + '0');
        c = tmp / 10;
        if(c == 0) return s;
    }
    return "1" + s;
}
string mul(string s) {
    int c = 0, tmp;
    for(int i = s.length() - 1; i >= 0; i--) {
        tmp = (s[i] - '0') * 2 + c;
        s[i] = char(tmp % 10 + '0');
        c = tmp / 10;
    }
    if(c) s = char(c + '0') + s;
    return s;
}
int main() {
    string num;
    while(cin >> num) {
        int tmp;
        string ans = "0";
        while(num != "0") {
            tmp = num[num.length() - 1] - '0';//最后一位
            ans = mul(ans);
            if(tmp & 1) {
                num[num.length() - 1]--;
                ans = add(ans);
            }
            num = div(num);
        }
        cout << ans << endl;
    }
    return 0;
}