自己实现64位整数输出





高精度整数是常见的问题之一。但实际上有的时候只是需要比现有整数精度高一点。比如需要128位整数,256位整数等。这个时候就有可能比起去写任意精度整数而言,针对特殊需求写比较好。因为位数比较少,所以好的方式是模仿现有的整数存储方式去实现,用二进制存储。这里面比较麻烦的一步就是输出,因为输出需要写成十进制数,但运算和存储都是二进制形式。于是我自己实现了一个64位整数的输出作为练习。实现64位的原因是为了便于和原有的64位整数输出效率进行对比。
这里面的基本思想就是用两个unsigned int来拼成一个64位整数,它们分别存储前32位和后32位,记为a和b,存储策略同已有的整数类型。输出的时候每次对a*2^32+b除以10000,余数为最末4位,然后循环得到所有十进制位。用10000应该是最好的选择,使用100000会在计算过程中溢出。计算a*2^32+b除以10000的时候将a和2^32分别考虑即可。如果是负数,则事先将其取反+1,化成相反数即可。此外还需要注意一些边界情况即可。
对于一般的整数,自测大约比系统的输出要慢一倍,特殊的整数会比系统的略快(例如-1)。

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
#include <stdio.h>
 
const unsigned int t = 10000;
const unsigned int u1 = 429496;
const unsigned int u2 = 7296;
 
void output(unsigned int a, unsigned int b) {
	unsigned int r[128];
	int p = 0;
	bool negative = false;
 
	if (a >= 0x80000000) {
		negative = true;
		if (a == 0x80000000 && b == 0) {
			printf("-9223372036854775808\n");
			return;
		}
		if (b != 0) {
			b = (~b) + 1;
			a = ~a;
		}
		else {
			a = (~a) + 1;
		}
	}
 
	while (a > 0 || b > 0) {
		unsigned int a2 = a % t;
		unsigned int b2 = b % t;
		unsigned int c = a2 * u2 + b2;
		unsigned int d = c / t;
 
		r[p++] = c - d * t;
 
		a /= t;
		b /= t;
 
		b += a2 * u1 + d;
	}
 
	if (negative) {
		printf("-");
	}
 
	if (p == 0) {
		printf("0");
	}
	else {
		printf("%d", r[--p]);
		while (p > 0) {
			printf("%04d", r[--p]);
		}
	}
	printf("\n");
}
 
int main() {
	long long c_array[] = {0x8000000000000000ll, 0xffffffffffffffffll,
		0x7fffffffffffffffll, 0x0000000000000000ll, 0x7fffffff7fffffffll,
		0x0000000000000001ll, 0x1234567890abcdefll};
	for (int i = 0; i < sizeof(c_array) / sizeof(c_array[0]); i++) {
		long long c = c_array[i];
		printf("%lld\n", c);
		output(c >> 32, c & 0xffffffff);
	}
	return 0;
}
本文来自Dora Blog,题目为自己实现64位整数输出,转载请注明出处。
如果你喜欢我的博客,请订阅本博客的RSS以更方便的阅读
欢迎关注我的新浪微博:http://weibo.com/diaorui1987