1、0 ^ N == N, N ^ N==0 2、异或运算满足交换律和结合律
int a == 甲; int b = 乙;
a = a ^ b;
b = a ^ b;
a = a ^ b;
把上面代码分为三个步骤 第一步: a = a ^ b; 此步骤过后 a = 甲 ^乙;b = 乙; 第二步: b = a ^ b; 此步骤过后 a = a ^ b = 甲 ^ 乙;b = a ^ b = 甲 ^ 乙 ^ 乙 = 甲; 第三步: a = a ^ b; 此步骤过后b = 甲; a = a ^ b = 甲 ^ 乙 ^ 甲 = 乙; 完成交换 注意:两个交换的数不能指向相同内存!!!
方法:遍历数组所有元素,一直异或。因为两个相同的数异或为0,所以异或到最后的数就是出现奇数次的数。
public static void printOddNumber1(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++){
eor = eor ^ arr[i];
}
System.out.println(eor)
}
例如:输入1001……01000 输出0000……01000 方法:加入输入的为N,这输出为 N & (~N + 1) 步骤: 输入:1001……01000 取反:0110……10111 再加一:0110……11000 相与:0000……01000
思路: 1、按照题目2的方法,全部的数一起异或,得到eor = a ^ b 2、按照题目3的方法,提取eor最右边1(其实任意一个一都行,因为值为1的地方表示两个数在该位不同),根据这个位是否为1,将数组分为A、B两部分。 3、对A部分的数进行一起进行异或运算,得到数1,将数1与eor异或得到数2
public static void printOddNumber(int [] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor = eor ^ arr[i];
}
int rightOne = eor & (~eor + 1);
int numA = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] & eor == 0) {
numA = numA ^ arr[i];
}
}
numB = eor ^ numA;
}
public static int bitCount(int N) {
int count = 0;
while (N != 0){
int rightOne = N & ((~N) + 1);
count++;
N = N ^ rightOne;
}
return count;
}