转自：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)相同，负数无数学意义。