异或运算
相同为0，不同为1，相当于无进位相加
0 ^ N = N
N ^ N = 0
异或运算满足交换律和结合律
一、打印一个数的二进制
题目
打印一个数的二进制
代码
package bitoperation;public class PrintBinary {public static void printBinary(int num) {for (int i = 32; i > 0; i--) {System.out.print((num & (1 << i)) == 0 ? '0' : '1');}}
}二、用位运算实现+ - * /
题目
用位运算实现+ - * /
代码
package class05;// 测试链接：https://leetcode.com/problems/divide-two-integers
public class Code03_BitAddMinusMultiDiv {public static int add(int a, int b) {int sum = a;while (b != 0) {sum = a ^ b;b = (a & b) << 1;a = sum;}return sum;}public static int negNum(int n) {return add(~n, 1);}public static int minus(int a, int b) {return add(a, negNum(b));}public static int multi(int a, int b) {int res = 0;while (b != 0) {if ((b & 1) != 0) {res = add(res, a);}a <<= 1;b >>>= 1;}return res;}public static boolean isNeg(int n) {return n < 0;}public static int div(int a, int b) {int x = isNeg(a) ? negNum(a) : a;int y = isNeg(b) ? negNum(b) : b;int res = 0;for (int i = 30; i >= 0; i = minus(i, 1)) {if ((x >> i) >= y) {res |= (1 << i);x = minus(x, y << i);}}return isNeg(a) ^ isNeg(b) ? negNum(res) : res;}public static int divide(int a, int b) {if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {return 1;} else if (b == Integer.MIN_VALUE) {return 0;} else if (a == Integer.MIN_VALUE) {if (b == negNum(1)) {return Integer.MAX_VALUE;} else {int c = div(add(a, 1), b);return add(c, div(minus(a, multi(c, b)), b));}} else {return div(a, b);}}
}三、不用中间变量交换俩个数的值
题目
不用中间变量交换俩个数的值
代码
package bitoperation;public class SwapTwoNum {public void swapTwoNum(int num1, int num2) {//设num1 = x,num2 = y//则num1 = x ^ ynum1 = num1 ^ num2;//则num2 = x ^ y ^ y = xnum2 = num1 ^ num2;//则num1 = x ^ y ^ x = ynum1 = num1 ^ num2;}
}四、找到出现奇数次的数
题目
在一个数组中，有一个数出现了奇数次，其他数都出现了偶数次，找出这个数
代码
package bitoperation;public class EvenTimesOddTimes {public int evenTimesOddTimes(int[] arr) {int num = 0;for (int i = 0; i < arr.length; i++) {num ^= arr[i];}return num;}
}原理
0 ^ N = N
N ^ N = 0
异或运算满足交换律和结合律
五、找到一个数二进制形式的最右边的1
题目
给定一个int类型的数，找到这个数二进制形式的最右边的1，并返回只有这位上有1其他位上为0的二进制对应的十进制数
代码
package bitoperation;public class FindRightOne {public int findRightOne(int num) {return num & (-num);}
}
六、找到数组中出现过奇数次的两个数
题目
一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
代码
package bitoperation;public class _6FindTwoNum {public void findTwoNum(int[] arr) {int num = 0;for (int i = 0; i < arr.length; i++) {num ^= arr[i];}//假设求得两个数为a和b//num现在等于 a ^ b//找到num最右边的1//此位上a和b必定有一个为1，一个不为1，a和b等价，假设a为1int one = num & (-num);int num2 = 0;for (int i = 0; i < arr.length; i++) {if ((arr[i] & one) != 0) {num2 ^= arr[i];}//得到的是a最右边的1的位数相等的所有数异或操作//右因为其它数都是出现过偶数次//所以num2 = aint b = num ^ num2;System.out.println(num2 + " " + b);}}
}七、找到出现了K次的数
题目
在一个数组中，一个数出现了K次，其它数都是出现了M次，0<K<M，现给出数组和M，请返回出现了K次的数的值
代码
package bitoperation;public class _7KM {public int km(int[] arr, int K, int M) {int[] myarr = new int[32];for (int i = 0; i < arr.length; i++) {for (int j = 0; j < 32; j++) {//如果arr的第0位的数的二进制的第j位为1，则记录在myarr[j]中myarr[j] += (arr[i] >> j) & 1;//相当于//if ((myarr[i] & (1 << j)) != 0) {// myarr[i]++;//}}}int num = 0;for (int i = 0; i < 32; i++) {if (myarr[i] % M != 0) {num |= (1 << i);}}return num;}
}
