位运算常见问题

发表于 | 更新于 | 分类于
位运算

前言

位运算常见的问题。

整数交换

问题描述

不申请新的变量交换a,b。

1
2
3
4
5
void swap(int &a, int &b){
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

同时也可以用 +,- 做。

1
2
3
4
5
void swap(int &a, int &b){
    a = a + b;
    b = a - b;
    a = a - b;
}

比较

寻找出现奇数次的数字(I)

问题描述

有一个整型数组A，其中只有一个数出现了奇数次，其他的数都出现了偶数次，请打印这个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)。

给定整形数组A及它的大小n，请返回题目所求数字。

解题思路

n ^ 0 = n, n ^ n = 0. 依数字次异或到最后就剩那个出现奇数次的数字。

参考代码
1
2
3
4
5
6
7
int find_num(vector<int> A, n){
    int res = 0;
    for(int i = 0; i < n; i++){
        res = res ^ A[i];
    }
    return res;
}

寻找出现奇数次的数字(II)

问题描述

给定一个整型数组arr，其中有两个数出现了奇数次，其他的数都出现了偶数次，找到这两个数。要求时间复杂度为O(N)，额外空间复杂度为O(1)。

给定一个整形数组arr及它的大小n，请返回一个数组，其中两个元素为两个出现了奇数次的元素,请将他们按从小到大排列。

解题思路

首先可以得出现次数为奇数次两个数字的异或值res，然后求出res不为0的比特位数。

参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
vector<int> find_num(vector<int> arr, int n){

    //res = a ^ b
    int res = 0;
    for(int i = 0; i < n; i++){
        res = res ^ arr[i];
    }

    //get the non_zero bit
    int k = 0;
    while(!((res>>k)&1)){
        ++k;
    }

    //get a
    int a = 0;
    for(int i = 0; i < n; i++){
        if((arr[i]>>k)&1){
            a = a ^ arr[i];
        }
    }

    //get b
    int b = a ^ res;

    vector<int> out;
    if(a < b){
        out.push_back(a);
        out.push_back(b);
    }else{
        out.push_back(b);
        out.push_back(a);
    }

    return out;
}