大整数算法[05] 移位操作 上一篇博文讲到了大整数位的相关操作，这次的内容依然和位的操作相关：移位操作。需要说明的是，这里所讲的大整数移位操作都是算术移位（左移的话精度会增加，而不是把移出的位丢掉）。 ★ 两种移位的区别 在移位操作当中存在两种不同的操作方式：逻辑移位和算术移位。在逻辑移位当中，移出的位丢失，移入的位取 0。在算术移位当中，移出的位丢失，左移入的位取 0，右移入的位取符号位，即最高位代表的数据符号保持不变。举个例子：有如下两个类型的变量（32位系统下）被定义： unsigned int u = 0x80000000; （8 后面有 7 个 0） int s = 0x80000000; 用二进制表示都是：1000 0000 0000 0000 0000 0000 0000 0000 u 跟 s 的区别在于 s 的最高位是符号位（0 代表正数，1 代表负数），所以如果用以下语句打印这两个变量，结果会是：2147483648， -2147483648。 printf(” u = 薥 u); printf(” s = %d ”, s); 第一个结果好说，无符号数就是 2^31，但是为什么第二个是 – 2^31 呢？按理说应该是 – 0 才对呀。原因是这些数都是用补码表示的。 先来看看 – 2^31 – 1 （-2147483647）这个数用补码怎么表示。 原码：1111 1111 1111 1111 1111 1111 1111 1111，注意最高位是符号位。要求补码，先计算反码，反码的计算是符号位不变，其余位取反。 反码：1000 0000 0000 0000 0000 0000 0000 0000，得到反码之后，将反码加 1 就得到补码了。 补码：1000 0000 0000 0000 0000 0000 0000 0001。所以 – 2^31 – 1 用补码表示就是 0x80000001。 要表示 – 2^31，只需要将 – 2^31 – 1 的补码减 1 即可，所以是 0x80000000，这就得到 32 位有符号整形下可表示的最小负整数。 下面看看进行移位后的结果是怎样的。 对于左移操作，不管是逻辑左移还是算术左移，左边移出的位都丢失，右边移入的位都取 0，所以如果执行如下两条语句：u <<= 1; s <<= 1; 其结果都是 0。 对于右移操作，逻辑右移左边补 0，算术右移左边补符号位。所以如果执行如下两条语句：u >>= 1; s >>= 1; 其结果：1073741824， -1073741824。结果的补码用二进制表示就是： u：0100 0000 0000 0000 0000 0000 0000 0000 s：1100 0000 0000 0000 0000 0000 0000 0000 上面的右移 1 位的操作，相当于在计算：2147483648 / 2 = 1073741824； – 2147483648 / 2 = – 1073741824。 对于移位操作，左移 n 位相当于乘以 2^n，右移 n 位相当于除以 2^n。 前面废话那么多就是想说明逻辑移位和算术移位是有区别嘀。对于大整数，算术移位操作不需要用什么补码，因为 dp 指向的内存保存的是大整数的绝对值，符号是用 sign 来跟踪的。另外和C里面不同的是，如果左移后位数不够，大整数的精度会增加，而不像C那样丢弃移出来的位。 ★ 左移和右移 b 个数位 简单来说就是乘以或除以 2 ^ (biL *b)，移位操作是以整个数位为单进行的。 左移 b 个数位： int bn_lshd(bignum *x, size_t b) { int ret; size_t i; bn_digit *top, *bottom; x->used += b; BN_CHECK(bn_grow(x, x->used)); top = x->dp + x->used – 1; bottom = x->dp + x->used – b – 1; for(i = x->used; i > b; i–) *top– = *bottom–; top = x->dp; for(i = 0; i < b; i++) *top++ = 0; clean: return ret; } 左移 b 个数位后，数位增加 b 位，所以 used 值要增加 b。使用 bn_grow 函数增加 bignum 的精度。然后用 top 指针指向 bignum 左移后的最高位，bottom 指针指向 bignum 当前的最高位，然后循环 used – b 次把每一个数位往左移动 b 个数位。操作结束后，让 top 指针指向最低位，循环 b 次把最低的 b 个数位置 0，完成移位操作。 右移 b 个数位： int bn_rshd(bignum *x, size_t b) { int ret = 0; size_t i; bn_digit *top, *bottom; if(x->used <= b) { BN_CHECK(bn_set_word(x, 0)); return ret; } bottom = x->dp; top = x->dp + b; for(i = 0; i < x->used – b; i++) *bottom++ = *top++; for(; i < x->used; i++) *bottom++ = 0; x->used -= b; clean: return ret; } 和左移不同的是，右移精度不会增加，但如果 used 的值小于等于 b，则 bignum 的最高位都会从右边被移出去，结果为 0。如果 used > b，让 bottom指向 bignum 的最低数位，top 指针指向第 b + 1 位，然后循环 used – b 次将每个数位往右挪动 b 个数位，最后将左边剩余的 b 位取 0，完成右移操作。 ★ 左移和右移 1 个比特位 很好理解，就是乘以 2 或者除以 2。下面的算法完成后会把 x 的值赋值给 y。 左移 1 位： int bn_lshift_1(bignum *y, const bignum *x) { int ret; size_t i, olduse, shift; bn_digit r, rr, *px, *py; BN_CHECK(bn_grow(y, x->used + 1)); olduse = y->used; y->used = x->used; px = x->dp; py = y->dp; r = 0; shift = (size_t)(biL – 1); for(i = 0; i < x->used; i++) { rr = *px >> shift; *py++ = (*px++ << 1) | r; r = rr; } if(r != 0) { *py = 1; y->used++; } py = y->dp + y->used; for(i = y->used; i < olduse; i++) *py++ = 0; y->sign = x->sign; clean: return ret; } 首先算法默认将 y 的精度增加到 x->used + 1 个数位，之所以要加 1，因为有可能刚好把最高位移到下一个数位中去。olduse 记录当前 y 的数位，然后将 y 的数位增加到 x 的数位，如果最终还有进位，y->used 还要加一。shift 变量表明每个数位要往右移动的比特位数，例如在 32 位系统下，shift = 31，64 位系统下 shift = 63。变量 r 存储上一个数位最左边的比特位，变量 rr 存储当前数位最左边的比特位。在循环当中，先将当前数位右移 shift 位来获得最左边的比特位，然后再将这个数位左移 1 位并且与右边数位的最左边比特位做 OR 操作，这样当前数位中的每一比特位就往左边移动了 1 位，并且右边数位的最左边比特位也移动到当前数位的最右位置。循环结束后，如果 r 不为 0，表明原来 bignum 最左边数位的最左边比特位为 1，在左移中被移到了新的数位中，所以 used 加一，新的数位值为 1。最后将 y 的高位设置为 0，把 x 的符号给 y 完成所有操作。 右移 1 位： int bn_rshift_1(bignum *y, const bignum *x) { int ret; size_t i, olduse, shift; bn_digit r, rr, *px, *py; BN_CHECK(bn_grow(y, x->used)); olduse = y->used; y->used = x->used; px = x->dp + y->used – 1; py = y->dp + y->used – 1; r = 0; shift = (size_t)(biL – 1); for(i = y->used; i > 0; i–) { rr = *px & 1; *py– = (*px– >> 1) | (r << shift); r = rr; } py = y->dp + y->used; for(i = y->used; i < olduse; i++) *py++ = 0; y->sign = x->sign; bn_clamp(y); clean: return ret; } 右移 1 位精度不会增加，不过仍然要调用 bn_grow 函数增加精度，因为一开始 y 的精度可能不够。右移 1 位的操作跟左移 1 位的操作比较类似，只是方向相反。在第一个循环当中，先当前数位的最右比特位存放到变量 rr 中，然后当前数位右移 1 位，接着将左边数位的最右比特位左移 shift 位后与当前数位做 OR 操作，最后将 rr 的值存放到变量 r 中，这样当前位的所有比特都往右移动了 1 位，并且左边数位的最右边比特也移动到当前数位的最左边。完成循环后将高位设置为 0，然后设置符号位，最后压缩多余位完成操作。 ★ 左移和右移 n 个比特位 如果说前面的移位操作都带有特殊性，那么下面这两个操作就是将其一般化而已。左移或右移 n 位相当于乘以或除以 2^n。 左移 n 位： int bn_lshift(bignum *y, const bignum *x, size_t count) { int ret; size_t i, d, shift; bn_digit r, rr, *py; if(y != x) BN_CHECK(bn_copy(y, x)); BN_CHECK(bn_grow(y, y->used + count / biL + 1)); if(count >= biL) BN_CHECK(bn_lshd(y, count / biL)); d = count & (biL – 1); if(d != 0) { py = y->dp; shift = (size_t)(biL – d); r = 0; for(i = 0; i < y->used; i++) { rr = (*py >> shift); *py = (*py << d) | r; py++; r = rr; } if(r != 0) y->dp[y->used++] = r; } clean: return ret; } 首先算法检查并增加 y 的精度，接着如果左移的位数 count 大于或等于一个数位的比特数，调用 bn_lshd 函数将 x 左移 count / biL 个数位，然后检查是否有剩余的比特位：d = count & (biL – 1)，如果 d 不为 0，表明还有剩余位，按照左移 1 位的原理提取剩余位向左移动完成左移 n 位的操作。 右移 n 位： int bn_rshift(bignum *y, const bignum *x, size_t count) { int ret = 0; size_t i, d, shift; bn_digit r, rr, *py; if(y != x) BN_CHECK(bn_copy(y, x)); if(count >= biL) BN_CHECK(bn_rshd(y, count / biL)); d = count & (biL – 1); if(d != 0) { py = y->dp + y->used – 1; shift = (size_t)(biL – d); r = 0; for(i = y->used; i > 0; i–) { rr = *py; *py = (*py >> d) | (r << shift); py–; r = rr; } } bn_clamp(y); clean: return ret; } 和左移 n 位一样，先做整个数位的右移，然后再按照右移 1 位的原理往右移动剩余的比特位。要注意的是，右移之后，需要压缩多余位来更新 used 的值。 ★ 时间复杂度分析 本文所讲到的移位操作，都是在一重循环内完成的，算法的复杂度与 bignum 的精度和大小有关，时间复杂度大致为 O(n)。 ★ 总结 移位操作对于某些特殊的计算是十分有效的，比如乘以或除以 2，因此碰到这类计算，最好使用移位操作而不是乘法或除法。讲完了大整数的位操作，接下来就要开始讲讲四则运算了。下一篇文章将介绍绝对值加法。 【回到本系列目录】 版权声明 原创博文，转载必须包含本声明，保持本文完整，并以超链接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4357222.html
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/83772.html
