位数（digits）的处理

2024-08-22 23:09:28

主要针对：二进制表示法，以及十进制表示法；

1. 获取位数

已知该数 n 采用十进制进行表示

二进制形式的位数：⌊log2n⌋+1
十进制形式的位数：⌊log10n⌋+1

2. 截断（保留前/后 m 位）

二进制：保留前 m 位 ⇒ 需要右移 n-m 位；
十进制：保留前 m 位 ⇒ 需要右移 n-m 位；
但这里的右移 n-m 位，涵义并不相同，二进制右移，对应着二进制位运算（除以 2n−m），十进制右移，对应的是十进制的位运算（除以 10n−m）；

// 保留整数 n 的前 m 位；

int part(int n, int m){

    return n / int(pow(10, int(log10(n))+1-m));

}

        part(123456789, 3) ⇒ 123

3. 一些应用

Karatsuba 快速乘积算法首先将两个整数分别一分为二。例如，a 和 b 各位 256 位的整数，那么使用 a1 和 b1 保存前 128 为，而 a0 和 b0 中保存后 128 位。分割后，a 和 b 可写成如下的形式。

{a=a0⋅10128+a1b=b0⋅10128+b1

最新文章

热门文章