进制转换和位运算

# 进制转换

在数学中，不止只有我们常见的10进制，最近刷了几道关于进制转换的题目，在这里做个总结和记录吧。

# 基本概念

首先我们要先了解进制的基本概念，这里我直接从LeetCode官方这里引用了。

任何一种进位计数制都有一个基数，基数为 X 的进位计数制称为 X 进制，表示每一个数位上的数运算时都是逢 X 进一。

对于一个 X 进制的数，其具体数值由其中的每个数码和数码所在的数位决定。整数部分从右往左的第 m 个数位表示的权重是 $X^m$，其中 m 最小为 0；小数部分从左往右的第 n 个数位表示的权重是$X^{-n}$，其中 n 最小为 1。

八进制的 $720.5$ 可以写成如下形式：

$720.5_{(8)} = 7 \times 8^2 + 2 \times 8^1 + 0 \times 8^0 + 5 \times 8^{-1}$

用我自己的话来说，就是数值*权重

# 进制转换的一般思路

一般来说，我们习惯将进制转换成十进制，这样便于理解和手算。当然，我们也可以不通过十进制作为中间态过度，比如我们熟悉的二进制和十六进制的转换。

# 非十进制转十进制

将非十进制数转成十进制数，只要将每个数位的加权和即可。

例如，将八进制数 $720.5_{(8)}$ 转成十进制：

$720.5_{(8)} = 7 \times 8^2 + 2 \times 8^1 + 0 \times 8^0 + 5 \times 8^{-1} = 464.625$

下面是程序的实现(只考虑整数)，我们可以从高位到低位进行读取，按照下面的方式读入,其中n表示是几进制数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int read() {
    char c = getchar();
    int k = 0;
    while (isint(c) == -1) c = getchar();
    while (isint(c) != -1) {
        k *= n;
        k += isint(c);
        c = getchar();
    }
    return k;
}

# 十进制转非十进制

首先我们先来看手算，将十进制数转成 X 进制数，需要对整数部分和小数部分分别转换。

对于整数部分，转换方式是将十进制数的整数部分每次除以 X 直到变成 0，并记录每次的余数，反向遍历每次的余数即可得到 X 进制表示。

对于小数部分，转换方式是将十进制数的小数部分每次乘以 X 直到变成 0，并记录每次的整数部分，正序遍历每次的整数部分即可得到 X 进制表示。

下面是整数转换的过程，这里要注意的是转换时是从低位到高位，如果要输出的话要进行倒序，体现在程序中就是先递归再输出。

1
2
3
4
5
6


void print(int a) {
    if (!a)
        return;
    print(a / m);
    putchar(itc(a % m));
}

# 负进制

[NOIP2000 提高组] 进制转换

在洛谷的这道题中，我们遇到了一个新的概念：负进制

在负进制数中是用 $-R$ 作为基数，例如 $−15$（十进制）相当于 $110001$ （$-2$进制），并且它可以被表示为 $2$ 的幂级数的和数：

$110001=1\times (-2)^5+1\times (-2)^4+0\times (-2)^3+0\times (-2)^2+0\times (-2)^1 +1\times (-2)^0$

如果按照上面所写的转换过程，就会出现一个问题，比如在C++里对$-15$进行取模和相除的结果是：

$-15%-2=-1$ ； $-15\div-2=7$ ； $7\times-2+(-1)=-15$

虽然式子是成立的，但我们得到的余数是负数，这肯定是不行的，所以我们要想办法进行转换。

所以我们可以将余数减去一个除数，同时将商+1。由于除数（绝对值）肯定是大于余数的，此时余数就会转换成正数。

下面是具体实现的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void slove(int n, int r) {
    if (n == 0)
        return;
    int m = n % r;  // m为余数
    if (m < 0)      // 如果余数小于0，转化为正数
        m -= r, n += r;  //商+1 => 被除数+除数
    if (m >= 10)
        m = 'A' + m - 10;
    else
        m += '0';
    slove(n / r, r);
    putchar(m);
}

# 位运算

位运算的基本概念在组成原理这些课上已经讲过不知道多少遍了，这里就只提一下我觉得重要的点。

位运算共有6种，分别是：与(&)、或(|)、异或(^)、取反(~)、左移(<<)和右移(>>)。

这里要特别注意一下右移运算，它分为逻辑右移和算术右移：

算术右移时，高位补最高位
逻辑右移时，高位补0

在C++中，数据类型包含有符号类型和无符号类型，其中有符号类型使用关键字 signed 声明，无符号类型使用关键字 unsigned 声明，两个关键字都不使用时，默认是有符号类型。对于有符号类型，右移运算为算术右移；对于无符号类型，右移运算为逻辑右移。

在学习和刷题时，我们容易发现，左移运算对应乘法运算。将一个数左移 $k$ 位，等价于将这个数乘以 $2^k$。例如，$29$ 左移 $2$ 位的结果是 $116$，等价于 $29 \times 4$。

算术右移运算对应除法运算。将一个数右移 $k$ 位，相当于将这个数除以 $2^k$。例如，$50$ 右移 $2$ 位的结果是 $12$，等价于 $50 / 4$，结果向下取整。

这里要注意，对于负数，整数除法是向 $0$ 取整，右移运算是向下取整，两者就不相同了。例如，$(-50)»2$的结果是 $−13$，而 $(-50) / 4$ 的结果是$-12$，两者是不相等的。

# 参考资料

位运算和数学 - LeetBook