java 位操作

1、位操作运算符的种类：&（与）、|（或）、~（取反）、^（异或）、<<（左移）、>>（右移）、>>>（无符号右移）。

2、位运算符操作不会短路。

3、位运算符操作的是补码，所以~后正负号会发生变化。

4、位运算符只能用于整型。

5、反码、补码是相对于有符号数而言的，且不改变符号位。无符号数没有反码、补码。

其中移位运算符需要注意的地方：

三个移位运算符的相同点：当移位的位数超出数值的位数则会取模后再移位。

<<（左移）：左移所操作数字的补码，二进制补码整体左移（包括符号位），溢出则舍弃，低位补0。这意味着正数在左移的过程中是可以变成负数的。以Java中int型作为测试，Java中int型为4个字节，所以移位的位数为0~31，用32作为测试。如下

public class Tests{
    public static void main(String[] args) {
        System.out.println(1<<32);　　//结果为1
        System.out.println(8>>33);　　//结果为4
        System.out.println(8>>>33);　　//结果为4
        System.out.println(1<<31);　　//结果为-2147483648
    }
}

由运行结果运行结果可以看出，对32进行了模运算。

但是如果我们一次不进行过长的移位就不会进行模运算，做如下测试

public class Tests{
    public static void main(String[] args) {
        int x = 1<<31;
        int y = 1<<31;
        System.out.println(x);　　//输出为-2147483648
        x = x<<31;
        System.out.println(x);　　//输出为0
        y = y<<1;
        System.out.println(y);　　//输出为0
    }
}

有上面的测试可以验证上述的点。左移操作是没有符号位一说的，直接对补码的整体进行操作。所以也就没有无符号左移<<<这样的运算符。

>>（右移或者说是有符号右移）：右移所操作数字的补码，二进制补码整体右移（包括符号位），舍弃右侧多出部分，高位补符号位。即相当于正数高位补0，负数高位补1。这样的操作对于负数来说，会让二进制数中的1的个数持续增多。但是得到的值是正确的。以整数-1来说。作如下测试。

public class Tests{
    public static void main(String[] args) {
        int x=-1;
        for(int i=0; i<10; i++){
            System.out.println(x>>1);　　//输出永远是-1；
        }
    }
}

在这个测试中-1所对应的原码为，为方便查看简单到8位，-1的原码为1000 0001 补码为1111 1111 所以无论移动多少次，其结果永远是-1。进一步可以以-8作为一个测试。一下完整的32位的-8、-4、-2、-1的原码和补码

-8原码：1000 0000 0000 0000 0000 0000 0000 1000

-8补码：1111 1111 1111 1111 1111 1111 1111 1000

-4补码：1111 1111 1111 1111 1111 1111 1111 1100

-2补码：1111 1111 1111 1111 1111 1111 1111 1110

-1补码：1111 1111 1111 1111 1111 1111 1111 1111

由上述的内容我们可以看出，-8右移一位则除2，补码中的1会多一个。但结果正确。

>>>（无符号右移）：右移做操作数字的补码，高位补0，低位超出则舍弃。由于高位补零，所以一个负数一旦移位则会变成正数。测试如下

public class Tests{
    public static void main(String[] args) {
        System.out.println(-1>>>1);　　//结果为2147483647
    }
}

一下为一些运用

统计十进制数对应的二进制中1的个数（统计的是补码）

public class Tests{
    public static void main(String[] args) {
        int sum = 0;
        int n = -8;
        do{
            sum += n&1;
        }while((n >>>= 1)!=0);
        System.out.println(sum);　　//29　　n取任何数
    }
}

还有一种

public class Tests{
    public static void main(String[] args) {
        int n = -8;
        int sum = 0;
        while(n != 0){
            sum++;
            n = n&(n-1);
        }
        System.out.println(sum);　　//29　　n取任何数
    }
}

下面这种方法对于正数很好理解，就是每次都取n-1的值，这样就会影响最低位的1及其更低位的值，影响的效果为取反，而高位不会影响。每次的循环都会利用&运算将低位的1去除。例如0111 1000，减一的值为0111 0111，&运算后为0111 0000。在负数的情况下，我们可以直接看补码的关系，1111 1000的补码为1000 1000，减一后（注意是负数加相反数）1111 1001的补码为1000 0111，直接看补码间的关系可以看出其实就是去掉符号位后，其余的值当作正数做减一运算与正数情况相同。

负数在变位补码时，只需要确定最低的一位1，比最低的1高的位依次求反（不包括最低位的1）。所以可以看作，在最低的一位1前的数会受影响。这里负数的减一即绝对值加1后，在变为补码，相当于从最低位就影响补码的值。这样可以认为，n（第一个1的高位取反）n-1（全部取反，相对于n）这样的&操作，会使n的最低位1及其更低位变成0。

异或交换元素值

public class Tests{
    public static void main(String[] args) {
        int a=2;
        int b=3;
        a = a^b;
        b = a^b;
        a = a^b;
        System.out.println(a+"   "+b);　　//3　　2
    }
}

快速幂

快速幂的主要思想为，将一个数的幂的指数，表示为二进制的科学计数法形式。

于是我们可以利用a来计算a的平方，再利用a的平方计算a的四次方。于是可以重复利用上一次的结果。二进制是可以表示任何整数的。于是指数就被拆分。简化理解为8421码，当a的5次方就有，0101，于是就有a的0次方乘a的4次方可得到。

public class Tests{
    public static void main(String[] args) {
        int x = 2, n = 5;        //x的n次方
        int ans = 1;    　　　　//保存结果
        while(n!=0){
            if((n&1)==1){
                ans *= x;        //该8421码对应的位是1，就乘进结果
            }
            x *= x;        //计算8421码对应的基数，
            n>>=1;        //准备8421码的下一位
        }
        System.out.println(ans);
    }
}

递归实现

int pow(int m,int n){   //m^n
    if(n==1) return m;
    int temp=pow(m,n/2);
    return (n%2==0 ? 1 : m)*temp*temp;
}

这个递归实现我是这样想的，以a的11次方为例（想成一条11米的绳子）。我们每一层的任务是，判断自己是不是在最后一层，如果不是就把自己的一半分到下一层，让下一层计算，留在自己这一层的要么和下一层一样大，要么就比下一层大一个。下一层计算结束，就把原来的自己还原回来。

java 位操作

推荐阅读