☘前言☘
今天是算法零基础打卡的第46天，题目本身不难，主要是为了理解位运算的。上链接：
《算法零基础100讲》(第46讲) 位运算 (异或) 入门
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
🎁主要知识点
异或运算
异或运算的应用
标记位取反
变量交换
出现奇数次的数
📓课后习题
136. 只出现一次的数字
190. 颠倒二进制位
461. 汉明距离
1486. 数组异或操作
477. 汉明距离总和
1720. 解码异或后的数组
📑写在最后
🎁主要知识点
异或运算
简单凯来说 就是同零异一，来看看真值表
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. 只出现一次的数字
136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解题思路
这个和奇数次那个思路是一样的。
int singleNumber(int* nums, int numsSize){ int ans = 0; for(int i = 0;i < numsSize;i++) ans ^= nums[i]; return ans; }
190. 颠倒二进制位
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. 汉明距离
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. 数组异或操作
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. 汉明距离总和
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. 解码异或后的数组
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; }
