长整数－－左移与右移

代码下载：

git clone git://git.code.sf.net/p/cutility/code cutility-code

长整数总共有两个文件一个为big_integer.h，一个为big_integer.c

在看这一篇文章这前你需要了解长整数的数据结构

(一)简介

BGInteger内部采用二进制的方式来存储数值，移位运算相对来说比其它的运算简单一点。主要的问题是在计算机内部，数据是采用补码的形式存储，而BGInteger采用的编码方式为原码。如果BGInteger为正，原码与补码相等，可以直接对BGInteger中的数值移位；但如果是负数，则需要把原码转换为补码后才能进行移位操作，转换公式如下：

补码＝反码＋1                                    

(二)补码与原码的转换

原码转换为补码的代码为：

/* translate original code to complement */
static void units_invert_complement(b_unit* d,b_unit* s,int size)
{
    b_unit carry=1;
    int i;
    for(i=0;i<size;i++)  /*补码= ~原码 +1 */
    {
        carry=(~s[i]&MASK)+carry;
        d[i]=carry&MASK;
        carry>>=SHIFT;
    }

    assert(carry==0);
}

补码转换为原码的代码为：

/* translate complement to original */
static void units_invert_origin(b_unit* d,b_unit* s,int size)
{
    b_unit carry=1;
    int i;
    for(i=0;i<size;i++) /*原码＝~(补码-1) */
    {
        carry=s[i]-carry;
        d[i]=(~carry)&MASK;
        carry>>=SHIFT;
    }
    assert(carry==0);
}

(三)左移与右移

(1)左移:

BGInteger最多支持对一个数左移2^31位，并且位移量必须为正数。因为负数的左移与右移都是补0，所以在左移负数时，可以直接使用原码。

BGInteger* bg_lshift(BGInteger* l,BGInteger* r)
{
    if(r->b_len<0) /*判断r是否为负，如果是则反加为NULL*/
    {
        WARN("Negative Shift Value");
        return NULL;
    }
    if(r->b_len==0)/*如果位移量为0,直接复制l，并返回*/
    {
        return bg_clone(l);
    }
    int shift_value=bg_to_abs_int(r); /*把r的绝对值转换为整型，如果|r|>2^31，返回值为负1*/

    if(shift_value<0) /*位移量太大，不能处理*/
    {
        WARN("Shift Value Is Too BIG");
        return NULL;
    }
    BGInteger* ret=abs_lshift(l,shift_value); /*绝对值左移，函数如下*/
    if(l->b_len<0)
    {
        self_negative(ret); /*如果l为负，则位移后的结果也为负*/
    }
    return ret;
}

static inline BGInteger* abs_lshift(BGInteger* l,int shift_value)
{

    int l_len=abs(l->b_len); /*l的长度*/
    b_unit* l_val=l->b_val;

    int t_len=l_len+shift_value/SHIFT+1; /*计算位移后的长度*/
    BGInteger* ret=bg_malloc(t_len);   /*分配空间*/
    b_unit carry;
    /*把数组位移，函数如下*/
    carry=units_lshift(ret->b_val+shift_value/SHIFT,l_val,l_len,shift_value%SHIFT);
    ret->b_val[shift_value/SHIFT+l_len]=carry; /*保存移出位*/

    bg_format_len(ret);
    return ret;
}

static b_unit units_lshift(b_unit* d,b_unit* s,int size, int shift_value)
{
    /*把数组s位移shift_value位到数组d*/
    /*shift_value必须小于SHIFT,SHIFT的值为15*/
    assert(size>=0&&shift_value<SHIFT);
    twob_unit t=0;
    int i;
    for(i=0;i<size;i++)
    {
        d[i]=(s[i]<<shift_value|t)&MASK;
        t=(s[i]>>(SHIFT-shift_value))&MASK;
    }
    return t;  /*返回溢出位*/
}

右移：

正数的右移用0补全，负数的右移则是用1补全，所以右移负数时，要涉及到编码的转换。和左移一样，位移量不能大于2^31，并且位移量不能为负

/*@condition r>=0
*/
BGInteger* bg_rshift(BGInteger* l,BGInteger* r)
{
    int l_len=l->b_len;
    int r_len=r->b_len;

    if(l_len==0) /*如果l为0,则直接返回0*/
    {
        return bg_create_zero();
    }
    if(r_len==0) /*如果位移量为0，直接复制l，并返回*/
    {
        return bg_clone(l);
    }
    if(r_len<0)  /*位称量不能为负*/
    {
        BUG("Shift With Negative Value");
        return NULL;
    }

    int shift_value=bg_to_abs_int(r); /*把r的绝对值转换为整型，如果r>2^31，则返回为-1*/

    /* bits(r)>31, is to big, so return NULL*/
    if(shift_value<0)
    {
        WARN("RSHIFT Right Is Too Big");
        return NULL;
    }
    BGInteger* ret=i_rshift(l,shift_value); /*该函数如下*/
    return ret;
}

static BGInteger* i_rshift(BGInteger* l,int shift_value)
{
    int l_len=abs(l->b_len);
    assert(shift_value>=0);
    BGInteger* ret=0;

    /* bits(l) < shift_value*/
    if(l_len*SHIFT<=shift_value)  /*如果位移量大于l的位数*/
    {
        if(l->b_len<0)           /*如果l为负，返回-1*/
        {
            return bg_create_from_int(-1);
        }
        else
        {
            return bg_create_zero();  /*如果l为正，返回0*/
        }
    }

    int sign=l->b_len<0?1:0;    /*判断l的正负*/

    ret=bg_malloc(l_len-shift_value/SHIFT);  /*为移位后的结果分配空间*/

    int shift_pre=shift_value/SHIFT;
    int shift_pos=shift_value%SHIFT;

    int size=l_len-shift_pre;
    int d=shift_pos;


    b_unit* ivt_l=malloc(sizeof(*ivt_l)*l_len);

    /* if l is negative , translate to complement */
    if(sign)
    {
        /*如果为负，则把l转换为补码后才位移*/
        units_invert_complement(ivt_l,l->b_val,l_len);
    }
    else
    {
        /*正数则不需要转换,直接复制*/
        memcpy(ivt_l,l->b_val,l_len*sizeof(*ivt_l));
    }

    b_unit* src=ivt_l+shift_pre;
    b_unit c_src;
    b_unit oflow=0; /*l为正，高位用0补全*/
    if(sign)
    {
        /* if left is negative, fill high bits 1 */
        /*如果l为负，高位用1补全*/
        oflow=(1<<d)-1;
    }
    oflow=(oflow<<(SHIFT-d))&MASK;
    int i=size;

    /* Right SHIFT */
    while(i--)   /*位移*/
    {
        c_src=src[i];
        src[i]=oflow|((c_src&MASK)>>d);
        oflow=(c_src<<(SHIFT-d))&MASK;
    }

    if(sign)
    {
        /* translate complement to original */
        /*如果为负数，则还需要把补码转换为原码*/
        units_invert_origin(ret->b_val,src,size);
        self_negative(ret);
    }
    else
    {
        memcpy(ret->b_val,src,sizeof(*src)*size);
    }

    free(ivt_l);
    bg_format_len(ret);

    return ret;
}