位运算四则运算
一、位运算简介
我们先来熟悉下位运算的操作,大致要用到的位运算如下:
与(&)操作
,该操作先将数值转换为二进制(如: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+1
2. 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)