开发基础随笔之位运算符（Bitwise Operators）

• 位运算符，属于算术运算符

1. 按位逻辑运算符：

~ 按位非   ~a   a的按位非
& 按位与   a&b  a和b的按位与
| 按位或     a|b   a和b的按位或
^ 按位异或    a^b   a和b的按位异或

2. 位移运算符：

<< 按位左移   a<<b   a左移b位
>> 按位右移   a>>b   a右移b位

• 位运算符的运算数只能是整数

---

位移运算符：按位左移

• a<<b：a左移b位，低位补0

int a = 5;
printf("%d", a << 3); // 40

a是int变量，占据32位、4个字节：

00000000 00000000 00000000 00000101 // 5

让a左移3位，相当于让a这一串整体向左挪动，结果相当于在0...101后面补上3个0：

00000000 00000000 00000000 00000101 000 

但是由于4个字节只有32位，因此将开头的3个0舍去，最终变成：

00000000 00000000 00000000 00101000 // 40

如果是负数的情况例子🌰：

int a = -5;
printf("%d", a << 3); // -40

11111111 11111111 11111111 11111011 // -5

11111111 11111111 11111111 11111011 000

11111111 11111111 11111111 11011000 // -40

• 有什么规律：
  整数5向左移3位后，2⁰ + 2² 变成 2³ + 2⁵ = (2⁰ + 2²) * 2³
  所以a << b 的运算结果跟 a * 2^b 一样

位移运算符：按位右移

• a>>b：a右移b位，高位用符号位填充

int a = 40;
printf("%d", a >> 3); // 5

00000000 00000000 00000000 00101000 // 40

40右移3位，相当于整体往右边移动，这时候就左边补上3个0，因为a是正数，所以补充的是0：

000 00000000 00000000 00000000 00101000

同样的由于4个字节只有32位，这时候右边的就要舍弃3位：

00000000 00000000 00000000 00000101 // 5

如果是负数的情况例子🌰：

int a = -40;
printf("%d", a >> 3); // 5-

由于a是负数，所有左边最高位就是用1来填补：

11111111 11111111 11111111 11011000 // -40

111 11111111 11111111 11111111 11011000 

11111111 11111111 11111111 11111011 // -5

• 有什么规律：
  整数40向右移3位后，由 2³ + 2⁵ 变成了 2⁰ + 2² = (2³ + 2⁵) * 2^-3 = (2³ + 2⁵) / 2³
  所以所以a >> b 的运算结果跟 a / 2^b 一样

应用例子🌰：计算a的两倍

之前做法是：

int a = 2;
printf("%d", a * 2); // 4

现在用位移来实现：直接向左移1位

int a = 2;
printf("%d", a << 1); // 4

同样的，计算下a的一半，之前做法是用除法/，现在通过右移实现：

int a = 2;
printf("%d", a >> 1); // 1

---

按位逻辑运算符

• 按位非，也叫做按位取反
  ~a：将a的所有二进制位（包括符号位）取反，0变1，1变0

// 00000000 00000000 00000000 00000000
int a = 0;
// 11111111 11111111 11111111 11111111
printf("%d", ~a); // -1

// 00000000 00000000 00000000 00000001
int a = 1;
// 11111111 11111111 11111111 11111110
printf("%d", ~a); // -2

// 00000000 00000000 00000000 00010011
int a = 19;
// 11111111 11111111 11111111 11101100
printf("%d", ~a); // -20

// 11111111 11111111 11111111 11101100
int a = -20;
// 00000000 00000000 00000000 00010011
printf("%d", ~a); // 19

• 按位与
  a & b：将每个二进制位的数值进行对比
  只有当2个二进制位都为1时，运算结果才为1
  只要有1个二进制位为0，运算结果就为0

int a = 140;
int b = 200;
printf("%d", a & b); // 136
/*
a：     00000000 00000000 00000000 10001100  // 140
b：     00000000 00000000 00000000 11001000  // 200
a & b： 00000000 00000000 00000000 10001000  // 136
*/

• 按位或
  a | b：将每个二进制位的数值进行对比
  只要有1个二进制位为1，运算结果就为1
  只有当2个二进制位都为0时候，运算结果才为0

