首页 » 位运算技巧整理

位运算技巧整理

位运算技巧整理

基础

异或^

两个操作数的位中，相同则结果为0，不同则结果为1。

与&

两个数都转为二进制，然后从高位开始比较，如果两个数都为1则为1，否则为0。

或|

两个数都转为二进制，然后从高位开始比较，两个数只要有一个为1则为1，否则就为0。

非~

如果位为0，结果是1，如果位为1，结果是0.

对数组异或操作，结果值与数组中的数字顺序无关

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
        int[] array = {6,5,3,2,4,1};
        int v = 0;
        for (int i = 0;i < array.length;i++) {
            v ^= array&#91;i&#93;;
        }
        System.out.println("数组异或值是:" + v);
}
 
&#91;/java&#93;
如果一个数组中所有数字都出现了偶数次，只有一个数字出现了一次。可以利用一个数和0异或还是自己，一个数和自己异或是0的原理，快速找到只出现一次的数字。
 
<h2> 取余数</h2>
如果一个数是2的正数次幂。另外一些数和这个数相除，取余数。
 
public static void main(String[] args) {
        int num = 123;
        int len = 32;
        int n = num % len;
        int m = num & (len - 1);
        System.out.println("m="+ m +",n="+n);

十进制转二进制

给定的数循环除以2，直到商为0或者1为止。将每一步除的结果的余数记录下来，然后反过来就得到相应的二进制了。计算机内部表示数的字节长度是固定的，比如8位，16位，32位。所以在高位补齐，java中字节码是8位的，所以高位补齐就是00001000.

1
2
3
4
5
6
7
8
9
10
11
public static String toBinary(int num) {
        String str = "";
        while(true) {
            str = num % 2 + str;
            num /= 2;
            if (num == 0) {
                break;
            }
        }
        return str;
}

二进制转十进制

去掉高位，然后从个位开始计算2的幂（个位是0），乘以对应位数上的数字。然后，把得到的数值相加。
如，8 的二进制位是 00001000。则二进制转十进制数：

1
（2的0次幂）*0+（2的1次幂）*0+（2的2次幂）*0+（2的3次幂）*1 = 8