[解题报告]《算法零基础100讲》(第48讲) 位运算 (左移)

今天是算法零基础打卡的第47天，题目有点难度，给大家亿点点参考。上链接：
《算法零基础100讲》(第47讲) 位运算 (异或) 进阶

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

• ☘前言☘
• 主要知识点
• • 左移运算
  • • 1.左移的定义
    • 2.左移的执行结果
    • 3.负数的执行结果
    • 4.左移负数的执行结果
    • 5.左移溢出的结果
  • 左移运算的亿些运用
  • • 1.取模运算
    • 2.作为标记码
• 课后习题
• • 190. 颠倒二进制位
  • 231. 2 的幂
  • 476. 数字的补数
  • 338. 比特位计数
• 写在最后

左移运算是一个二元运算符x< ( . . . 100000 ) 2 ⇒ ( 100000 00...0 ⏟ y ) 2 left (...100000 right )_2Rightarrow left (100000underbrace{00...0}_{y} right )_2 (...100000)2​⇒(100000y 00...0​​)2​
可以看到就是在低位补0

x ≪ y 的 执 行 结 果 等 价 于 x × 2 y bold x bold llbold y 的执行结果等价于 x times 2^y x≪y的执行结果等价于x×2y

#include 
int main() {
   int x = 3;
   int y = 5;
   printf("%dn", x << y);
   return 0;
}

执 行 结 果 等 价 于 3 × 2 5 = 96 符 合 结 论 执行结果等价于 3 times 2^5 = 96符合结论 执行结果等价于3×25=96符合结论
最常用的方式是1<

当x为负数的时候
( 11111111111111111111111111111111 ) 2 ⇒ ( 11111111111111111111111111111110 ) 2 left( 11111111 11111111 11111111 11111111 right)_2Rightarrowleft( 11111111 11111111 11111111 11111110 right)_2 (11111111111111111111111111111111)2​⇒(11111111111111111111111111111110)2​
也是同样的运算规律

与右移的效果是一样的

会产生同余效果 int的最大长度是2^32

x m o d y ⇒ x & ( ( 1 ≪ y ) − 1 ) x quad modquad yRightarrow x quad & quad ((1ll y) - 1) xmody⇒x&((1≪y)−1)

1< 需要与位与位或 位异或和取反结合0.0

190. 颠倒二进制位

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

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

解题思路

有几个需要确认的点

1. 如果两个位置元素相同 不需要修改
2. 如果两个位置元素不同 两者取反就好了

bool getbit(uint32_t n,int k){
    return n & ((uint32_t)1< 
 
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;
}
 
 
写在最后 
考完试了，来补坑，今天写了足足四篇题解，，，，真的累。今天考完分布式了，就剩周五的模集让我头秃了，洗澡睡觉，明日再战0.0