异或运算^

异或相当于不进位相加

异或的性质

  • 0^N = N
  • N^N = 0
  • A^B = B ^ A交换律
  • (A^B)^C = A^(B^C)结合率
  • A^B^C^D^E 与异或的顺序无关

不用额外变量交换两个数

A = A ^ B
B = A ^ B
A = A ^ B

设A = 甲,B = 乙

第一步:A = A ^ B = 甲 ^ 乙

第二步:B = A ^ B = 甲 ^ 乙 ^ 乙 = 甲 ^ (乙 ^ 乙) = 甲 ^ 0 = 甲 = A

第三步:A = A ^ B = 甲 ^ 乙 ^ 甲 = (甲 ^ 甲)^ 乙 = 0 ^ 乙 = 乙 = B

需要注意的是,使用此方法的前提是不是同一空间的数,比如数组中

如果 a = b = 1;

用上述方法交换arr[a]和arr[b]就会发现arr[a]会被刷新为0,因为第一步就是同一个数在进行异或,这与两个相同的数交换不同

/*
int a = b = 1;
a = a ^ b = 1 ^ 1 = 0;
b = a ^ b = 0 ^ 1 = 1;
a = a ^ b = 0 ^ 1 = 1;
int[] arr = {1,1};
arr[a] = arr[a] ^ arr[b] = arr[1] ^ arr[1] = 1 ^ 1 = 0;
arr[b] = arr[a] ^ arr[b] = arr[1] ^ arr[1] = 0 ^ 0 = 0;//arr[1]的数已经完全变为了0
arr[a] = arr[a] ^ arr[b] = arr[1] ^ arr[1] = 0 ^ 0 = 0;
*/

异或的妙用

有这样一道题

  • 一个数组中有一种s数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这种数

传统做法可以创建一个哈希表,去做一个词频统计

但如果用异或运算的性质,就可以省去那个哈希表

public static int main(int[] arr){
    int eor = 0;
    for (int j : arr) {
        eor = eor ^ j;
    }
    return eor;
}

我们知道N ^ N = 0,如果给定的数组符合题目的要求,那么就只有一个数是奇数,最后的eor也就是这个数

那么将题目升级一下

  • 一个数组中有两种数出现了奇数次,其他数都出现了偶数次,怎么找到并打印这两种数?

将这道题按上一道题那样进行操作之后,最后的eor = a ^ b(a,b就是那两种数,因为a!=b,所以eor一定不为0)

那么eor二进制形式下的最右侧的那个1,就可以将a和b分为两个范围,假设eor最右侧的1是第三位上,

整个数组一类是第三位是1,还有一类是第三位为0,a和b一定是以这两类分开来的,因为eor是a ^ b得来的。异或结果为1,只有一个为1,一个为0.

那么既然我们将俩个数分开来了,那么将其中一类进行一次挨个异或操作,就可以将其中的答案之一挑选出来。

那么现在的问题就是如何去从一个int的数(a)取出最右侧的1

这里直接提供方法

ans = a & ( - a )

如何判断一个数是否该位上是否为1,

我们考虑一下与运算,全为1才是1,那么正好可以判断它与完之后是不是0来分类,如果这一位上它是0,那么与完的结果全部为0。

将为0的再进行一次异或运算就可以得出答案之一one,再将eor和one异或一下,就可以将另一个答案得出

    public static void printOddTimesNum2(int[] arr) {
        int eor = 0;
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];
        }
        // a 和 b是两种数
        int rightOne = eor & (-eor); // 提取出最右的1
        int onlyOne = 0; 
        for (int i = 0 ; i < arr.length;i++) {
            if ((arr[i] & rightOne) != 0) {
                onlyOne ^= arr[i];
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }
版权声明:除特殊说明,博客文章均为栋dong原创,依据CC BY-SA 4.0许可证进行授权,转载请附上出处链接及本声明。
如有需要,请在留言板留言,或者添加我的QQ或者微信
我只是一个学生,如有错误或者侵权,请联系我,谢!
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
春节
快乐