用位运算实现四则运算之加减乘除(用位运算求一个数的1/3) via Hackbuteer1

转自:http://blog.csdn.net/hackbuteer1/article/details/7390093

^: 按位异或;&:按位与; | :按位或

计算机系统中,数值一律用补码来表示:因为补码可以使符号位和数值位统一处理,同时可以使减法按照加法来处理。

对补码做简单介绍:数值编码分为原码,反码,补码,符号位均为0正1负。

原码 -> 补码: 数值位取反加1

补码 -> 原码: 对该补码的数值位继续 取反加1

补码 的绝对值(称为真值):正数的真值就是本身,负数的真值是各位(包括符号位)取反加1(即变成原码并把符号位取反).

b -> -b : 各位(包括符号位)取反加1

加法运算:将一个整数用二进制表示,其加法运算就是:相异(^)时,本位为1,进位为0;同为1时本位为0,进位为1;同为0时,本位进位均为0.

所以,不计进位的和为sum = a^b,进位就是arr = a&b,(与sum相加时先左移一位,因为这是进位)。完成加法直到进位为0.

减法运算:a-b = a+(-b)  根据补码的特性,各位取反加1即可(注意得到的是相反数,不是该数的补码,因为符号位改变了)

(上面用二进制实现的加减法可以直接应用于负数)

乘法运算:原理上还是通过加法计算。将b个a相加,注意下面实际的代码。

除法运算:除法运算是乘法的逆。看a最多能减去多少个b,


加法运算:

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);
}


一、移位运算符及其规则

移位运算符就是在二进制的基础上对数字进行平移,是在补码的基础上进行操作的。按照平移的方向和填充数字的规则分为三种:<<(左移)、>>(带符号右移)、>>>(无符号右移)。

左移运算符的规则:

(1).int类型数值实际移位的次数是和32的余数,移位33次和移位1次得到的结果相同;

例如int a=1,b=32; a<<b;

在程序预处理阶段,编译器会自动执行b=b&31;(一个数的余数,即与这个数减一后做位and运算),因此b=0,所以a<<b;之后,a=1。

(2).byte、short和char类型移位的结构会变成int类型,自然要满足规则(1)

(3).long类型数值实际移位的次数是和64的余数,移位66次和2次得到的结构相同。

右移运算符的规则:没有左移的那些要求

二、三种移位运算符的介绍:

(1)左移运算符(<<)

语法格式:需要移位的数字<<移位的次数;

规则:高位移出舍弃,低位的移入补零;

数学意义:在数字没有溢出的前提下,对于正数和负数,左移一位都相当于乘以2的1次方,左移n位就相当于乘以2的n次方。

(2)带符号右移运算符(>>)

语法格式:需要移位的数字>>移位的次数;

规则:低位移出舍弃,高位的空位补符号位,即正数补零,负数补1;

数学意义:对于正数,当移出的位中没有1时,右移一位相当于除2,右移n位相当于除2的n次方;对于负数,当移出的位中没有0时,右移一位相当于除2,右移n位相当于除2的n次方。

(3).无符号右移运算符(>>>)

语法格式:需要移位的数字>>>移位的次数

规则:低位移出舍弃,高位补零。对于正数来说,与(2)相同,而对于负数则不同;

数学意义:正数与(2)相同,负数无数学意义。

上一篇:二分答案 & 洛谷 P2678 跳石头


下一篇:快速阅读《QT5.9 c++开发指南》2