秦九韶算法: 将 b 进制的数转化为 10 进制

$3203_{b}$ => 十进制
$3×b^3 + 2×b^2 + 0×b^1 + 3×b^0$ => 3 ×b+2 ×b+0 ×b+3 => 可以从高位递推得到

短除法: 将 10 进制的数转化为 b 进制 (在进行除法的过程中, 进制是b进制而不是10进制!!!)

$123_{10}$ => b进制

不断除以b, 余数就是结果的个位, 十位, 百位....
例如: $123/2 = 31..1, 61/2 = 30..1, 30/2 = 15..0, 15/2 = 7..1, 7/2 = 3..1, 3/2 = 1..1, 1/2 = 0..1$

$123_{10}$ 转化为 2 进制的结果就是 $1111011_{2}$

短除法是秦九韶的逆过程, 例如 $1201_{3}$ => $1×3^3 + 2×3^2 + 0×3^1 + 1×3^0$, 它除以3的结果就是最低位的1
因为其他位上的数都是$3^n$, 一定会被3整除, 余下来的数就是最低位上的数(因为一定小于3)
然后不断循环, 扣出所有位上的数即可

一般的 $a -> b$ 的进制转换可以先将 $a -> 10$, 再将 $10 -> b$

但是通过短除法, 可以直接将 a -> b, 利用的就是上面的原理(不需要使用秦九韶算法, 因为 a 不需要再进行额外的转换)

=> 让$a$不断除以$b$, 每次 $a = 商$, $b$的低位等于余数, 不断循环直到 $a = 0$
存储 b可以用vector不断push_back
练习题

任何进制都可以使用加减乘除运算, 只是进位需要转换成$x$进制

关于负数除法的注意点:

1. C艹始终向$0$取整, python是向下取整 => 例如 $-3 / 2 = -1…-1$ (向下取整, 并且C++可以允许余数为负数的情况)
2. 在数学计算中, 余数始终 $>= 0$
3. 商的符号 => 负负得正
4. 余数的符号 => 数学中的余数恒为正数, C艹中的余数符号与被除数相同
5. 右移与除法的不同点 : 右移是向下取整, 除$2$向$0$取整, 例如 -3 >> 1 = -2, -3 / 2 = -1 => 所以如果存在被除数是负数的情况, 不能用除法, 需要用右移才能取到中位数