[转载]关于java中异或运算符讲解,另有实例()

看到一篇关于java中异或运算的文章,受益匪浅,特此转载记录一下:http://t.csdn.cn/vD8eY

异或也常用于加密、校验、密钥传输等领域,密码学中常见。

异或是一种基于二进制的位运算,用符号XOR或者^表示,其运算法则是对运算符两侧数的每一个二进制位同值则取0,异值则取1.简单理解就是不进位加法,如1+1=0,0+0=0,1+0=1.For example: 3^5 = 6转成二进制后就是 0011 ^ 0101 二号位和三号位都是异值取1 末尾两个1同值取零,所以3^5 = 0110 = 6

异或是一种基于二进制的位运算,用符号XOR或者^表示,其运算法则是对运算符两侧数的每一个二进制位同值则取0,异值则取1.简单理解就是不进位加法,如1+1=0,0+0=0,1+0=1.For example: 3^5 = 6转成二进制后就是 0011 ^ 0101 二号位和三号位都是异值取1 末尾两个1同值取零,所以3^5 = 0110 = 6

应用举例

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?解法一、显然已经有人提出了一个比较精彩的解法,将所有数加起来,减去1+2+…+1000的和。这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。解法二、异或就没有这个问题,并且性能更好。将所有的数全部异或,得到的结果与1^2^3^…^1000的结果进行异或,得到的结果就是重复数。但是这个算法虽然很简单,但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。首先是异或运算满足交换律、结合律。所以,1^2^…^n^…^n^…^1000,无论这两个n出现在什么位置,都可以转换成为1^2^…^1000^(n^n)的形式。其次,对于任何数x,都有x^x=0,x^0=x。所以1^2^…^n^…^n^…^1000 = 1^2^…^1000^(n^n)= 1^2^…^1000^0 = 1^2^…^1000(即序列中除了n的所有数的异或)。令,1^2^…^1000(序列中不包含n)的结果为T则1^2^…^1000(序列中包含n)的结果就是T^n。T^(T^n)=n。所以,将所有的数全部异或,得到的结果与1^2^3^…^1000的结果进行异或,得到的结果就是重复数。当然有人会说,1+2+…+1000的结果有高斯定律可以快速计算,但实际上1^2^…^1000的结果也是有规律的,算法比高斯定律还该简单的多。

google面试题的变形:一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数

@Test
public void fun() {
int a[] = { 22, 38,38, 22,22, 4, 4, 11, 11 };
int temp = 0;
for (int i = 0; i < a.length; i++) {
temp ^= a[i];
}
System.out.println(temp);
}

我的实例

在刷leetcode中遇到了下题:

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数  和 ,计算并返回它们之间的汉明距离。

x
y
输入:x = 1, y = 4
输出:2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

根据实例可看出,这是求两数异或后结果的二进制中非零位数的个数,用异或知识解题快速高效,因此可写出如下代码

class Solution {
    public int hammingDistance(int x, int y) {
        //先异或,再取有二进制的位数
        //将两个数字异或
        int num = x ^ y;
        //获取异或后数字的二进制不为零位
        int res = 0;
        while(num > 0){
            res++;
            num &= (num - 1);
        }
        return res;
    }
}
————————

看到一篇关于java中异或运算的文章,受益匪浅,特此转载记录一下:http://t.csdn.cn/vD8eY

异或也常用于加密、校验、密钥传输等领域,密码学中常见。

异或是一种基于二进制的位运算,用符号XOR或者^表示,其运算法则是对运算符两侧数的每一个二进制位同值则取0,异值则取1.简单理解就是不进位加法,如1+1=0,0+0=0,1+0=1.For example: 3^5 = 6转成二进制后就是 0011 ^ 0101 二号位和三号位都是异值取1 末尾两个1同值取零,所以3^5 = 0110 = 6

异或是一种基于二进制的位运算,用符号XOR或者^表示,其运算法则是对运算符两侧数的每一个二进制位同值则取0,异值则取1.简单理解就是不进位加法,如1+1=0,0+0=0,1+0=1.For example: 3^5 = 6转成二进制后就是 0011 ^ 0101 二号位和三号位都是异值取1 末尾两个1同值取零,所以3^5 = 0110 = 6

应用举例

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空间,能否设计一个算法实现?解法一、显然已经有人提出了一个比较精彩的解法,将所有数加起来,减去1+2+…+1000的和。这个算法已经足够完美了,相信出题者的标准答案也就是这个算法,唯一的问题是,如果数列过大,则可能会导致溢出。解法二、异或就没有这个问题,并且性能更好。将所有的数全部异或,得到的结果与1^2^3^…^1000的结果进行异或,得到的结果就是重复数。但是这个算法虽然很简单,但证明起来并不是一件容易的事情。这与异或运算的几个特性有关系。首先是异或运算满足交换律、结合律。所以,1^2^…^n^…^n^…^1000,无论这两个n出现在什么位置,都可以转换成为1^2^…^1000^(n^n)的形式。其次,对于任何数x,都有x^x=0,x^0=x。所以1^2^…^n^…^n^…^1000 = 1^2^…^1000^(n^n)= 1^2^…^1000^0 = 1^2^…^1000(即序列中除了n的所有数的异或)。令,1^2^…^1000(序列中不包含n)的结果为T则1^2^…^1000(序列中包含n)的结果就是T^n。T^(T^n)=n。所以,将所有的数全部异或,得到的结果与1^2^3^…^1000的结果进行异或,得到的结果就是重复数。当然有人会说,1+2+…+1000的结果有高斯定律可以快速计算,但实际上1^2^…^1000的结果也是有规律的,算法比高斯定律还该简单的多。

google面试题的变形:一个数组存放若干整数,一个数出现奇数次,其余数均出现偶数次,找出这个出现奇数次的数

@Test
public void fun() {
int a[] = { 22, 38,38, 22,22, 4, 4, 11, 11 };
int temp = 0;
for (int i = 0; i < a.length; i++) {
temp ^= a[i];
}
System.out.println(temp);
}

我的实例

在刷leetcode中遇到了下题:

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数  和 ,计算并返回它们之间的汉明距离。

x
y
输入:x = 1, y = 4
输出:2
解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

根据实例可看出,这是求两数异或后结果的二进制中非零位数的个数,用异或知识解题快速高效,因此可写出如下代码

class Solution {
    public int hammingDistance(int x, int y) {
        //先异或,再取有二进制的位数
        //将两个数字异或
        int num = x ^ y;
        //获取异或后数字的二进制不为零位
        int res = 0;
        while(num > 0){
            res++;
            num &= (num - 1);
        }
        return res;
    }
}