&按位与
只有1&1= 1
有0一定为0。
- n&n-1 可是使得n最靠后的1变成0,其他位置不变。
- 在快速幂这种,比较个位数与1。如1001 & 1。当个位是1的时候输出1。
|按位或
只有 0|0 = 0
可活用在让一个数据的某些位置变1。
^按位异或
0^0=0; 0^1=1; 1^0=1; 1^1=0;
三个性质
- 0^X = X; X^X =0
- 交换律 :a^b = b^a
- 结合律:a^b^c = a^(b^c)
使特定位置翻转。例:X=10101110,使X低4位翻转,用X ^ 0000 1111 = 1010 0001即可得到。
~取反
~1=0; ~0=1;
使一个数的最低位为零,可以表示为:a&~1。
~1的值为1111111111111110,再按“与”运算,最低位一定为0。
<< 左移运算符
相当于*2。
>>右移运算符
相当于/2。
>>> 和 <<< 无符号整数的右移和左移运算符
就是无视符号位,把符号位当成数值位移动。
计算机中表达数都是用有符号整数,所以当做到无符号整数的题目时,移动一定要用这两运算符。
1,应用算法
快速幂
计算x的n次方的时候,常见方法是x乘n次,这种方法的时间复杂度是0(n)。
而快速幂是利用了位运算,比如2的10次方,将10转换成1001,为1的时候要乘以权重,这样只要乘3次。
快速幂的时间复杂度为0(logn)。
1,题目
2,解法
class Solution {
public double myPow(double x, int n) {
if(x == 0 || n == 0 || x==1)
return 1;
long cur = n;
if( cur<0 ){
x = 1/x;
cur = -cur;
}
double ans = 1.0;
while(cur>0){
if((cur & 1) == 1){
ans *= x;
}
x *= x;
cur>>=1;
}
return ans;
}
}
需要注意n等于-(2的32次方)。如果没有将n转成long型的话,直接-n就会大于int的最大值(2的32次方-1)。
位运算需要修改符号的,最好还是换成大的整数结构。
如
public int myPow(double x, int n) {
int a = -2147483648;
return -a;
}
最后结果本应该为2147483648,但是给出的结果是a,溢出就没有处理。
正文完