听同学百度二面中,不准用四则运算操作符来实现四则运算。一想就想到了计算机组成原理上学过的。位运算的思想可以应用到很多地方,这里简单的总结一下用位运算来实现整数的四则运算。
加法运算:
int AddWithoutArithmetic(int num1,int num2)
{
if(num2==0) return num1;//没有进位的时候完成运算
int sum,carry;
sum=num1^num2;//完成第一步没有进位的加法运算
carry=(num1&num2)<<1;//完成第二步进位并且左移运算
return AddWithoutArithmetic(sum,carry);//进行递归,相加
}
简化一下:
int Add(int a,int b)
{
return b ? Add(a^b,(a&b)<<1) : a;
/*if(b)
return Add(a^b,(a&b)<<1);
else
return a;*/
}
上面的思路就是先不计进位相加,然后再与进位相加,随着递归,进位会变为0,递归结束。
非递归的版本如下:
int Add(int a, int b)
{
int ans;
while(b)
{ //直到没有进位
ans = a^b; //不带进位加法
b = ((a&b)<<1); //进位
a = ans;
}
return a;
}
减法运算:
//这个和加法一样了,首先取减数的补码,然后相加。
int negtive(int a) //取补码
{
return Add(~a, 1);
}
int Sub(int a, int b)
{
return Add(a, negtive(b));
}
正数乘法运算:
//正数乘法运算
int Pos_Multiply(int a,int b)
{
int ans = 0;
while(b)
{
if(b&1)
ans = Add(ans, a);
a = (a<<1);
b = (b>>1);
}
return ans;
}
整数除法(正整数)
//除法就是由乘法的过程逆推,依次减掉(如果x够减的)y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。
int Pos_Div(int x,int y)
{
int ans=0;
for(int i=31;i>=0;i--)
{
//比较x是否大于y的(1<<i)次方,避免将x与(y<<i)比较,因为不确定y的(1<<i)次方是否溢出
if((x>>i)>=y)
{
ans+=(1<<i);
x-=(y<<i);
}
}
return ans;
}
完整的实现:
// 加减乘除位运算
// 程序中实现了比较大小、加减乘除运算。所有运算都用位操作实现
// 在实现除法运算时,用了从高位到低位的减法
// 具体如下,算法也比较简单,所以没有作注释
#include<iostream>
#include<cstdio>
using namespace std;
int Add(int a, int b)
{
int ans;
while(b)
{ //直到没有进位
ans = a^b; //不带进位加法
b = ((a&b)<<1); //进位
a = ans;
}
return a;
}
//这个和加法一样了,首先取减数的补码,然后相加。
int negtive(int a) //取补码
{
return Add(~a, 1);
}
int Sub(int a, int b)
{
return Add(a, negtive(b));
}
// 判断正负
int ispos( int a )
{ //正
return (a&0xFFFF) && !(a&0x8000);
}
int isneg( int a )
{ //负
return a&0x8000;
}
int iszero( int a )
{ //0
return !(a&0xFFFF);
}
//正数乘法运算
int Pos_Multiply(int a,int b)
{
int ans = 0;
while(b)
{
if(b&1)
ans = Add(ans, a);
a = (a<<1);
b = (b>>1);
}
return ans;
}
//乘法运算
int Multiply(int a,int b)
{
if( iszero(a) || iszero(b) )
return 0;
if( ispos(a) && ispos(b) )
return Pos_Multiply(a, b);
if( isneg(a) )
{
if( isneg(b) )
{
return Pos_Multiply( negtive(a), negtive(b) );
}
return negtive( Pos_Multiply( negtive(a), b ) );
}
return negtive( Pos_Multiply(a, negtive(b)) );
}
//除法就是由乘法的过程逆推,依次减掉(如果x够减的)y^(2^31),y^(2^30),...y^8,y^4,y^2,y^1。减掉相应数量的y就在结果加上相应的数量。
int Pos_Div(int x,int y)
{
int ans=0;
for(int i=31;i>=0;i--)
{
//比较x是否大于y的(1<<i)次方,避免将x与(y<<i)比较,因为不确定y的(1<<i)次方是否溢出
if((x>>i)>=y)
{
ans+=(1<<i);
x-=(y<<i);
}
}
return ans;
}
//除法运算
int MyDiv( int a, int b )
{
if( iszero(b) )
{
cout << "Error" << endl;
exit(1);
}
if( iszero(a) )
return 0;
if( ispos(a) )
{
if( ispos(b) )
return Pos_Div(a, b);
return negtive( Pos_Div( a, negtive(b)) );
}
if( ispos(b) )
return negtive( Pos_Div( negtive(a), b ) );
return Pos_Div( negtive(a), negtive(b) );
}
// 比较两个正数的大小(非负也可)
int isbig_pos( int a, int b )
{ //a>b>0
int c = 1;
b = (a^b);
if( iszero(b) )
return 0;
while( b >>= 1 )
{
c <<= 1;
}
return (c&a);
}
// 比较两个数的大小
int isbig( int a, int b )
{ //a>b
if( isneg(a) )
{
if( isneg(b) )
{
return isbig_pos( negtive(b), negtive(a) );
}
return 0;
}
if( isneg(b) )
return 1;
return isbig_pos(a, b);
}
分享到:
相关推荐
将近250行的算法 实现了通过字符串进行加减乘除四则运算 纯通过处理字符串和数组实现 希望能帮助大家: 例如:String input "33+26 77+70"; String result ""; try { result Account...
汇编实现一位十进制加减乘除四则运算的计算器,代码简单易懂
大整数四则运算 BigInt 加减乘除 括号 优先级,Python支持无限精度的运行,Java有BigInteger类,但是对C和C++就只能自己实现,这是一个带加减乘除运算的实现。
基于条件结构实现两个数的加减乘除运算
大数四则运算 大数四则运算(大数加减乘除,无限位数运算) 大数 数据结构 加减乘除 无限位数 运算
按照IEEE754浮点数标准,完整的浮点数加乘除四则运算的程序,每个都是单独的一个文件,注释完整。编译仿真全通过!
C语言 实现四则运算 加减乘除
数据加减乘除四则运算 无数据校验,只能对整数数据进行操作运算 QQ:405418144 E_mail:sgzhou12345@sina.com
汇编程序设计之加减乘除四则运算,课程设计论文报告,含流程图,附带源码,Window下双击EXE文件即可运行,欢迎下载交流学习
用C++编写的四则运算 采用类的思想 各个击破 包括加减乘除
自己写的加减乘除四则运算,写着练手,代码有点乱,不知道别人能看懂不
加减乘除四则运算
一篇用汇编语言实现的加减乘除四则运算,是一篇实验报告。
上课时编的基于对话框的简单计算器程序, 有两个输入框,一个输出框,加减乘除四个按钮。 可以看看
可以实现简单加减乘除运算,用C语言实现的计算器 希望对大家有所帮助
汇编语言 加减乘除四则运算 程序 汇编语言 加减乘除四则运算 程序
mips整数运算模拟IEEE754浮点数运算的加减乘除
C++版本的四则运算事例,支持负数,表达式中可以含有空格,讲解文章:https://www.cnblogs.com/swarmbees/p/9356346.html
本程序实现两个非负整数的加减乘除四则高精度运算; 有比较详细的注释,测试了10组随机数据并未出现运行时错误。 如果发现程序有bug,欢迎提出指正!
加减乘除四则运算汇编程序及源代码