| 目录 [+] |
1 原文引用
《数据结构（C语言版）》（严蔚敏、吴伟民编著），3.2.1 数制转换，把十进制转换为其他进制的原理：N = (N div d) x d + N mod d（其中：div为整除运算，mod为求余运算）
例如：(1348)10 = (2504)8，其运算过程如下：
| N | N div 8 | N mod 8 |
| 1348 | 168 | 4 |
| 168 | 21 | 0 |
| 21 | 2 | 2 |
| 2 | 0 | 2 |
void conversion() {
InitStack(S); // 构造空栈
scanf("%d", N);
while (N) {
Push(S, N % 8);
N = N / 8;
}
while (!StackEmpty(S)) {
Pop(S, e);
printf("%d", e);
}
}
2 对上面引用的说明
说是十进制，实际上是二进制，输入的十进制整数字符串被scanf转换成了二进制。上面的公式很直观，是对的，但是怎么想到用这样一个公式？
以上面的数字为例，根据进制的定义，得到如下算式：
(1348)10 = 1*(10^3)+3*(10^2)+4*(10^1)+8*(10^0) = S(k)*(8^k)+S(k-1)*(8^(k-1))+...+S(1)*(8^1)+S(0)*(8^0)
观察上面的算式，发现只有S(0)*(8^0)是落单的，其他的都是8的倍数，那S(0)*(8^0)就是N%8了，即S(0)=N%8，N-S(0)是8的倍数，从而得出，N=N%8+8*(S(1)+S(2)*(8^1)+...+S(k-1)*(8^(k-2))+S(k)*(8^(k-1)))，这次S(1)成了落单的，S(1)=((N-N%8)/8)%8=(N/8)%8，剩下的可以用一样的方法得出。这就是上面的做法。
也可以先找到手动计算S(k),S(k-1),...,S(1),S(0)的方法。如果8^(k+1)>=N，那k就是最高指数，给8^k加倍，直至超过N，超过之前的那个倍数就是S(k)，可以对N-S(k)*(8^k)及8^(k-1)做类似的计算，剩下的也一样，最后得到2*(8^3)+5*(8^2)+0*(8^1)+4*(8^0)。
这个手动计算过程是有规律的，可以以此写一个程序，先不论好坏。
通过前面的过程容易发现，S(k)=N/(8^k)，余数(k)=N%(8^k)，S(k-1)=余数(k)/(8^(k-1))，余数(k-1)=余数(k)%(8^(k-1))，可以以此修改一下前面写的那个程序。继续往前推导，S1=余数(2)/(8^1)，余数(1)=余数(2)%(8^1)=N%8，S(0)=余数(1)/(8^0)=余数(1)=N%8，反过来计算就是上面的做法了。
3 整数的进制转换例子
3.1 java.lang.Integer.toString
GPL license（代码不允许商业使用）；通用算法跟书上介绍的一样，8/10/16进制有专门的优化实现。Pre[-]
public static String toString(int i, int radix) {
if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) // MIN_RADIX=2, MAX_RADIX=36
radix = 10;
/* Use the faster version */
if (radix == 10) {
return toString(i);
}
char buf[] = new char[33]; // 使用足够大的字符数组保存结果，而不是栈
boolean negative = (i < 0);
int charPos = 32;
if (!negative) {
i = -i; // 如果是正整数，那转化为负整数，下面统一处理
}
while (i <= -radix) {
buf[charPos--] = digits[-(i % radix)]; // digits: [0-9a-z]范围内的字符数组，正好36个字符
i = i / radix;
}
buf[charPos] = digits[-i];
if (negative) {
buf[--charPos] = '-';
}
return new String(buf, charPos, (33 - charPos));
}
3.2 groff itoa
GPL license（代码不允许商业使用）；算法跟书上介绍的一样。Pre[-]
#define INT_DIGITS 19 /* enough for 64 bit integer */
char *itoa(i)
int i;
{
/* Room for INT_DIGITS digits, - and '\0' */
static char buf[INT_DIGITS + 2]; // 使用足够大的静态局部字符数组保存结果，多线程调用这个函数的话，应该会有问题
char *p = buf + INT_DIGITS + 1; /* points to terminating '\0' */
if (i >= 0) {
do {
*--p = '0' + (i % 10);
i /= 10;
} while (i != 0);
return p;
}
else { /* i < 0 */
do {
*--p = '0' - (i % 10);
i /= 10;
} while (i != 0);
*--p = '-';
}
return p;
}
3.3 Linux itoa
GPL license（代码不允许商业使用）；这个算法跟额外介绍的其中一个方法一样。
namespace linux
{
void itoa( int i,char* string)
{
int power, j;
j=i;
for (power=1;j>=10;j/=10)
power*=10;
for (;power>0;power/=10)
{
*string++='0'+i/power; i%=power;
}
*string='\0';
}
}
--引用自itoa的两种实现 - Author: yanglinbo - www.cppblog.com3.4 Solaris itoa
GPL license（代码不允许商业使用）；算法跟书上介绍的一样。Pre[-]
namespace solaris
{
char * itoa(long n, int base) // 从下面的代码来看，base允许的最大取值是16
{
register char *p;
register int minus;
static char buf[36];
p = &buf[36];
*--p = '\0';
if (n < 0) { minus = 1; n = -n; } else minus = 0;
if (n == 0) *--p = '0';
else while (n > 0) { *--p = "0123456789abcdef"[n % base]; n /= base; }
if (minus) *--p = '-';
return p;
}
}
4 数值运算规范
上面那些程序的一个关键是数值的整除及求余运算规范，前面的分析是基于对整除及求余的基本认识。语言规范决定数值运算规范。我不熟悉其他语言，仅以Java为例。
4.1 Java Remainder Spec
In C and C++, the remainder operator accepts only integral operands, but in the Java programming language, it also accepts floating-point operands.The remainder operation for operands that are integers after binary numeric promotion (§5.6.2) produces a result value such that (a/b)*b+(a%b) is equal to a.
--引用自JLS # 15.17.3. Remainder Operator % - docs.oracle.com
在Java里边，整除负数有个特例，这里就不说了。正整数的运算是比较直观的，一般也不会有问题，有负数就得小心了。如果要做任意数字的整除或求余，那得把相关的数值运算规范好好看完，其他运算也一样。
5 任意非二进制之间的转换
非二进制一般是human-readable的需要，这种情况下，都是可打印ASCII字符串，这一步只讨论这种情况。分两步：
（1）先把其中一种进制转换为二进制。这一步就是把字符串转换为数字，字符跟数字的联系是字符编码，比如ASCII。
（2）再把二进制转换为另一种进制。
6 进制的引申含义，以及进制跟Base系列编码的区别
上面的(1348)10跟(2504)8反映的是一种等价映射关系，代表的是同一个整数。对于数字的二进制表示跟数字的2^k（k>1）进制表示之间的等价映射关系，有一种很直观的映射，就是用一个字符来表示k-bit，能无损地相互转换，所以是等价的，但未必是进制转换（开头那句是假设）。实现起来很方便，逻辑右移k、按位与(2^k-1)就行了，其实，逻辑右移k就是对2^k做整除运算，按位与(2^k-1)就是对2^k求余，如果不映射那些残余的无意义0bit（比如0x0000007C中前面的那些0），那还是符合上面的那个公式，属于进制转换，否则，那就算别的编解码方式，比如Base64、Base32（结尾可能有=）。
7 数字压缩
7.1 介绍
）用更高进制表示的数字长度更短，可以节约存储空间。当然，二进制排除在外，因为最终的数据都是以二进制的形式存储，是否节约存储空间在于编码方法。如果把二进制输出为字符串，比如，0xFFFF对应的是11111111，每个'1'都至少需要一个字节存储，那就有可比性了。）2/3/4/5/6/7/8-bit就是Base4/8/16/32/64/128/256，如果不映射那些残余的无意义0bit，那就是进制转换。
）如果输出的字符需要human-readable，那64进制最节约空间。如果要用10或16进制存储数字，那可以考虑转换为64进制存储。
）如果输出的字符不需要human-readable，那256进制最节约空间。比如，int32类型的24需要4个字节，转换为256进制只需要1个字节。
）当然，上面说的是单个数字，如果需要连续保存很多数字，那需要有方法分离出连续的数字。
举两个业界的例子，都不是human-readable编码。
7.2 UTF-8编码
UTF-8使用1到4个八位字节来表示Unicode code point。Unicode code point的范围是0到U+10FFFF。在编程语言里边，int32/uint32就可以表示了，UTF-32就直接使用4个八位字节表示Unicode code point。UTF-8编码格式（来自UTF-8 definition - tools.ietf.org）：
Char. number range | UTF-8 octet sequence (hexadecimal) | (binary) --------------------+--------------------------------------------- 0000 0000-0000 007F | 0xxxxxxx 0000 0080-0000 07FF | 110xxxxx 10xxxxxx 0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx 0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx The letter x indicates bits available for encoding bits of the character number.数字1/0是固定的前缀，解决了连续保存的数字之间的边界问题，边界对受损的数据有限制损失的功效。
7.3 Protocol Buffers
Protocol Buffers的数字编码很紧凑，编码文档在https://developers.google.com/protocol-buffers/docs/encoding）Base 128 Varints
- Varints是一种使用一到多字节的整数序列化方法，越小的数字使用越少的字节。
- 对于varint的每个字节，最后一个字节除外，都是用最高位用来表示后面还有没有字节属于这个varint，1代表有，0代表没有，所有字节的低7位代表原始数字的二进制补码表示，低字节中的数据放在varint的高位。
- 以300为例，二进制字符串为100101100（前面的0都已省略），按照7位一组分开（低位优先）并交换顺序，得到0101100 10，补上指示后续字节的最高位并扩充不足的位，得到10101100 00000010，这就是300的varint编码。
- 这里扩充的最高位解决了连续保存的varints之间的边界问题。
）ZigZag encoding
用二进制补码表示的负数，最高位是1，相应的varint会有很多字节；所以有必要把负整数映射为比较小的正整数，以提高压缩效率。对于sint32 n，这里提供的映射方式是这样的：(n << 1) ^ (n >> 31)。
(n << 1)^(n >> 31)不够直观，无法直接看出设计意图。
这个算式的等价表示：
- 如果n>=0，那(n << 1)=2n，(n >> 31)=0，(n << 1)^(n >> 31)的结果是2n；
- 如果n<0，那(n << 1)=2n，(n >> 31)=0xFFFFFFFF，(n << 1)^(n >> 31)的结果是-2n-1。证明如下：在二进制补码系统中，对于int32 n, -n=~n+1, ~n=n^0xFFFFFFFF, -> n^0xFFFFFFFF=-n-1, -> (2n)^0xFFFFFFFF=-2n-1。
sint64同理。
8 附录：二进制跟64进制互相转换的Java实现
Radix64Converter.java - sandynz.blogspot.com=文章版本=
20130320130501 修改一点格式，顺便增减一些内容
20130506 改为html格式
No comments:
Post a Comment