计算机存储整型

1. 原码（Sign-Magnitude）

定义：最高位表示符号位（0为正，1为负），其余位表示数值的绝对值。

示例（8位二进制）：

+5：00000101
-5：10000101

2. 反码（Ones' Complement）

定义：

• 正数：与原码相同。
• 负数：符号位不变，数值位按位取反（0变1，1变0）。

示例：

+5：00000101（同原码）
-5：11111010

3. 补码（Two's Complement）

定义：

• 正数：与原码相同。
• 负数：符号位不变，数值位取反后加 1（即反码 +1）。

示例：

+5：00000101
-5：
原码：10000101
数值位取反：11111010（反码）
加 1：11111011（补码）

位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 6 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

为了方便叙述，下文中省略「按位」。

与、或、异或

这三者都是两数间的运算，因此在这里一起讲解。

它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

运算	运算符	数学符号表示	解释
与	$\&$	$\&$、$\operatorname{and}$	只有两个对应位都为 1 时才为 1
或	$|$	$\mid$、$\operatorname{or}$	只要两个对应位中有一个 1 时就为 1
异或	^	$\oplus$、$\operatorname{xor}$	只有两个对应位不同时才为 1

注意区分逻辑与（对应的数学符号为 $\wedge$）和按位与、逻辑或（$\vee$）和按位或的区别。网络中的资料中使用的符号多有不规范之处，以上下文为准。

异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即 $a \oplus b \oplus b = a$。

举例

$$5 = (101)_2 \\ 6 = (110)_2 \\ 5 \operatorname{\&} 6 = (100)_2 = 4 \\ 5 \operatorname{|} 6 = (111)_2 = 7 \\ 5 \oplus 6 = (011)_2 = 3 \\$$

取反

取反是对一个数 num 进行的位运算，即单目运算。

取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把 num 的二进制补码中的 0 和 1 全部取反（0 变为 1，1 变为 0）。有符号整数的符号位在 ~ 运算中同样会取反。

补码：在二进制表示下，正数和 0 的补码为其本身，负数的补码是将其对应正数按位取反后加一。

举例（有符号整数）

$$\begin{aligned} 5 &= (00000101)_2 \\ \text{~}5 &= (11111010)_2 = -6 \\ -5 \text{ 的补码} &= (11111011)_2 \\ \text{~}(-5) &= (00000100)_2 = 4 \\ \end{aligned}$$

左移和右移

num << i 表示将 num 的二进制表示向左移动 i 位所得的值。

num >> i 表示将 num 的二进制表示向右移动 i 位所得的值。

举例

$$\begin{aligned} 11 &= (00001011)_2 \\ 11 << 3 &= (01011000)_2 = 88 \\ 11 >> 2 &= (00000010)_2 = 2 \\ \end{aligned}$$

移位运算中如果出现如下情况，则其行为未定义：

• 右操作数（即移位数）为负值；
• 右操作数大于等于左操作数的位数；

简单应用

取出整数对应二进制每一位

$(12)_{10} = (1100)_2$

判断$(1100)_2$ 最低位是否为1

$(1100)_2\&(1)_2$

判断$(1100)_2$ 最次低位是否为1

$(1100)_2\&(10)_2$

$\dots$

$(1)_2 = (1<<0)$

$(10)_2 = (1<<1)$

$(100)_2 = (1<<2)$

int n;
cin>>n;
for(int i=31; i>=0; i--){
  if(n&(1<<i)){
    cout<<1;
  }else{
    cout<<0;
  }
}
  

取出整数连续几位二进制

$(17)_{10} = (10001)_2$

从低位往高位每四位取一下

$(10001)_2 \& (1111)_2$

$(1111)_2 = (f)_{16}$

17 & 0xf 取出四位

去掉最后4位 $17>>4$

int n;
while(n){
  int t = n&0xf;
  cout<<t;
  n=n>>4;
}

例题

B3870 P9496