上一篇博文講到了大整數位的相關操作，這次的內容依然和位的操作相關：移位操作。需要說明的是，這裡所講的大整數移位操作都是算術移位（左移的話精度會增加，而不是把移出的位丟掉）。
★ 兩種移位的區別
在移位操作當中存在兩種不同的操作方式：邏輯移位和算術移位。在邏輯移位當中，移出的位丟失，移入的位取 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，因此碰到這類計算，最好使用移位操作而不是乘法或除法。講完了大整數的位操作，接下來就要開始講講四則運算了。下一篇文章將介紹絕對值加法。
【回到本系列目錄】
版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4357222.html
