二进制位运算实现乘法程序

《二进制位运算实现乘法程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、位运算实现乘法运算在回答本问题之前，先学习一些有关位运算的知识。(1)常用的等式：-n=~（n-1）=~n+1(2)获取整数n的二进制中最后一个1:n&~(n-1)或者n&(-n)。例如n=010100,则-n=101100，n&(-n)=000100。(3)去掉整数n的二进制中最后一个1:n&(n-1)。例如n=010100,n-1=010011,则n&(n-1)=010000。注：对n为正数或者负数都适用。先看一个实例：1011*1010，因为二进制运算的特殊性，可以将该乘法运算

2、表达式拆分成两个运算，1011*0010于1011*1000的和。而对于二进制运算，左移一位，等价于乘以0010，左移三位，等价于乘以1000,所以两者的乘积为10110于1011000的和，即为1101110.因而乘法可以通过一系列的移位和加法运算完成。最后一个1通过n&~(n-1)求得，可通过n&(n-1)去掉最后一个1，为了高效的得到左移的位数，可提前计算一个map。算法如下，所示：#include#include#includeusingnamespacestd;intmultiply(inta,i

3、ntb){boolneg=(b