int a = 140;
int b = 200;
printf("%d", a | b); // 204
/*
a：     00000000 00000000 00000000 10001100  // 140
b：     00000000 00000000 00000000 11001000  // 200
a & b： 00000000 00000000 00000000 11001100  // 204
*/

• 按位异或
  a ^ b：将每个二进制位的数值进行对比
  当2个二进制位的值不相等时，运算结果就为1
  当2个二进制位的值相等时，运算结果才为0

int a = 140;
int b = 200;
printf("%d", a ^ b); // 68
/*
a：     00000000 00000000 00000000 10001100  // 140
b：     00000000 00000000 00000000 11001000  // 200
a & b： 00000000 00000000 00000000 01000100  // 68
*/

特点：
a ^ 0：结果为a
a ^ a：结果为0
a ^ b=b ^ a
a ^ b ^ c=a ^ (b ^ c)=(a ^ c) ^ b：多个值进行异或，值的位置顺序不影响

---

与位运算符相关的赋值运算符

---

按位与&判断奇偶性

一般我们判断一个数的奇偶，通常都是用这个数跟2取余，余数为0是偶数，否则是奇数：

int a = 26;
printf("%s", (a % 2) ? "奇数" : "偶数"); // 偶数

int b = 25;
printf("%s", (b % 2) ? "奇数" : "偶数"); // 奇数

现在还可以用按位与&来判断奇偶：

int a = 26;
printf("%s", (a & 1) ? "奇数" : "偶数"); // 偶数
        
int b = 25;
printf("%s", (b & 1) ? "奇数" : "偶数"); // 奇数

根据按位与的规则，我们来看下：任何数跟1进行按位与操作，就看最后一位，二进制位最低位是1，结果就是1，如果是0，结果就是0。

    0b 1100 (12)
&   0b 0001 (1)
=   0b 0000 (0)
         
    0b 1101 (13)
&   0b 0001 (1)
=   0b 0001 (1)

所以只要看下a的最低位是什么，就能知道奇偶。不管你左边的二进制位数有多少1或者0（最终换成十进制相加肯定是偶数），这时候只要你最低位是1（1是 2⁰ = 1）最终换成十进制最后一位是+ 1必定奇数；如果最低位是0，偶数+ 0依然是偶数。

---

不使用第三方变量交互两个整型变量的值

一般需要交互两个数的值，我们会通过一个临时的值来进行交互：

int a = 10;
int b = 20; 
        
int temp = a; // 10
a = b; // 20
b = temp; // 10
printf("%d  %d\n", a, b); // 20 10

但是这种方法需要多声明一个变量，无形中浪费了内存，那么如何不通过第三方变量进行交换：

a = a + b; // 30 = 10 + 20
b = a - b; // 10 = 30 - 20
a = a - b; // 10 = 30 - 10
printf("%d  %d\n", a, b);

a = a * b; // 200 = 10 * 20
b = a / b; // 10 = 200 / 20
a = a / b; // 20 = 200 / 10
printf("%d  %d\n", a, b);

a = a - b; // -10 = 10 - 20
b = a + b; // 10 = -10 + 20
a = b - a; // 20 = 10 - -10
printf("%d  %d\n", a, b);

上面借助两个变量间的加减乘除计算，来交互两个值。这种做法有不足，整型在计算的时候容易造成值溢出或者精度丢失；加减乘容易导致溢出，除法会导致精度丢失。
通过按位异或^直接操作二进制位进行交互，不会有上述的问题。

a = a ^ b; 
b = a ^ b; 
a = a ^ b; 
printf("%d  %d\n", a, b);

我们知道异或有几个特点：
a ^ 0：结果为a
a ^ a：结果为0
a ^ b=b ^ a
a ^ b ^ c=a ^ (b ^ c)=(a ^ c) ^ b
那么第二步中的

b = a ^ b;  等价于  10 ^ 20 ^ 20 ===  10 ^ 0 === 10

第三步中的

a = a ^ b;  等价于  10 ^ 20 ^ 10 ===  10 ^ 10 ^ 20 === 0 ^ 20 === 20

最终a、b实现了交互
又因为按位异或赋值符号^=的存在，我们可以进行更简洁的写法：

a ^= b; // a = a ^ b
b ^= a; // b = b ^ a = a ^ b
a ^= b; // a = a ^ b
printf("%d  %d\n", a, b);