【位运算进阶之—-左移（＜＜）】

大家好，欢迎来到IT知识分享网。

今天我们来谈谈左移这件事。

❤️简单来说，对一个数左移就是在其的二进制表达末尾添0。左移一位添一个0，结果就是乘以2；左移两位添两个0，结果就乘以2 ^ 2；左移n位添n个0，结果就是乘以2 ^ n，小心溢出😄！

一、基础知识：

✨左移操作是一种位操作，用来将一个数的二进制表达的所有位向左移动指定的位数，并在右侧用0填充空位。

1️⃣ 左移的二进制表示：

✨x<<y 表示将x向左移动y位。（其中x和y都是整数）
如：1001 << 2 —->

2️⃣ 左移的执行结果：

#include<stdio.h> int main(void) { 
       int x = 3, y = 2; printf("%d", x << y);//3*（2^2） return 0; } 

• 可能聪明的你已经想到了左移的强大之处，即对1左移时，得到的都是2的幂，这是一个非常重要的知识点❗️

• 上面我们讨论的左移都是对正整数来说的，那如果对负数呢？对负数左移会发生什么？左移负数位又是如何？阁下莫急，且听我慢慢道来……

3️⃣ 对负数左移：

如：-3<<2 是多少呢？相信你心中已经有答案了，请看下图！

#include<stdio.h> int main(void) { 
        int x = -3, y = 2; printf("%d", x << y); return 0; } 

这其实也可以用补码来解释：

• -(3<<2):
  • 3的补码：00000000 00000000 00000000 00000011
  • 3的补码左移两位：00000000 00000000 00000000 00001100=12 ，再取负得-12。
• -3<<2:
  • -3的补码：
  • -3的补码左移两位：
  • 转换成原码： 00000000 00000000 00001011+1 = 00000000 00000000 00001100 = -12。

4️⃣ 左移负数位：

那么，3<<(-2)又是多少呢？😢 放过我吧！💢💢💢

#include<stdio.h> int main(void) { 
         printf("%d", 32<< (-1)); return 0; } 

• 可能有朋友就要类比了，加上-1就是减去1，那么左移-1位是不是右移一位呢？让我们继续往下看：

• 咦，怎么有条波浪线？这是什么？输出怎么会是0？按道理来说如果是右移那么结果是32/2=16啊！！！

为什么会有警告？难道我想错了？

• 让我们寻着警告去看看到底问题出在哪儿了！

5️⃣左移时溢出！

✨（非溢出）移位可以分为逻辑移位和算术移位。

• 无符号整数：逻辑移位，左、右添0；
• 有符号整数：算术移位，符号位不变，分正负；

✨溢出可以分为位溢出和值溢出（此为博主自己分的，可能不合理，但博主自己觉得合理），而我们又知道，整数分为无符号整数和有符号整数。所以通过组合我们大概了解到，此处的溢出一共有4种情况。

（1）位溢出（移位/mod的角度）：

✨对于位溢出来说，我们在上面已经讨论过了，int 类型一共32位，移位大于等于32位或小于0位即为位溢出。

注：在不同的编程语言中，对于超出操作数位数的移位操作，可能会有不同的行为。一些语言会将超出的位数进行取模操作，即将移位的位数先对操作数的位数取模，然后再进行相应的位移，比如C语言❗️❗️❗️

（2） 值溢出（值的角度）：

✨当变量的值超过了其所能表达的值的范围时，产生值溢出。但溢出的值并不会消失，而是以另一种形式存在着。

下面我们举例来说明：

❤️有符号整数：

#include<stdio.h> int main(void) { 
          int a = 9; printf("%d\n", a << 31); printf("%d\n", a << 32);//等价于a<<0; printf("%d", a<<33);//等价于a<<1; return 0; } 

1️⃣左移31位：（31<32)未溢出

