?前言?

今天是算法零基础打卡的第46天，题目本身不难，主要是为了理解位运算的。上链接：
《算法零基础100讲》(第46讲) 位运算 (异或) 入门

🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
?联系方式：2201891280(QQ)
?全文大约阅读时间： 20min

全文目录

?前言?
🎁主要知识点
📓课后习题
📑写在最后

🎁主要知识点

异或运算

简单凯来说就是同零异一，来看看真值表

x y x ^ y
0 0 0
1 0 1
0 1 1
1 1 0

异或运算的应用

标记位取反

位或的特性：

一个数与1异或就相当于取反
一个数与0异或就相当于不变

int main() {
    int x;
    scanf("%d", &x);
    printf("%d\n", x ^ 0b1000); 
    return 0;
}

变量交换

因为同0异1，再加上上面的性质，就可以得出下面的代码。

int main() {
    int a, b;
	while (scanf("%d %d", &a, &b) != EOF) {
	    a = a ^ b;   // (1)
	    b = a ^ b;   // (2)
	    a = a ^ b;   // (3)
	    printf("%d %d\n", a, b);
	}
	return 0;
}

出现奇数次的数

因为偶数的异或之后结果为0，所以出现奇数次就会被剩下。

int main() {
    int n, x, i, ans;
    scanf("%d", &n);
    ans = 0;
    for(i = 0; i < n; ++i) {
        scanf("%d", &x);
        ans = (ans ^ x);
    } 
    printf("%d\n", ans);
    return 0;
}

📓课后习题

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

解题思路

这个和奇数次那个思路是一样的。

int singleNumber(int* nums, int numsSize){
    int ans = 0;
    for(int i = 0;i < numsSize;i++)
        ans ^= nums[i];
    return ans;
}

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。
提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在示例 2 中，输入表示有符号整数-3，输出表示有符号整数 -1073741825。

解题思路

判断对应位是否相等，相等就跳过，不等将两者翻转

bool getbit(uint32_t n,int k){
    return n & ((uint32_t)1<<k);
}
uint32_t reverseBits(uint32_t n) {
    for(int i = 0; i < 16; ++i)
        if(getbit(n,i) != getbit(n, 31-i)){	//不等于时进行翻转
            n ^= (uint32_t)1 << i;	//翻转
            n ^= (uint32_t)1 << 31 - i;//翻转
        }
    return n;
}

461. 汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

解题思路

只要两者位不同就加1

int hammingDistance(int x, int y){
    int count = 0;
    for(unsigned i = 1;i < 2147483648;i<<=1)
        if((i&x)^(i&y)) count++;
    return count;
}

1486. 数组异或操作

给你两个整数，n和start 。
数组nums定义为：nums[i] = start + 2*i（下标从 0 开始）且 n == nums.length 。
请返回 nums中所有元素按位异或 （XOR） 后得到的结果。

解题思路

让干啥干啥？

int xorOperation(int n, int start){
    int ans = 0;
    for(int i = 0; i < n; ++i)
        ans ^= start + 2*i;
    return ans;
}

477. 汉明距离总和

两个整数的 汉明距离 指的是这两个数字的二进制数对应位不同的数量。
给你一个整数数组 nums，请你计算并返回 nums中任意两个数之间汉明距离的总和。

解题思路

直接冲肯定超时，所以换一个思路，可以按位来统计，直接计算结果然后加入统计。

int totalHammingDistance(int* nums, int numsSize){
    int ans = 0;
    for(int i = 0;i < 32;i++){
        int count = 0;
        for(int j = 0;j < numsSize;j++)	
            if(nums[j] & ((unsigned)1<<i))   count++;//统计1的数量
        ans+=(numsSize - count)*count;	//假如结果
    }
    return ans;
}

1720. 解码异或后的数组

未知整数数组arr 由n 个非负整数组成。
经编码后变为长度为n - 1的另一个整数数组encoded ，其中encoded[i] = arr[i] XOR arr[i + 1]。例如，arr = [1,0,2,1]经编码后得到 encoded = [1,2,3] 。
给你编码后的数组 encoded和原数组 arr 的第一个元素first（arr[0]）。
请解码返回原数组arr。可以证明答案存在并且是唯一的。

解题思路

利用异或再异或就可以回来的性质直接算就好了。

int* decode(int* encoded, int encodedSize, int first, int* returnSize){
    *returnSize = encodedSize + 1;
    int *ans = malloc(sizeof(int)*(encodedSize + 1) );
    ans[0] = first;
    for(int i = 0; i < encodedSize; ++i)
        ans[i+1] = encoded[i] ^ ans[i];
    return ans;
}