一. 怎样表示带符号的整数？

在计数系统中，整数的符号可以用多种办法表示，例如原码、反码、补码、

这三种表示方式都用最高有效位表示正负，0 代表正，1 代表负。当前计算机大多采用补码来表示带符号的整数

原码反转每个二进制位，即可求得该原码对应的反码；原码反转每个二进制位，然后给反转的总结果加 1，即可求得该原码对应的补码。

正数的补码和原码是一样的，对一个数的原码求补码会得到这个数的相反数

例1： 用补码表示有符号数 35、-35

课堂练习

用补码表示有符号数 23、-23、105、-105

1.1 3 位计算机示例

不论计算机是多少位的，下面这几条规则均适用于补码表示法

1. 0 总是用所有二进制位都是 0 的数来表示
2. -1 总是用所有二进制位都是 1 的数来表示
3. 值最小的负整数总是用开头为 1 且其余二进制位均为 0 的数来表示
4. 值最大的数总是用开头为 0 且其余二进制位均为 1 的数来表示

用 3 位计算机做加减法

1. 2 + 1
2. 3 +（-1）
3. 2 +（-4）
4. 3 + 2
5. (-4) + 3

二. 初探位运算

2.1 按位取反 ~

~ 把 1 变为 0，把 0 变为 1

~（11011）= （00100）

2.2 按位与 &

& 通过逐位比较两个运算对象，对于每个位，两个运算对象相应位都为 1，结果为 1，否则为 0

（11011）& （00100）=（00000）

2.3 按位或 |

| 通过逐位比较两个运算对象，对于每个位，两个运算对象相应位只要有一个为 1，结果为 1，否则为 0

（11011） |（00100） = （11111）

2.4 按位异或 ^

^ 通过逐位比较两个运算对象，对于每个位，两个运算对象相应位不同为 1，相同为 0

（11011）^（00100）=（11111）

2.5 掩码(mask)

掩码指的是一串用于与目标数字进行按位操作的二进制数字

可以将目标数字中的 0 看作关闭，1 看作打开

2.5.1 打开位

令 flags 表示目标数字。假如 flags = 00001111

打开 flags 的第几位，就令 mask 的第几位为 1，其余位为 0，然后 flags | mask

如打开 flags 的第 8 位，flags | 10000000

2.5.2 关闭位

令 flags 表示目标数字。假如 flags = 00001111

关闭 flags 的第几位，就令 mask 的第几位为 1，其余位为 0，然后 flags & ~mask

如关闭 flags 的第 3 位，flags & ~00000100

2.5.3 切换位

如果目标数字的该位打开，将其关闭。如果该位关闭，将其打开

令 flags 表示目标数字。假如 flags = 00001111

切换 flags 的第几位，就令 mask 的第几位为 1，其余位为 0，然后 flags ^ mask

如切换 flags 的第 3 位，flags ^ 00000100

2.5.4 检查某位

令 flags 表示目标数字。假如 flags = 00001111

检查 flags 的某位，就令 mask 对应的某位为 1，其余为 0

1. (flags & mask) == mask，flags 的该位为 1，处于打开状态
2. (flags & mask) != mask，flags 的该位为 0，处于关闭状态

#include <stdio.h>
typedef unsigned char byte;

const byte read_power = 0x1;   // 001
const byte write_power = 0x2;  // 010
const byte exec_power = 0x4;   // 100

void checkPower(const byte power)
{
    if((power & read_power) == read_power)
        printf("Read ");
    if((power & write_power) == write_power)
        printf("Wrire ");
    if((power & exec_power) == exec_power)
        printf("Execute\n");
}

int main(void)
{
    byte my_power = 0x7;
    checkPower(my_power);

    my_power = my_power & (~read_power);   
    checkPower(my_power);

    my_power = my_power | read_power; 
    checkPower(my_power);
    return 0;
}

作业

给你一幅由 N * N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计算法，将图像旋转 90 度。

1. 设计一个使用额外的空间的算法
2. 设计一个不使用额外空间的算法

示例

matrix = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

// 旋转后，使其变为
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]