34_位操作和布尔代数.md

位操作和布尔代数

1. 位与二进制

1.1 整数的二进制表示

1. 定义：$\forall \space a \in \mathbb{N}$ $$ a = \sum_{i=1}^{n}a_i2^{i-1} \space(a_i \in {1,2})$$ 其中 $2^{i-1}$ 称为第 $i$ 位的位权

1.2 计算机中的位

1. 位是最小的计算机数据存储单位
2. 每一个位存储一个二进制码（记作0或1）
3. 对于整型数据来说，每个计算机位对应这个整数二进制表示中的一个位
4. 8个位可以构成一个字节，因此在常见的实现中，int 类型有32个二进制位，long long 有64个二进制位

注：逻辑代数中，0和1不表示数量的大小，而是表示两种对立的状态

2. 位操作

位操作只能应用于整型数据

2.1 位操作的种类

1. 按位与(&)：两个数对应的位进行“与”运算，生成新数：114514&1919810=68418

   A	B	A&B
   0	0	0
   1	0	0
   0	1	0
   1	1	1

2. 按位或(|)：两个数对应的位进行“或”运算，生成新数：114514|1919810=1965906

   A	B	A|B
   0	0	0
   1	0	1
   0	1	1
   1	1	1

3. 按位异或(^)：两个数对应的位进行“异或”运算，生成新数：114514^1919810=1897488

   A	B	A^B
   0	0	0
   1	0	1
   0	1	1
   1	1	0

4. 按位取反(~)：1变0，0变1

   A	~A
   0	1
   1	0

5. 按位左移(<<)
6. 按位右移(>>)

3. 布尔代数