Java 位运算

Java使用补码来表示二进制数, 在计算机运算的时候, 都是以补码的方式来运算。在补码表示中,最高位为符号位,正数的符号位为0,负数为1。补码的规定如下:
　　· 对正数来说,最高位为0,其余各位代表数值本身(以二进制表示)。正数的原码、反码、补码都一样。
　　· 对负数而言,把该数绝对值的补码按位取反,然后对整个数加1,即得该数的补码。以下是-1补码的计算过程：

　　10000000000000000000000000000001 （-1的原码）
　　11111111111111111111111111111110 （-1的反码：原码除符号位按位取反）
　　11111111111111111111111111111111 （-1的补码：反码加1）

一、位运算的概念

　　位运算表达式由操作数和位运算符组成，实现对整数类型的二进制数进行位运算。

　　位运算符可以分为逻辑运算符(包括~、＆、|和^)及移位运算符(包括>>、<<和>>>)。

　　　　&（与）：当两边操作数的位同时为1时，结果为1，否则为0。如1100&1010=1000
　　　　| （或）：当两边操作数的位有一边为1时，结果为1，否则为0。如1100|1010=1110
　　　　~（非）：0变1,1变0。如 ~1100=0011
　　　　^（异或）：两边的位不同时，结果为1，否则为0。如1100^1010=0110
　　　　<<（左移）：a向左移动b指定的位数（在低位补0）。表示原来的值乘2。（a<<b, a表示运算符左侧的运算对象，b表示右侧的数值）
　　　　>>（右移）：a向右移动b指定的位数。若值为正，则在高位插入0；若值为负，则在高位插入1。
　　　　>>>（无符号右移）：a向右移动b指定的位数。无论正负，都在高位插入0。这一运算符是C或C++没有的。

　　位运算符的优先级：~的优先级最高，其次是<<、>>和>>>，再次是＆，然后是^，优先级最低的是|。

public class Test {
    
    public static void main(String[] args) {
        Integer a = Integer.MAX_VALUE;
        Integer b = Integer.MIN_VALUE;
        toBinary("(MAX_INT) a", a);
        toBinary("(MIN_INT) b", b);
        toBinary("~ b", ~b);
        toBinary("a & b", a & b);
        toBinary("a | b", a | b);
        toBinary("a ^ b", a ^ b);    
        toBinary("b << 2", b << 2);    
        toBinary("b >> 2", b >> 2);    
        toBinary("b >>> 2", b >>> 2);    
    }
    
    public static void toBinary(String op, Integer a) {
        String str = Integer.toBinaryString(a);
        System.out.printf("%n%11s: ", op);
        for(int i = 0, delta = 32 - str.length(); i < 32; i++){
            if(i < delta)
                System.out.print("0");
            else
                System.out.print(str.charAt(i - delta));
            if((i + 1) % 8 ==0)
                System.out.print(" ");
        }
    }
}

运行结果

二、位运算的应用

1. m*2^n

　　3*2^5 : (3<<5))

　　法则一：任何数左移（右移）32的倍数位等于该数本身。

　　法则二：在位移运算m<<n的计算中，若n为正数，则实际移动的位数为n%32，若n为负数，则实际移动的位数为(32+n%32)，右移，同理。

2. 判断一个数n的奇偶性

　　n&1 == 1? "奇数" : "偶数"

　　int类型的1前31位都是0，最低位为1，当一个数为奇数，其最低位也是1。

3. 不用临时变量交换两个数

异或没有顺序性，且满足以下规则：

　　① a ^ a =0
　　② a ^ b =b ^ a
　　③ a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;
　　④ d = a ^b ^ c 可以推出 a = d ^ b ^ c.
　　⑤ a ^ b ^a = b.

根据第五个规则，可以交换变量值。

public class Test {
    
    public static void main(String[] args) {
        int a = 4;
        int b = 10;
        a = a ^ b;
        b = a ^ b;
        a = a ^ b;
        System.out.println("a=" + a + ", b=" + b);
    }
}

运行结果: a=10, b=4

计算过程如下：

a = a ^ b
　b = a ^ b = (a ^ b) ^ b = a
　a = a ^ b = (a ^ b) ^ a = b

4. 计算散列码

　　HashMap中在使用put函数插入值，会先计算当前元素的hash值，来计算该元素在hashtable中的存储位置。

int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12); 
int h = hash ^ (hash >>> 7) ^ (hash >>> 4);

　　散列的本意就是要尽量均匀分布，经过上面的计算，可以把“1”变的均匀一点：

　　before：12539 = 00000000 00000000 00110000 11111011
　　 after：13206 = 00000000 00000000 00110011 10010110