大整数算法[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("\nu = %u\n", u);
printf("\ns = %d\n", 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，因此碰到这类计算，最好使用移位操作而不是乘法或除法。讲完了大整数的位操作，接下来就要开始讲讲四则运算了。下一篇文章将介绍绝对值加法。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
