算法(十) 位运算

&按位与

只有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，溢出就没有处理。