绝密笔记 | 算法(十) 位运算

&按位与

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

正文完