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

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

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

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

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

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

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

下面附代码:

《只用位运算来写整数四则运算程序》有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/

发表评论

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