异或运算 ^ 是位运算中的一种它的规则很简单二进制位相同为 0不同为 1​0 ^ 0 0​0 ^ 1 1​1 ^ 0 1​1 ^ 1 0因此在十进制中有四个重要性质:1.任何数与0异或结果为本身。2.任何数与其本身异或结果为0。3.异或运算满足交换率。4.异或运算满足结合律。即:交换律a ^ b b ^ a​结合律(a ^ b) ^ c a ^ (b ^ c)​自反性a ^ a 0​恒等性a ^ 0 a可以利用其特性实现一些算法:问题 1找出数组中唯一出现一次的数字(单身狗问题)给定一个非空整数数组其中只有一个元素出现一次其余元素均出现两次。请找出这个只出现一次的元素。输入 nums [2, 3, 2, 4, 4]​输出 3思路:先定义一个result0然后分别与每一位异或运算。由于0^2^3^2^4^4 0^(2^2)^(4^4)^3 0^0^0^3 3可以得到只出现一次的数字。int singleNumber(int* nums, int numsSize) {int x 0;for (int i 0; i numsSize; i) {x ^ nums[i];}return x;}问题 2找出 0 到 n 之间缺失的数字给定一个数组它包含 0 到 n 之间的所有数字但恰好缺失了一个。请找出这个缺失的数字。输入 nums [9, 6, 4, 2, 3, 5, 7, 0, 1]​输出 8思路:先令x为0^1^2^3^4^5^6^7^8^9然后x再与nums中的元素分别异或。int missingNumber(int* nums, int numsSize) {int x 0;for (int i 0; i numsSize; i) {x ^ i;}for (int i 0; i numsSize; i) {x ^ nums[i];}return x;}问题三:双单身狗问题给定一个非空整数数组其中有且仅有两个元素出现一次其余元素均出现两次。请找出这两个只出现一次的元素。输入 nums [1, 2, 1, 3, 2, 5]输出 [3, 5]思路:如果仍按照上述思想全部异或运算最后的答案是3^56那么我们可以考虑:根据3^5的性质把nums分为两组而3和5正好被分开就可以分而治之。把6转换为二进制:110它是怎么来的011(3)^101(5)------110(6)发现:当6的二进制为1的那一位3和5对应的二进制该位的数不同。由此可以分为两类。比如我们取中间那位。看nums中所有元素:数字 二进制 倒数第二位1 001 02 010 11 001 03 011 12 010 15 101 0中间位为0的: 1 1 5中间位为1的: 2 2 3则可以分开求取。int* singleNumber(int* nums, int numsSize, int* returnSize) {// 1. 整体异或得到 a ^ bint xor_all 0;for (int i 0; i numsSize; i) {xor_all ^ nums[i];}// 2. 找到区分位a和b不同的最低位// 技巧xor_all -xor_all 得到最低位的1int diff_bit xor_all (-xor_all);// 3. 根据diff_bit分组并异或int num1 0, num2 0;for (int i 0; i numsSize; i) {// 注意在C语言中按位与的结果是0或非0if (nums[i] diff_bit) {num1 ^ nums[i]; // 这一位为1的组} else {num2 ^ nums[i]; // 这一位为0的组}}// 4. 返回结果int* result (int*)malloc(2 * sizeof(int));if (result NULL) {*returnSize 0;return NULL;}result[0] num1;result[1] num2;*returnSize 2;return result;}