大整數算法[04] 位操作，整數算法04操作

大整數算法[04] 位操作，整數算法04操作

       上一篇文章介紹了大整數的比較操作，今天來談談和位相關的操作。

        ★ 引子

        在大整數的表示和相關定義這篇文章中講到了大整數是如何表示的。為了方便後面的講解，這裡先按照前面的定義，給出一個大整數的例子（32位系統下，每一個數位長度為32比特）：

         假設有一 bignum x，十進制值為 1134924633606254832，對應的十六進制值為 0xFC00FF0F0F0F0F0，那麼按照大整數的表示方法， 2^32 進制就表示成（每一位用逗號隔開）：

        （264245232，4042322160） 即：1134924633606254832 / (2^32) = 264245232, 1134924633606254832 mod (2^32) = 4042322160。

         高位用二進制表示為：0000 1111 1100 0000 0000 1111 1111 0000

         低位用二進制表示為：1111 0000 1111 0000 1111 0000 1111 0000

         ★ 返回指定下標 pos 的比特位

          這裡的下標（pos）是從大整數的最低為開始，並且以 0 作為起始值，例如上述 bignum x 中下標為 3 的比特位為 0，下標為 4 的比特位為 1。

          給定一個 pos 值，要找出對應的比特位在哪裡，可以先找到 pos 對應的比特位到底在大整數的哪一個數位中。比如當 pos = 38 時，pos / biL = 38 / 32 = 1，

biL （bits in limbs）為數位的比特長度，32 位系統下 biL 為 32。這樣就知道 pos 對應的比特位在大整數 x 的第二個數位中（對應於下標為 1 的數組單元中）。找到了大概位置，就要確定在數位中的具體位置了，這可以通過做求余運算得到：pos % biL = 38 mod 32 = 6，這樣將該數位右移 6 位後與 1 做一次邏輯與操作，即可得到 pos 對應的比特值為 1 （對應紅色標明的那一位）。（0000 1111 1100 0000 0000 1111 1111 0000，1111 0000 1111 0000 1111 0000 1111 0000）

boolean bn_get_bit(const bignum *x, const size_t pos)
{
    boolean bit;

    //pos is zero base number

    if(x->alloc * biL <= pos)
        return 0;

    bit = (x->dp[pos / biL] >> (pos & (biL - 1))) & 1;

    return bit;
}

       在 2 的補碼運算中，計算 a mod (2^n) 等價於 a AND (2^n - 1)。

         ★ 給定下標值 pos 設置對應位置的比特位

         和前面的原理一樣，先找到 pos 對應的比特位的位置。假設 pos = 35，則 offset = pos / biL = 1， mod = pos / biL = 3。找到對應的位置後，要先把該位的值清空，具體的做法是：將 1 左移 mod = 3 位，然後取反，這時操作結果的二進制就會是 1111 1111 1111 1111 1111 1111 1111 0111，與大整數的第二個數位（對應數組下標為 1）進行與運算，便清空該位的值。然後將函數傳入的 boolean 類型的 value 左移 mod = 3 位後與大整數的第二個數位做或運算即可把新的比特位設置好。

int bn_set_bit(bignum *x, const size_t pos, boolean value)
{
    int ret = 0;
    size_t offset, mod;

    //pos is zero base number

    if(value != TRUE && value != FALSE)
        return BN_INVALID_INPUT;

    offset = pos / biL;
    mod = pos & (biL - 1);

    if(pos >= x->alloc * biL)
    {
        if(value == FALSE) return 0; //如果pos超過了分配的數位並且value為0，則無需操作，因為高位默認為0，否則需要增加精度。
        BN_CHECK(bn_grow(x, offset + 1));
    }

    x->dp[offset] &= ~((bn_digit)1 << mod);
    x->dp[offset] |= ((bn_digit)(value) << mod);

    x->used = x->alloc;  //如果bignum的精度增加，則需要從最左邊的數位開始往右檢查有效數位，保證used值的正確。
    bn_clamp(x);  //壓縮多余位

clean:

    return ret;
}

         ★ 返回有效比特位的數量

         有效比特位是指從左起第一個不為 0 的比特位開始到最右比特位為止的中間所有比特位。例如本文給出的例子，除最高位的前四個比特位之外，其他都是有效的比特位，有效比特位的數量是 60。按照前面所說的，可以很容易得到下面的算法：

size_t bn_msb(const bignum *x)
{
    size_t i, j;

    i = x->used - 1;

    for(j = biL; j > 0; j--)
        if(((x->dp[i] >> (j - 1)) & 1) != 0)
            break;

    return biL * i + j;
}

         這個算法的意義在於可以計算出一個 bignum 的實際比特大小，雖然簡單，但在後面很多算法中會多次用到。

         ★ 返回最低有效比特位前 0 的數量

          最低有效比特位是指從右起第一個不為 0 的比特位，本例中 bignum x 的最低有效比特位就是位於低數位中從右起下標為 4 的比特位。前面 0 的數量為 4。於是可以很容易寫出如下算法：

size_t bn_lsb(const bignum *x)
{
    size_t i, j;

    for(i = 0; i < x->used; i++)
    {
        if(x->dp[i] != 0)
        {
            for(j = 0; j < biL; j++)
            {
                if(((x->dp[i] >> j) & 1) != 0)
                    return i * biL + j;
            }
        }
    }

    return 0;
}

        對於一個整數 p（p > 0）， 都可以通過如下的形式表示：p = q * 2^r，其中 q 是一個奇數，例如 36 = 9 * 2^2， r = 2。bn_lsb 算法的意義在於可以通過計算最低有效比特位前 0 的數量來計算 r 的值。這個算法雖然也很簡單，但它會在後面計算最大公約數的算法中大顯身手。

         ★ 返回 bignum 的字節大小

         這裡要注意的是：這個操作不是返回 bignum 占用了多少內存，例如對於 bignum x，即使一開始分配了 3 個單元的內存，其字節大小仍然是 8 byte。計算 bignum 的字節大小，只需要將 x 的比特大小加上 7 除以 8 即可。加上 7 的目的是避免 x 的比特位不是 8 的倍數時除完之後少了一個字節。

size_t bn_size(const bignum *x)
{
    return ((bn_msb(x) + 7) >> 3);
}

         ★ 總結

         大整數位的相關操作原理不難，但是如果一開始沒有定義好 bignum 的結構，比如使用十進制，那麼操作起來就是相當麻煩，這再一次說明編程時二進制思維是很重要嘀。下一篇文章會介紹大整數的移位操作。

     【回到本系列目錄】

版權聲明
原創博文，轉載必須包含本聲明，保持本文完整，並以超鏈接形式注明作者Starrybird和本文原始地址：http://www.cnblogs.com/starrybird/p/4355521.html