位运算四则运算
一、位运算简介
我们先来熟悉下位运算的操作，大致要用到的位运算如下：
与(&)操作，该操作先将数值转换为二进制（如：a=3 => a=11），然后再进行操作。会对两个数相同的位置上进行操作，如果两个操作数长度不一致，会对值较短的数进行高位补0。（如：a =3 , b = 4, a+b = 011+100）；相同位置为全1才为1，有0必为0，则上述结果：a&b = 000。或(|)操作，跟与(&)操作不一样的地方在于，相同位置有1则1。a|b = 000。异或(^)操作，相同则为0，不同则为1。a^b = 111。
我们将从加法开始依次分析。
二进制加法
可以很轻松的利用异或(^)操作与与(&)操作来实现加法的运算。与(&)操作可以用来获取两者相加进位，因为相同的位置同时出现1结果才为1，那么此时对结果集进行左移(<<)操作得到即为进位的值，采用异或(^)操作得到的是我们不带进位的相加结果，再利用不带进位与进位相加，依次迭代，即可以求出我们需要的值。
例如：a=010010，b=100111,计算步骤如下：
代码清单 1.
public int add(int sum1,int sum2){
if(sum1 == 0) return sum2;
if(sum2 == 0) return sum1;
//这里sum代表结果集，carry代表的是进位
int sum = 0,carry;
while(sum2 != 0){
//这里的num1^num2得到的正是两者相加，不带进位的结果
//首轮结果 010010^100111 = 110101
sum = num1^num2;
//carry代表的进位 (010010&100111) <<1= (000010)<<1 = (000100),在这里刚好进位了
carry = (num1&num2)<<1;
//这里替换掉num1,num2是为了方便迭代，当carry为0,即无进位结束循环
num1 = sum;
sum2 = carry;
}
return sum;
}1234567891011121314151617二进制减法
二进制的减法跟简单，其实就是在加法的基础上进行改进，众所周知，在计算机中一切都是在做加法，减法的由来就是一个数加上另外一个数的负数。计算机中的负数可以采用补码+1的形式得到
tip: 取反（~）得到补码: a的补码为~a。
代码清单 2.
public int sub(int num1,int num2){
return add(num1,add(~num2,1));
}123二进制乘法
乘法有个特性就是，当你乘一个数的时候，你会左移它所出现的位置步，比如：10110010那么就会左移动1位，10111000左移3位，利用好这个特性我们就可以对一个数进行拆分了，保留每一位上面的1，其余的都变成0。
在这里需要用到几个辅助的位操作：1. -n = ~(n-1) = ~n+12. n&~(n-1)，获取n中二进制中的最后一个13. n&(n-1)，去掉n中二进制中的最后一个1
代码清单3.
public int multiply(int a,int b) {
//利用map存放需要移动的位数，以及1向左移动i位的值
//用于快速缓存移动的位数，将移位的值->移位位数进行mapping
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<32;i++) {
map.put(1<<i, i);
}
int sum = 0;
while(b>0) {
int last = b&(~(b-1));//取得最后一个1;
int count = map.get(last);//取得移动的位数
sum = add(sum,a<<count);
b = b&(b-1); //去掉最后一个1;
}
return sum;
}12345678910111213141516二进制除法
二进制的除法可以利用移位跟加减法进行计算。思路如下：先对除数进行移位操作，移位到一个临界值，即比被除数小的最大值，再用除数进行迭代相减，有点类似辗转相除法。
代码清代4.
public int div(int a,int b) {
if(a<b) {
return 0;
}
int bleft = 0; //b左移的位数
//迭代获取除数达到临界值需要移动的位数
while((bleft <<msb)<a) {
bleft ++;
}
int res = 0;//商
for(int i=bleft ;i>=0;i--) {
//每次进行检验，如果当除数移位后，大于被除数，跳过这次循环
if((b<<i)>a) continue;
//这里记录移位的结果集，当i满足的时候即为1不满足即为0
res |= (1<<i);
//缩小被除数的范围。
a = sub(a,b<<i);
}
return res;
}1234567891011121314151617181920 下面贴张图，应该就很好理解了。满足为1，不满足上0
POW的实现
在这里不使用的循环的原因是，那样太需要计算很多次，这里的temp用于保存上次的记录的结果，直接拿出来用，避免的了重复的计算，我们一次分为奇偶来讨论，如 x^4 可以拆分为
x^2*x^2 => x^(y/2)，而奇数的话，我们可以用上次保存的偶数乘以x得到。代码如下：
public int pow(int x,int y) {
if(y == 1) return x;
int result = 0;
int temp = pow(x,y/2);
//y&1 可以验证奇偶 当y的二进制末尾不存在1即为偶数
if((y&1) != 0) {//奇数
result = x*temp*temp;
}else {//偶数
result = temp*temp;
}
return result;
}123456789101112总结
全部代码清单
public class Arithmetic {
public static void main(String[] args) {
Arithmetic atri = new Arithmetic();
System.out.println(atri.add(1, 2));
System.out.println(atri.multiply(2, 3));
System.out.println(atri.div(6, 3));
}
/**
* a+b => 1111 + 1011 不带进位的相加 加上进位
* @param a
* @param b
* @return
*/
public int add(int a,int b) {
if(b==0) {
return a;
}
if(a == 0) {
return b;
}
int sum=0,carry;//carry代表进位
while(b!=0) {
sum = a^b; //不带进位的相加
carry = (a&b)<<1; //进位
a = sum;
b = carry;
}
return sum;
}
//取数值的相反数 用补码+1 得到相反数
public int negative(int a) {
return add(~a,1);
}
public int sub(int a,int b) {
return add(negative(b),a);
}
public int multiply(int a,int b) {
//利用map存放需要移动的位数，以及1向左移动i位的值
Map<Integer,Integer> map = new HashMap<>();
for(int i=0;i<32;i++) {
map.put(1<<i, i);
}
int sum = 0;
while(b>0) {
int last = b&(~(b-1));//取得最后一个1;
int count = map.get(last);//取得移动的位数
sum = add(sum,a<<count);
b = b&(b-1); //去掉最后一个1;
}
return sum;
}
public int div(int a,int b) {
if(a<b) {
return 0;
}
int bleft = 0;
while((b<<bleft)<a) {
bleft++;
}
int res = 0;
for(int i=bleft;i>=0;i--) {
if((b<<i)>a) continue;
res |= (1<<i);
a = sub(a,b<<i);
}
return res;
}
}位运算应用口诀 清零取反要用与，某位置一可用或
若要取反和交换，轻 轻松松用异或
移位运算
要点 1 它们都是双目运算符，两个运算分量都是整形，结果也是整形。
2 “<<” 左移：右边空出的位上补0，左边的位将从字头挤掉，其值相当于乘2。
3 “>>”右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统。
4 “>>>”运算符，右边的位被挤掉，对于左边移出的空位一概补上0。
位运算符的应用 (源操作数s 掩码mask)
(1) 按位与– &
1 清零特定位 (mask中特定位置0，其它位为1，s=s&mask)
2 取某数中指定位 (mask中特定位置1，其它位为0，s=s&mask)
(2) 按位或– |
常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0 s=s|mask)
(3) 位异或– ^
1 使特定位的值取反 (mask中特定位置1，其它位为0 s=s^mask)
2 不引入第三变量，交换两个变量的值 (设 a=a1,b=b1)
目标 操作 操作后状态
a=a1^b1 a=a^b a=a1^b1,b=b1
b=a1^b1^b1 b=a^b a=a1^b1,b=a1
a=b1^a1^a1 a=a^b a=b1,b=a1
二进制补码运算公式：
-x = ~x + 1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x – ~y – 1 = (x|y)+(x&y)
x-y = x + ~y + 1 = (x|~y)-(~x&y)
x^y = (x|y)-(x&y)
x|y = (x&~y)+y
x&y = (~x|y)-~x
x==y: ~(x-y|y-x)
x!=y: x-y|y-x
x< y: (x-y)^((x^y)&((x-y)^x))
x<=y: (x|~y)&((x^y)|~(y-x))
x< y: (~x&y)|((~x|y)&(x-y))//无符号x,y比较
x<=y: (~x|y)&((x^y)|~(y-x))//无符号x,y比较
应用举例
(1) 判断int型变量a是奇数还是偶数
a&1 = 0 偶数
a&1 = 1 奇数
(2) 取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1
(3) 将int型变量a的第k位清0，即a=a&~(1<<k)
(4) 将int型变量a的第k位置1， 即a=a|(1<<k)
(5) int型变量循环左移k次，即a=a<<k|a>>16-k (设sizeof(int)=16)
(6) int型变量a循环右移k次，即a=a>>k|a<<16-k (设sizeof(int)=16)
(7) 整数的平均值
对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法：
int average(int x, int y)
//返回X,Y 的平均值
{
return (x&y)+((x^y)>>1);
}
(8)判断一个整数是不是2的幂,对于一个数 x >= 0，判断他是不是2的幂
boolean power2(int x)
{
return ((x&(x-1))==0)&&(x!=0)；
}
(9)不用 temp交换两个整数
void swap(int x , int y)
{
x ^= y;
y ^= x;
x ^= y;
}
(10) 计算绝对值
int abs( int x )
{
int y ;
y = x >> 31 ;
return (x^y)-y ; //or: (x+y)^y
}
(11) 取模运算转化成位运算 (在不产生溢出的情况下)
a % (2^n) 等价于 a & (2^n – 1)
(12)乘法运算转化成位运算 (在不产生溢出的情况下)
a * (2^n) 等价于 a<< n
(13)除法运算转化成位运算 (在不产生溢出的情况下)
a / (2^n) 等价于 a>> n
例: 12/8 == 12>>3
(14) a % 2 等价于 a & 1
(15) if (x == a) x= b;
else x= a;
等价于 x= a ^ b ^ x;
(16) x 的 相反数 表示为 (~x+1)