位运算算法篇：异或运算

位运算算法篇：异或运算

引用

CSDN

1.

https://m.blog.csdn.net/2301_80260194/article/details/145532893

位运算中的异或运算是一种非常有趣且实用的运算方式。它不仅在算法设计中有着广泛的应用，而且其独特的性质和规则也使得它成为计算机科学领域的一个重要知识点。本文将从异或运算的基本原理出发，深入探讨其在实际编程中的多种应用场景，帮助读者全面理解并掌握这一运算方式。

1. 原理

(1). 无进位相加

异或运算的规则是"相同为0，相异为1"。为了更好地理解这个规则，我们可以将其理解为"无进位相加"。在二进制加法中，逢二进一的原则会导致两个1相加时产生进位，而异或运算则不会产生这样的进位。例如：

10011001 ^ 11110101
10011001
+11110101
——————
01101100

(2). 异或运算的性质

异或运算满足交换律和结合律。对于任意四个数a、b、c、d，它们的异或运算结果与运算顺序无关：

a ^ b ^ c ^ d = a ^ c ^ b ^ d = (a ^ c) ^ d ^ b = (a ^ (c ^ b) ^ d)

异或运算的另一个重要性质是：任何数与0异或等于其本身，任何数与自身异或等于0。这个性质可以推广到多个相同数的异或运算中：

• 偶数个相同数异或的结果为0
• 奇数个相同数异或的结果为该数本身

这个性质在解决某些特定问题时非常有用。例如，已知一个序列的整体异或和c，以及该序列一部分的异或和b，要找到另一部分的异或和a，可以通过以下方式计算：

c = a ^ b
a = c ^ b ^ b = a ^ (b ^ b) = a ^ 0 = a

2. 应用

(1). 交换两个数

要交换两个数a和b的值，可以使用异或运算：

#include<iostream>
using namespace std;
int main()
{
    int a=10,b=20;
    cout<<"before: "<<a<<" "<<b<<endl;
    a=a^b;
    b=a^b;
    a=a^b;
    cout<<"After: "<<a<<" "<<b<<endl;
    return 0;
}

(2). 找到缺失的数

在一个连续区间中找到缺失的数，可以使用异或运算：

#include<iostream>
using namespace std;
int main()
{
    int arr[]={1,2,3,4,5,6,7,8,10};
    int ret=0;
    for(int i=1;i<=10;i++)
    {
        ret^=i;
    }
    int ret2=0;
    for(int i=0;i<sizeof(arr)/sizeof(int);i++)
    {
        ret2^=arr[i];
    }
    ret=ret^ret2;
    cout<<ret<<endl;
    return 0;
}

(3). 比较两个数的大小

使用位运算比较两个数的大小，不使用条件判断语句：

#include<iostream>
using namespace std;
void getmax(int a,int b)
{
    int c=a-b;
    int returnB=(c>>31)&1;
    int returnA=1-returnB;
    int  res=a*returnA+b*returnB;
    cout<<"the max is:"<<res<<endl;
    return;
}
int main()
{
    int a=20,b=10;
    getmax(a,b);
    a=10,b=30;
    getmax(a,b);
    return 0;
}

(4). 找到出现为奇数次的数

在一个序列中找到出现奇数次的数：

#include<iostream>
using namespace std;
int main()
{
    int arr[]={1,1,1,2,2,3,3,4,4,5,5};
    int ret=0;
    for(int i=0;i<sizeof(arr)/sizeof(int);i++)
    {
        ret^=arr[i];
    }
    cout<<ret<<endl;
    return 0;
}

(5). 找到两个不同出现奇数次的数

在一个序列中找到两个出现奇数次的数：

#include<iostream>
using namespace std;
int main()
{
    int arr[]={1,1,1,2,2,3,3,4,4,5,5,7,7,7};
    int ret=0;
    for(int i=0;i<sizeof(arr)/sizeof(int);i++)
    {
        ret^=arr[i];
    }
    int check=ret&(-ret);
    int ret2=0;
    for(int i=0;i<sizeof(arr)/sizeof(int);i++)
    {
        if((check&arr[i])!=0)
        {
            ret2^=arr[i];
        }
    }
    ret=ret^ret2;
    cout<<ret<<" "<<ret2<<endl;
    return 0;
}

(6). 找到出现次数小于m次的数

在一个序列中找到出现次数小于m次的数：

#include <iostream>
#include <vector>
using namespace std;
int findNumberAppearingLessThanMTimes(const vector<int>& nums, int m) {
    int result = 0;
    int bitCount[32] = {0};  // 用于统计每一位上1的个数
    // 遍历每一位
    for (int i = 0; i < 32; ++i) {
        for (int num : nums) {
            // 检查num的第i位是否为1
            if (num & (1 << i)) {
                bitCount[i]++;
            }
        }
        // 如果第i位上1的个数不是m的倍数，则结果的第i位为1
        if (bitCount[i] % m != 0) {
            result |= (1 << i);
        }
    }
    return result;
}
int main() {
    vector<int> nums = {2, 2, 3, 3, 3, 4, 4, 4, 4};  // 示例序列
    int m = 3;  // 其他数出现的次数
    int result = findNumberAppearingLessThanMTimes(nums, m);
    cout << "The number appearing less than " << m << " times is: " << result << endl;
    return 0;
}

3. 结语

异或运算在计算机科学中有着广泛的应用，从基础的位操作到复杂的算法设计，都能看到它的身影。通过本文的介绍，相信读者对异或运算有了更深入的理解。希望这些知识能为你的编程之路提供帮助。