只用位运算来写整数四则运算程序

整数在计算机中是以二进制形式存储的,整数的运算归根到底是二进制位的逻辑运算。

那么如何用最基本的位运算来实现整数的四则运算?

我今天写了“加”、“减”、“乘”、“除”、“取余”和“取相反数”这几种基本运算,代码中只用到了位运算。

我选择的是short型数值,并用代码循环了所有可能的情况(两个操作数分别从-32768到32767),可以验证我的运算函数的结果和直接做运算的结果是完全相同的(包括溢出的情况)。这些函数经过简单修改很容易支持更多位的整数。

有符号整数右移操作会复制符号位,我把一些函数的参数设置成了unsigned类型的,但是调用函数的时候可以直接传进有符号数。“加”、“减”、“乘”函数传进无符号数也可以得到正确结果。

由于有符号数中负数比正数多一个-32768,所以为了让程序支持边界条件,除法运算中所有操作都是针对负数进行的。

下面附代码:

short ADD(register unsigned short a,register unsigned short b){
    register unsigned short t;
    do{
        t=a&b;
        a^=b;
        b=t<<1;
    }while(t);
    return a;
}

short MINUS(register unsigned short a){
    return ADD(~a,1);
}

short SUB(register unsigned short a,register unsigned short b){
    return ADD(a,MINUS(b));
}

short MUL(register unsigned short a,register unsigned short b){
    register unsigned short r=0;
    while(a){
        if(a&1)r=ADD(r,b);
        a>>=1;
        b<<=1;
    }
    return r;
}

short DIV(register short a,register short b){
    register short r=0;
    register char t=0;
    register char s=(unsigned short)(a^b)>>15;
    if(b==0)exit(-1);
    if(a>0)a=MINUS(a);
    if(b>0)b=MINUS(b);
    while(a<=(b<<t))t++;
    while(a<=b){
        while(a>(b<<t))t--;
        a=SUB(a,(b<<t));
        r|=1<<t;
    }
    return s?MINUS(r):r;
}

short MOD(register short a,register short b){
    return SUB(a,MUL(DIV(a,b),b));
}

《只用位运算来写整数四则运算程序》有4个想法

  1. 这篇文章很赞!

    你给的加法是 O(n) 的复杂度,其中 n 是二进制位数。事实上可以用 O(log n) 时间算出来,现代 CPU 里加法器就是用 Kogge–Stone adder 的原理造的。
    http://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder
    代码
    http://www.quora.com/How-would-you-add-two-integers-using-bit-manipulation?

    如果你对位运算的奇技淫巧感兴趣,Hacker’s Delight 这本书一定不会让你失望:
    http://www.hackersdelight.org/

    1. 超前进位加法器。。。
      位运算完成工作的方法可以理解为CPU的工作方式。。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注