(笔试题)只用逻辑运算实现乘法运算
实现 运算 笔试 乘法 只用 逻辑运算
2023-09-14 08:59:06 时间
题目:
如题所示
思路:
看一个实例,1011*1010,由于二进制的特殊性,可以将该乘法运算表达式拆分为两个运算,1011*1000以及1011*0010的和,对于二进制运算,左移一位,等价于乘以0010,左移三位,等价于乘以1000,因此两者的乘积为10110+1011000之和,即为1101110.
通过上述例子,可知一个乘法运算可以转化为一系列的移位和加法运算来完成。如a*b
最后一个1可通过b&~(b-1)求得,可通过b&(b-1)去掉,为了高效得到左移的位数,可以提前计算并保存在map中。
代码:
#include <iostream> #include <map> using namespace std; int add(int num1,int num2){ if(num1==0) return num2; if(num2==0) return num1; int num_xor=num1^num2; int carry=(num1&num2)<<1; return add(num_xor,carry); } int multiply(int a,int b){ bool neg=false; if(a>0 && b<0){ neg=true; b=-b; } if(a<0 && b>0){ neg=true; a=-a; } if(a<0 && b<0){ a=-a; b=-b; } map<int,int> bit_map; for(int i=0;i<32;i++) bit_map.insert(pair<int,int>(1<<i,i)); int sum=0; while(b>0){ int last_bit=bit_map[b&~(b-1)]; //sum+=(a<<last_bit); sum=add(sum,a<<last_bit); b=b&(b-1); } if(neg) sum=-sum; return sum; } int main() { int a=11,b=-10; cout << multiply(a,b) << endl; return 0; }
相关文章
- 初探和实现websocket心跳重连(npm: websocket-heartbeat-js)
- Java实现 LeetCode 241 为运算表达式设计优先级
- Java实现 LeetCode 189 旋转数组
- Java实现 蓝桥杯 算法提高 最大值路径
- Java实现 蓝桥杯VIP 算法提高 乘法运算
- 通过重写虚方法实现加法运算
- thymeleaf+bootstrap,onclick传参实现模态框中遇到的错误
- (笔试题)只用逻辑运算实现乘法运算
- 2044. 统计按位或能得到最大值的子集数目(dfs实现组合型枚举&或位运算)
- Linux 安装与NAT实现上网
- MySQL Percona PXC集群实现MySQL主从复制强一致性
- 利用位运算实现一个字段表示多个属性
- Backbone - create model的实现原理
- Atitit.单向sso 单点登录的设计与实现
- Angular sort recursive的实现原理
- 双色球算法实现
- Java实现中文算数验证码(算数运算+-*/)
- 【信号处理】天线分集与空时编码技术——瑞利衰落信道下MRC性能(matlab代码实现)
- Python图像处理丨三种实现图像形态学转化运算模式
- 从源码分析快速实现对新开源软件的检测
- python 代码小技巧之一行代码转换列表中的数据并实现运算
- reactos操作系统实现(125)
- 分布式 Web UI 自动化系统的设计与实现
- VC++中实现INI文件读写的方法和示例
- Java Swing文本编辑器的实现
- 数据结构与算法详解(含算法分析、动图图解、Java代码实现、注释解析)
- 【信号检测】基于长短期记忆(LSTM)在OFDM系统中基于深度学习的信号检测(Matlab代码实现)