java中的位运算

雨点打透心脏的1/2处 2021-10-31 15:54 328阅读 0赞

java中的位运算主要有**移位运算**和**逻辑运算**

**1. 移位运算**

1.  左移：操作符为<<，向左移动，右边的低位补0，左边高位舍弃，将二进制看做整数，左移1位就相当于乘以2。
2.  无符号右移：操作符为>>>，向右移动，右边的舍弃掉，左边补0。
3.  有符号右移：操作符为>>，向右移动，右边的舍弃掉，左边补的值取决于原来最高位，原来是1就补1，原来是0就补0，将二进制看做整数，右移1位相当于除以2

**2. 逻辑运算**

按位与 &：两位都为1才为1  
按位或 |：只要有一位为1，就为1  
按位取反 ~： 1变为0，0变为1  
按位异或 ^ ：相异为真，相同为假

*  ***应用场景1***：可通过与1进行按位与&运算判断奇偶性  
    奇数都不是2的整数倍，转换成二进制后最低位必然为1，偶数则相反。

int i = 1;	// 二进制存储方式为00000000 00000000 00000000 00000001
        int j = 5;	// 二进制存储方式为00000000 00000000 00000000 00000101
        int k = 6;	// 二进制存储方式为00000000 00000000 00000000 00000110
        if ((i & j) == 1) {
          System.out.println("j的最低位为1，为奇数");
        }
        if ((i & k) == 0) {
          System.out.println("k的最低位为0，为偶数");
        }

*  ***应用场景2***：判断一个正整数是不是2的整数次幂  
    我们先来看一下常见的2的整数次幂的数：2、4、8、16，转化成二进制依次为：10、100、1000、10000 ，规律是除了首位是1，其他全是0。恰巧这些数减去1后等于他们依次按位取反的结果，比如8-1=7，二进制是0111，可以通过8的二进制1000按位取反得到。而8&7=0，提取一下规律就是：

n&(n-1)==0

*  ***应用场景3***——按位与&代替取模运算%  
    a % b == a & (b - 1) 前提：b 为 2^n
 *  ***应用场景4***——不用加减乘除的加法运算  
    三步走策略：

1.  每一位相加不计算进位  
    （ 异或运算相当于不进位的加法运算，如：0^ 1=1，1^ 0=1，0^ 0=0，1^1=0.因此用异或执行此步）
2.  记下进位  
    （二进制加只有1，1才会产生进位，与&性质一样，1&1=1，然后再左移1位来表示进位，1<<1=10）
3.  将前两步结果执行1，2两步，直到没有进位为止  
    以5，17为例：  
    5的二进制101，17二进制10001，  
    执行第一步：101^ 10001=10100；  
    执行第二步：(101^ 10001)<<1=00010；  
    执行第三步：10100^ 00010=10110；10100&00010=00000；循环结束，返回10110=22。

public int add(int a, int b) {
            int sum=0;
            int carry=0;
            do {
                sum=a^b;  //不进位的加法
                carry=(a&b)<<1;  //求进位
                a=sum;
                b=carry;
            }while(carry!=0);
            return sum;
        }

*  ***应用场景5***—— HashMap 中的 indexFor 方法：

static int indexFor(int h,int length){
    	return h & (length-1);
     }

这个方法是使用哈希值对链表数组的长度取模，得到值所在的索引位置，里面使用位运算（&）代替普通的（%）运算。

原理：  
假设n=3，则 2^ 3 = 8，表示成 2 进制就是 1000；而2^3 - 1 = 7 ，即 0111。

*  对于按位与&运算， X & (2^3 - 1) 就相当于取 X 的 2 进制的最后三位数。
 *  对于整除/与求模运算%，X / 8 相当于 X >> 3，即把 X 右移 3 位，而被移掉的后三位，则是 X % 8的值，也就是余数。因此X & (2^3 - 1) =X % (2^3)。

**总结：X / 2^n = X >> n，那么 X & (2^n - 1) = X % 2^n。**

参考链接：  
https://www.cnblogs.com/JackPn/p/9379617.html