• 1.从移位的角度来看：
  • 第一步，左移31位： 00000000 00000000 00000000（负）
  • 第二步，再求出其原码：0 +1= 00000000 00000000 00000000（先记下符号位，然后各位取反，末位加一，再回归符号位）
  • 第三步，可以看出这是最小的数：也即-2^31=-
• 2.从值的角度来看:
  因为9<<31=9 * (2 ^ 31) ，下面我们结合下图来看👇
  
  
  

注：0 和 -2 ^ 31 相对

☝️如上图所示，对于int 类型（有符号整数）的x来说，其范围为：-2 ^ 31 ~ 2 ^ 31-1，当x=2 ^ 31 -1时，x+1将会变为-2 ^ 31,从而我们可以看出越界的本质就是转圈圈。此处1圈是2 ^ 32个数，半圈是2 ^ 31 个数。所以9<<31=9* (2 ^ 31)=4.5* 2 ^ 32=4.5圈，去除整圈，得到0.5圈，从而结果是-2 ^ 31。怎么样，是不是很神奇？
👏当然，也可以通过取模来理解（其实补码的本质就是模运算），将原值与2 ^ 32 取模（因为1圈是2 ^ 32个数），得到2 ^ 31, 但有符号整数上界为2 ^ 31-1,再加一个数将会过渡到最小数 - (2 ^ 31).（此处是有向增加的）

2️⃣左移32位：(32=32溢出)

• 1.从移位的角度来看：
  • 第一步，左移32位：00000000 00000000 00000000 00000000（正）
  • 第二步，求出其原码： +1=00000000 00000000 00000000 00000000❗️咦❓怎么是0啊❓上面的结果明明是9啊❗️怎么回事❓
    
    

👉这就要考虑到位溢出了！我们上面说过了，C语言会将超出的位数进行取模操作，即将移位的位数对操作数的位数取模，然后进行相应的位移。因为如果直接移位的话，当移位长度大于31时必定是0；因为32>=32,所以32=0(mod(32))，从而原式的值等于00000000 00000000 00000000 00001001左移0位，也就是9本身。

mod可以理解为%运算；

• 2.从值的角度来看：

3️⃣左移33位与左移32位类似，将位数33先和32取模再进行移位。此处不再赘述。

❤️无符号整数：

如上图，☝️

• 无符号整数unsigned int 范围为 0~(2 ^ 32)-1,总共也是2 ^ 32个数，但都是非负数。

(2 ^ 32 -1) +1 = 0 ,即结果要对2 ^ 32取模。

#include<stdio.h> int main(void) { 
           int a = 9; unsigned int b = a ; printf("%d\n", a << 31); printf("%u\n", b<<31); printf("%d\n", a << 32); printf("%u\n", b << 32); return 0; } 

二、拓展应用：

1. 取模和位运算的转换：

✨x mod (2 ^ y) = x &((1<<y)-1) 即取x二进制表达后y位。（对于位与的操作可以参考前面的博文）

2. 生成标记码：

✨现将1<<k作为第k个标记位的标记码。（此处取从0开始）

（1. 标记位置1：

✨对于二进制数x，将它的第k位置为1.（从低位开始计位，即从右往左）

置1—>位或：x|(1<<k)

（2. 标记位置0：

✨对于二进制数x，将它的第k位置为0.（从低位开始计位，即从右往左）

置0—>位与：x&(1<<k) ，哦，不不不，不是这样的，应该是x&(~(1<<k))

（3. 标记位取反：

✨对于二进制数x，将它的第k位取反.（从低位开始计位，即从右往左）
取反—>异或：x^(1<<k)

3. 生成掩码：

✨我们可以通过左移来生成一个掩码，从而实现对一个数二进制表达的末k位执行一些操作。

• 1<<k表示100…00（1加上k个0）
• (1<<k)-1表示011111（0加上k个1）

😵好了，今天的讲解就到这里了，相信你也是收获满满吧！

这真的我是肝的最久的一篇文章了，没有之一，从早上肝到了晚上，，，😭😭😭