今日学习 计组 数电 有感。
忽然发觉，补码是一个非常神奇的东西……
补码的本质是模运算，在一个 $n$ 位系统中，数的表示范围是 $(-2^{n-1},2^{n-1}-1)$，所有的运算都在模 $2^n$ 下进行。
- 正数：直接表示
- 负数：$-x$ 表示为 $2^n-x$ （即补码）
可以发现，用补码来表达负数可谓优雅，在加法运算中能够自动处理正负，乘法运算同样能在二进制下高效地完成。
所以……为什么不试试用存储补码的方式来实现高精度呢！
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| constexpr int B = 15000;
struct Bigint{
bitset<B> a;
bitset<B> add(bitset<B> x, bitset<B> y){
bitset<B> res;
bool carry = 0;
for(int i = 0; i < B; i++){
res[i] = x[i] ^ y[i] ^ carry;
carry = x[i] + y[i] + carry >> 1;
}
return res;
}
bitset<B> neg(bitset<B> x){
auto y = x;
bool convert = 0;
for(int i = 0; i < B; i++){
if(convert) y[i].flip();
if(y[i]) convert = 1;
}
return y;
}
bitset<B> mul(bitset<B> x, bitset<B> y){
bool is_neg = x[B - 1] ^ y[B - 1];
x = x[B - 1] ? neg(x) : x;
y = y[B - 1] ? neg(y) : y;
bitset<B> res;
for(int j = 0; j < B; j++){
if(y[j]){
res = add(res, x << j);
}
}
if(is_neg) res = neg(res);
return res;
}
Bigint(bitset<B> a) : a(a) {}
Bigint(int x){
if(x >= 0){
a = x;
}
else{
a = -x;
a = neg(a);
}
}
Bigint(string s){
bool is_neg = 0;
if(s[0] == '-'){
is_neg = 1;
s = s.substr(1);
}
for(auto &c : s){
a = add(a << 3, a << 1);
a = add(a, c - '0');
}
if(is_neg) a = neg(a);
}
Bigint operator+ (const Bigint &o){
return add(a, o.a);
}
Bigint operator- (const Bigint &o){
return add(a, neg(o.a));
}
Bigint operator* (const Bigint &o){
return mul(a, o.a);
}
void print(){
string s;
auto b = a;
if(b[B - 1]){
cout << "-";
b = neg(b);
}
for(int i = B - 2; i >= 0; i--){
int carry = b[i];
for(auto &c : s){
int sum = (c - '0') * 2 + carry;
c = (sum % 10) + '0';
carry = sum / 10;
}
if(carry) s += "1";
}
for(int i = s.size() - 1; i >= 0; i--){
cout << s[i];
}
if(s.empty()) cout << "0";
}
};
|
这时候就有人要问了，计组又学了一遍补码，数电在干嘛呢，哦，数电在里面实现了全加器）