重庆智能网站建设设计,洛阳搜索引擎优化,小程序源码带后台,可以做海报的网站按位异或#xff1a;相同为0#xff0c;不同为1
异或运算性质
1#xff09;异或运算就是无进位相加#xff08;ab写二进制形式每位相加时不进位#xff09;
2#xff09;异或运算满足交换律、结合律#xff0c;也就是同一批数字#xff0c;不管异或顺序是什么#…按位异或相同为0不同为1
异或运算性质
1异或运算就是无进位相加ab写二进制形式每位相加时不进位
2异或运算满足交换律、结合律也就是同一批数字不管异或顺序是什么最终的结果都是一个
30^nnn^n0原来是0还是0原来是1无进位想加还是0
4整体异或和如果是x整体中某个部分的异或和如果是y那么剩下部分的异或和是x^y
应用不借助中间变量交换ab的值
aa^b;
ba^b;
aa^b; 弊端尤其进行数组下标交换时要保证指针位置不能相同指向的数的值可以相同
arr[i]i^j;arr[j]i^j;arr[i]i^j; 前提ij
数组中1种数出现了奇数次其他的数都出现了偶数次返回出现了奇数次的数
出现了偶数次的数与eor异或结果还是eor
怎么把一个int类型的数提取出最右侧的1来
~a把a打散盯着最右侧的1,1自身变0左右两侧均取反
~a1最右侧的1左边的数字没变右边使得盯着的1由还原
~a1-a 数组中有2种数出现了奇数次其他的数都出现了偶数次找到并打印这两种数
public class Code02_EvenTimesOddTimes {// arr中只有一种数出现奇数次public static void printOddTimesNum1(int[] arr) {int eor 0;for (int i 0; i arr.length; i) {eor ^ arr[i];}System.out.println(eor);}// arr中有两种数出现奇数次public static void printOddTimesNum2(int[] arr) {int eor 0;for (int i 0; i arr.length; i) {eor ^ arr[i];}// a 和 b是两种数// eor ! 0// eor最右侧的1提取出来// eor : 00110010110111000// rightOne :00000000000001000int rightOne eor (-eor); // 提取出最右的1int onlyOne 0; // eorfor (int i 0 ; i arr.length;i) {// arr[1] 111100011110000// rightOne 000000000010000if ((arr[i] rightOne) ! 0) {onlyOne ^ arr[i];}}System.out.println(onlyOne (eor ^ onlyOne));}public static int bit1counts(int N) {int count 0;// 011011010000// 000000010000 1// 011011000000// while(N ! 0) {int rightOne N ((~N) 1);count;N ^ rightOne;// N - rightOne}return count;}public static void main(String[] args) {int a 5;int b 7;a a ^ b;b a ^ b;a a ^ b;System.out.println(a);System.out.println(b);int[] arr1 { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };printOddTimesNum1(arr1);int[] arr2 { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };printOddTimesNum2(arr2);}}假设ab这两个数出现了奇数次拿eor^整个数组得到eora^b而ab说明eor0说明eor某一位必然有1不妨取最右边的1然后根据这个1对原数组进行分类一类这一位上有1另一类没有假设a这一位上有1b没有定义eor·异或上a所在的那一类那一类只有a出现了奇数次所以eor·a然后eor·在异或eor得到b 一个数组中有一种数出现了k次其他数字都出现了m次m1,km,找到出现了k次的数
package class02;import java.util.HashMap;
import java.util.HashSet;public class Code03_KM {public static int test(int[] arr, int k, int m) {HashMapInteger, Integer map new HashMap();for (int num : arr) {if (map.containsKey(num)) {map.put(num, map.get(num) 1);} else {map.put(num, 1);}}for (int num : map.keySet()) {if (map.get(num) k) {return num;}}return -1;}public static HashMapInteger, Integer map new HashMap();// 请保证arr中只有一种数出现了K次其他数都出现了M次public static int onlyKTimes(int[] arr, int k, int m) {if (map.size() 0) {mapCreater(map);}int[] t new int[32];// t[0] 0位置的1出现了几个// t[i] i位置的1出现了几个for (int num : arr) {while (num ! 0) {int rightOne num (-num);t[map.get(rightOne)];num ^ rightOne;}}int ans 0;for (int i 0; i 32; i) {if (t[i] % m ! 0) {if (t[i] % m k) {ans | (1 i);} else {return -1;}}}if (ans 0) {int count 0;for (int num : arr) {if (num 0) {count;}}if (count ! k) {return -1;}}return ans;}public static void mapCreater(HashMapInteger, Integer map) {int value 1;for (int i 0; i 32; i) {map.put(value, i);value 1;}}public static int[] randomArray(int maxKinds, int range, int k, int m) {int ktimeNum randomNumber(range);// 真命天子出现的次数int times Math.random() 0.5 ? k : ((int) (Math.random() * (m - 1)) 1);// 2int numKinds (int) (Math.random() * maxKinds) 2;// k * 1 (numKinds - 1) * mint[] arr new int[times (numKinds - 1) * m];int index 0;for (; index times; index) {arr[index] ktimeNum;}numKinds--;HashSetInteger set new HashSet();set.add(ktimeNum);while (numKinds ! 0) {int curNum 0;do {curNum randomNumber(range);} while (set.contains(curNum));set.add(curNum);numKinds--;for (int i 0; i m; i) {arr[index] curNum;}}// arr 填好了for (int i 0; i arr.length; i) {// i 位置的数我想随机和j位置的数做交换int j (int) (Math.random() * arr.length);// 0 ~ N-1int tmp arr[i];arr[i] arr[j];arr[j] tmp;}return arr;}// [-range, range]public static int randomNumber(int range) {return ((int) (Math.random() * range) 1) - ((int) (Math.random() * range) 1);}public static void main(String[] args) {int kinds 5;int range 30;int testTime 100000;int max 9;System.out.println(测试开始);for (int i 0; i testTime; i) {int a (int) (Math.random() * max) 1; // a 1 ~ 9int b (int) (Math.random() * max) 1; // b 1 ~ 9int k Math.min(a, b);int m Math.max(a, b);// k mif (k m) {m;}int[] arr randomArray(kinds, range, k, m);int ans1 test(arr, k, m);int ans2 onlyKTimes(arr, k, m);if (ans1 ! ans2) {System.out.println(ans1);System.out.println(ans2);System.out.println(出错了);}}System.out.println(测试结束);}}
