进制转换

进制,也就是满X进一。其本质上是对于计数的简写。比如原来要表示一个数,只能用若干个小棒来表示。进制的出现,就相当于出现了代表一定数值的小棒的出现。这也就是位权:满X进一中的X。

(摘自百度百科)进制转换是人们利用符号来计数的方法。进制转换由一组数码符号和两个基本因素“基数”与“位权”构成。基数是指,进位计数制中所采用的数码(数制中用来表示“量”的符号)的个数。位权是指,进位制中每一固定位置对应的单位值。

理解了进制的本质后,我们就可以着手用数学工具去实现进制转换了。

短除法

首先以十进制为例。规定//为带余数除法,我们规定一个正整数123,那么:

1
2
3
123 // 10 = 12......3
12 // 10 = 1 ......2
1 // 10 = 0 ......1

观察。可以得到,三次除法的余数分别是3,2,1.对应个位,十位,百位。为什么呢?因为

1
123(10)=1*10^2+2*10^1+3*10^0

所以,每次得到的余数,就是对应位的数。显然,此结论对于N进制都成立。

下面,我们用编程实现这个算法。

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
/* Dec2Bin - by xeonds */
#include <stdio.h>

int base_dec_2_bin_convert(int num);

int main(void)
{
int i;

scanf("%d", &i);
if (i <= 512 && i >= -512)
printf("dec:%d bin:%d\n", i, base_dec_2_bin_convert(i));
else
puts("Out of range.");

return 0;
}

int base_dec_2_bin_convert(int num)
{
int result = 0, i = 1;

while (num > 0)
{
result += num % 2 * i;
num = (num - num % 2) / 2;
i *= 10;
}

return result;
}

算法核心部分是最后几行。num % 2 * i是计算最后一位并乘10,便于用int表示。num = (num - num % 2) / 2是将num减去余数并除以位权。

用[[Python|Python]]的话还可以写得更短些:

1
2
3
4
5
6
7
8
#!/usr/bin/python

def base_10_to_2(number):
result = ''
while number:
number, rest = divmod(number, 2)
result = str(rest) + result
return result

更进一步,我们可以实现任意进制转换:

1
2
3
4
5
6
7
def base_n_convert(number, letters):
length = len(letters)
result = ''
while number:
number, rest = divmod(number-1, length)
result = letters[rest] + result
return result

其实这是我写的一个密码字典生成器。效率暂且不论,其原理也是进制转换。这里的number是待转换的十进制数,letters是待转换的N进制数的所有字符,比如十进制是09,十六进制是0F。

上面实现的,都是10进制转其他进制。其他进制转十进制很简单,只需要将各个位乘以其位权,求和即可得到其十进制表示。其原因很简单,我们的数学体系是建立在十进制的,所以对于十进制环境下的各种运算都很熟悉。这个方法对于任意进制转p进制其实都适用,不过这需要编写相应进制的四则运算算法,相对麻烦一些。

任意进制和任意进制的互转,可直接也可间接。间接,即将p进制数先转换为10进制等中间进制,再将其转换为q进制。直接,即利用对应规则进行转换。如二进制和十六进制互转,便可利用有限个对应规则实现快速互转。

小结

和栈机制一样,进制转换是很多技术的基础。某些时候利用它,或许会获得意想不到的奇效。

同时,作为算法的源泉,数学真的很重要

作者

xeonds

发布于

2021-09-24

更新于

2024-10-08

许可协议

评论