☘前言☘
今天是算法零基础打卡的第47天，题目有点难度，给大家亿点点参考。上链接：
《算法零基础100讲》(第47讲) 位运算 (异或) 进阶
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
🎁主要知识点
左移运算
1.左移的定义
2.左移的执行结果
3.负数的执行结果
4.左移负数的执行结果
5.左移溢出的结果
左移运算的亿些运用
1.取模运算
2.作为标记码
📓课后习题
190. 颠倒二进制位
231. 2 的幂
476. 数字的补数
338. 比特位计数
📑写在最后
🎁主要知识点
左移运算
1.左移的定义
左移运算是一个二元运算符x<<y，其中x和y都是整数，读作“x左移y位"。
( . . . 100000 ) 2 ⇒ ( 100000 00...0 ⏟ y ) 2
可以看到就是在低位补0
2.左移的执行结果
x ≪ y 的 执 行 结 果 等 价 于 x × 2
#include <stdio.h> int main() { int x = 3; int y = 5; printf("%d\n", x << y); return 0; }
执 行 结 果 等 价 于 3 × 2 5 = 96 符 合 结 论
最常用的方式是1<<y来生成2的幂
3.负数的执行结果
当x为负数的时候
( 11111111111111111111111111111111 ) 2 ⇒ ( 11111111111111111111111111111110 ) 2
也是同样的运算规律
4.左移负数的执行结果
与右移的效果是一样的
5.左移溢出的结果
会产生同余效果 int的最大长度是2^32
左移运算的亿些运用
1.取模运算
x m o d y ⇒ x & ( ( 1 ≪ y ) − 1 )
2.作为标记码
1<<y可以对第y位进行操作
需要与位与位或 位异或和取反结合0.0
📓课后习题
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; //第i位取反 n ^= (uint32_t)1 << 31 - i; //第32-i位取反 } return n; }
231. 2 的幂
231. 2 的幂
给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回true ；否则，返回false 。
如果存在一个整数x使得n == 2x ，则认为 n是 2 的幂次方。
解题思路
如果一个数字是2的幂 那么这个数字二进制只有一个1 其余为0 并且 x & (x-1) = 0
bool isPowerOfTwo(int n){ return n <=0 ? false : !(n &(n-1));//一行搞定？ }
476. 数字的补数
476. 数字的补数
对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。
例如，整数 5 的二进制表示是"101" ，取反后得到"010" ，再转回十进制表示得到补数 2 。
给你一个整数num ，输出它的补数。
解题思路
依次判断把每一位取反就好了，用num>>i做判断跳出循环。
int findComplement(int num){ for(int i = 0;num >> i;i++) num = num ^ (1 << i); return num; }
338. 比特位计数
338. 比特位计数
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1的数组ans 作为答案。
解题思路
依次计算插入结果就好了
int* countBits(int n, int* returnSize){ *returnSize = n + 1; int *ans = malloc(sizeof(int) * (n + 1)),size= 0; for(int i = 0;i <= n;i++){ int temp = i,count = 0; while(temp){ if(temp & 1) count++; //看最低位是否为1 temp >>= 1; //右移一位 } ans[size++] = count; } return ans; }
