位运算
计算机中的数以二进制的形式存在,位运算就是对二进制数位进行操作,执行效率很高
机器语言就是位运算
运算符
与 &
或 |
取反 ~
异或 ^
左移 <<(相当于 ×2,低位补0,高位舍去)
右移 >>(相当于 ÷2,低位舍去,高位补0)
负数
计算机中运算使用二进制补码,正数补码是本身,负数补码符号位不变,其余按位取反,最后+1
eg:快速判断i是否等于-1可以直接使用~i,因为-1补码为11111111,取反后就是00000000,即0
位运算的加减乘除
加法
设两个数为x,y
- 各位对齐异或得x
- 各位相与得y
- 若y$\neq$;0,则回到1步骤;若y=0
减法
由于计算机只进行加法,可以采用一个数加一个负数
eg:13-6 = 13+(-6)
乘法
转换为乘数倍的被乘数相加,对于正负号可以采用绝对值计算,最后单独确定正负号,同号为正异号为负
除法
转换为用除数去减被除数,直到被除数小于除数,此时所减次数为商,被除数为余数,正负号同乘法
位运算高级使用
特殊乘除法
对于乘除数为2的n次方时,可以采用左移右移n位的方式快速计算
交换两个整数值
以前采用的是设置过渡变量,现在学习了位运算中的异或可以采用它的特殊性质:x^0=x,x^x=0
对于a,b两个值
a ^= b
b ^= a
a ^= b
原理:a=a^b,b=b^a=b^(a^b)=a,a=a^b=a^(a^b)=b
判断奇偶
取最后一位,若为1则奇数,若为0则偶数
即判断a&1