异或运算的性质异或运算的性质

89 阅读 0 评论 59 点赞

我是靠谱客的博主整齐猫咪，最近开发中收集的这篇文章主要介绍异或运算的性质异或运算的性质，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

异或运算的性质

1）0^N == N, N^N == 0
2）异或运算满足交换律和结合率
3）不用额外变量交换两个数
4) 异或就是无进位的相加

int a = A, b = B;
a = a ^ b = A ^ B;
b = a ^ b = (A ^ B) ^ B = A ^ (B ^ B) = A ^ 0 = A；
a = a ^ b = (A ^ B) ^ A = (A ^ A) * B = B;

4）一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到这一个数

public class Main {
public static void printOddTimesNum1(int[] arr) {
int eO = 0;
for (int cur : arr) {
eO ^= cur;
}
System.out.println(eO);
}
}

5）一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数

public class Main {
/**
* 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到这两个数
*/
public static void printOddTimesNum2(int[] arr) {
int eO = 0, eOhasOne = 0;
for (int curNum : arr) {
eO ^= curNum;
}
// 假设 a 和 b 出现了奇数次, 那么 eO = a ^ b
// 因为 a != b, 所以 eO 的二进制中肯定有一位不为0
int rightOne = eO & (~eO + 1); // 提取出最右侧为1的值
for (int cur : arr) {
if ((cur & rightOne) != 0) {
eOhasOne ^= cur;
}
}
System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
}
}

6)给定两个有符号32位整数a和b，返回a和b中较大的。

public class Main {
/**
* x必须为0或者1
*/
public static int flip(int x) {
return x ^ 1;
}
/**
* (x >> 31) & 1获取x的符号位，负数=1 正数=0
* 如果x为正数，最后返回1
* 如果x为负数，最后返回0
*/
public static int sign(int x) {
return flip((x >> 31) & 1);
}
public static int getMax(int a, int b) {
int c = a - b; // 这里有可能会溢出, 因此这里是有问题的
int ac = sign(c); // 如果ac = 1, 则 a > b, ac = 0, 则 a < b
int ab = flip(ac); // 如果ac = 1, 则ab = 0, 如果ac = 0, 则ab = 1
return a * ac + b*ab;
}
public static int getMax2(int a, int b) {
int c = a - b;
int sa = sign(a); // 获取a的符号
int sb = sign(b); // 获取b的符号
int sc = sign(c); // 获取c的符号
int difSab = sa ^ sb; // 如果difSab=1, 说明符号不一样, 如果difSab=0，说明符号一样
int sameSab = flip(difSab);
// difSab与sameSab的关系:difSab=1,sameSab=0或者difSab=0,sameSab=1
/**
* 如果a和b的符号相同(difSab=0), a - b >= 0(sc=1), 则返回a
* 如果a和b的符号不相同(difSab=1), a >= 0(sa=1), 则返回a
*/
int returnA = difSab * sa + sameSab * sc;
int returnB = flip(returnA);
return a * returnA + b * returnB;
}
public static void main(String[] args) {
System.out.println(getMax(10, 20));
}
}

7)判断一个32位正数是不是2的幂、4的幂

public class Main {
/**
* 二进制下只有一个状态为1
*/
public static boolean is2Power(int n) {
return (n & (n - 1)) == 0;
}
public static boolean is2Power2(int n) {
int x = n & (~n + 1); // 找到最右侧为1的数
return x == n;
}
public static boolean is4Power(int n) {
/**
* 1. 首先需要判断是2的幂
* 2. 4^0=1, 4^1=100, 4^2=10000, 4^3=1000000 ==> 1的位置在基数位置 1 3 5 7
* 因此跟 ......01010101010101
*/
return (n & (n - 1)) == 0 && (n & 0x55555555) != 0;
}
public static void main(String[] args) {
System.out.println(is2Power(19));
System.out.println(is2Power2(19));
}
}

8)给定两个有符号32位整数a和b，不能使用算术运算符，分别实现a和b的加、减、乘、除运算

public class Main {
/**
* 加法
*/
public static int add(int a, int b) {
int sum = a;
// 当进位信息为0时就结束了
while (b != 0) {
/**
* 1. 异或运算等于无进位的结果
* 2. &运算的结果左移以为就是进位的结果
* 3. 将1、2步骤的结果相加
*/
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
return sum;
}
/**
* 减法
* 将b变成负数与a相加
*/
public static int minus(int a, int b) {
return add(a, negNum(b));
}
/**
* 取反加1
*/
public static int negNum(int n) {
return add(~n, 1);
}
/**
* 乘法
* 跟十进制的乘法一样
*/
public static int multi(int a, int b) {
int sum = 0;
while (b != 0) {
if ((b & 1) != 0) {
sum = add(sum, a);
}
a = a << 1;
b = b >>> 1;
}
return sum;
}
public static void main(String[] args) {
System.out.println(add(10, -5));
System.out.println(minus(19, 11));
System.out.println(multi(4,-5));
}
}