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

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

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

下面就让我们来详细看看吧！

---

---

一、基础知识：

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

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

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

---

2️⃣ 左移的执行结果：

✨左移操作相当于将一个数乘以2的n次方。
x<<y <=> x * (2 ^ y)
如：

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

执行结果如下：

如上图可见，3<<2 = 3 * (2^2)= 3*4 = 12;

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

1左移n位	值	2的幂
1<<1	2	2^1
1<<2	4	2^2
1<<3	8	2^3
…	…	…
1<<n	2^n	2^n

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

---

3️⃣ 对负数左移：

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

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

执行结果如下：

✨(-x)<<y <=>-(x<<y) ：即对负数左移y位等于对正数左移y位后再取负。

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

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

---

4️⃣ 左移负数位：

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

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

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

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

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

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

警告1 （点我👈）

警告2（点我👈）

😄看来左移负数位是未定义的行为啊，所以我们最好不要这样写，可能会带来不必要的麻烦，如果想要右移的话就乖乖使用右移操作。

---

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;
}

执行结果如下：

如上面的代码所示，a原本是9，其二进制表达为：00000000 00000000 00000000 00001001，现在对其进行左移操作：

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

• 1.从移位的角度来看：
  • 第一步，左移31位：10000000 00000000 00000000 00000000（负）
  • 第二步，再求出其原码：01111111 11111111 11111111 1111111+1=10000000 00000000 00000000 00000000（先记下符号位，然后各位取反，末位加一，再回归符号位）
  • 第三步，可以看出这是最小的数：也即-2^31=-2147483648
• 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位：

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

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

mod可以理解为%运算；

• 2.从值的角度来看：

✨对于上面的9<<32，我们不能仅仅通过表面的移位去观察，而更应该计算一番。
👉因为9<<32=9*(2^32) ，所以原式就等于9圈，刚好是0。😄

3️⃣左移33位与左移32位类似，先对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;
}

执行结果如下：

注：无符号十进制整数用%u输出；
计算方法根据上图转圈圈就好，此处不再赘述。

---

二、拓展应用：

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）

从而可以进行以下操作：
🌟将末k位变为1：x|((1<<k)-1)
🌟将末k位变为0：x&(1<<k) 或 x&(~((1<<k)-1))
🌟将末k位都取反：x^((1<<k)-1)

---

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

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

---