进制

12 个物品被称为 1 打，12 打被称为 1 罗，12 罗被称为 1 格。请问：

1. 15 个是几打几个？
2. 6775 个是几格几罗几打？
3. 2 打 3 个是多少个？
4. 1 格 9 罗 8 打 10 个是多少个？

以上的“几”均是不小于 0 且小于 12 的整数

在十六进制下的 ABCD 等于十进制的多少？

十进制下的 114514 在十六进制中表示为什么？

二进制和其他进制的原理并没有什么不同，但是二进制的特殊之处在于能使用最少的符号数量（0 和 1）表示出所有的整数

二进制下的 10101101 是十进制的多少？

十进制下的 89 在二进制下如何表示？

由于二进制中只使用 0 和 1 两种符号，非常适合使用电子方式实现运算过程

例：P1143 进制转换

#include <cstdio>
#include <cstring>
const int N = 40;
char num[N];
int ans[N];
int char_to_int(char ch) { // 单个数位符号转成数字
    return ch >= '0' && ch <= '9' ? ch - '0' : ch - 'A' + 10;
}
char int_to_char(int x) { // 数字转成单个数位符号
    return x < 10 ? '0' + x : x - 10 + 'A';
}
int main()
{
    int n, m;
    scanf("%d%s%d", &n, num, &m);
    int dec = 0, len = strlen(num);
    // 原数转换为十进制
    for (int i = 0; i < len; i++) dec = dec * n + char_to_int(num[i]);
    len = 0;
    // 转换为m进制
    while (dec != 0) {
        ans[len] = dec % m; dec /= m; len++;
    }
    // 输出转换好的数字
    for (int i = len - 1; i >= 0; i--) printf("%c", int_to_char(ans[i]));
    printf("\n");
    return 0;
}

补充：一位十六进制数码对应 4 位数的二进制数码，所以将十六进制和二进制之间相互转换时可以不用十进制为中间跳板，直接进行翻译即可（二进制需要四位四位分组，必须从右向左分组）。例如，二进制数 1010110111 经过分组可以变为 0010 1011 0111，直接口算得到 2B7，反之亦然

二进制与数据存储

计算机内存只能一位一位地存储 0 和 1，那么内存中如何存储各种数据类型？
假设在 C++ 中定义了这些变量：

int a = 233;
int b = -233;
float c = 3.14;
char d[4] = "Ha!";

上图表现了计算机内存中变量的存储方式，“0x”是十六进制数字前的前缀

内存非常大，如果希望定位到某个变量，就需要知道这个变量所在的地址。假如在一台 32 位计算机中，地址是 32 位二进制数，可以缩写为 8 位十六进制。一个 0 或 1 的数码被称为一位，8 位被称为一字节，也就是 1B（Byte）

一个 int 类型或 float 类型的变量占用 32 位空间。十进制数字 233 转换为二进制数字为 11101001，所以 233 存储在内存中，在低位（右边）填入 11101001，而左边（高位）用 0 填充。十进制的 -233 是一个负数，在内存中就会表示为 1···100010111，高位是用 1 填充的。而浮点数比较复杂，需要将十进制的浮点数转换为二进制的浮点数，然后在内存中分别记录符号、指数和有效数字

一个 char 类型的变量占用 8 位，大小为 4 的 char 类型数组占用 32 位。将这个数组中的每个原数的 ASCII 码转换为二进制后直接存入内存中。例如，'H' 的 ASCII 码值为 72，'a' 的 ASCII 码值为 97，'!' 的 ASCII 码值为 33；字符串最后还有一个 '\0'，对应的值是 0

定义一个变量，就会为这个变量准备一块内存空间，并记录这个空间的起始地址，当访问到这个变量的时候，就会根据地址在内存中找到这个变量的值

有些变量类型也有无符号数，例如 unsigned int 类型，这个类型和 int 类型一样占用 32 位，但是以放弃存储正负符号为代价，可以存储 \(0\) 到 \(2^{32}-1\)

计算机中还有其他表示数据大小的单位，比如 1KB 是 \(2^{10}=1024\) 字节，1MB 是 \(2^{20}\) 字节，1GB 是 \(2^{30}\) 字节

负数转二进制

考虑到 int 占用 32 位太长，这里使用只占 8 位的 signed char 类型举例，57 用二进制表示为 00111001（补足 8 位）。要表示一个负数，那就要占用最高位的一位来表示正负，0 表示非负，1 表示负数

• 用除了第一位的数字表示这个负数的绝对值，第一位变成 1，这样 -57 表示为 10111001，这种表示方式称为原码。一般计算机不使用这种方式来表示负数

• 将负数的绝对值对应的数全部取反，由 1 变为 0，由 0 变为 1，这样 -57 表示为 11000110，这种表示方式称为反码。使用反码有一个问题：0 有两种表示方式（全 0 和全 1），所以也不常用

• 先计算负数的反码，然后加 1，这样 -57 表示为 11000111，这是计算机使用的表示负数的方法，被称为补码。这种表达方式下，0 只有 1 个，全 1 代表 -1

有了补码这种表示负数的方式，计算机就可以很方便地计算二进制减法了。例如要计算 66-57 时，可以认为是 66+(-57)。66 的二进制是 01000010，-57 的二进制是 11000111，列竖式累加

  ..    ..  （进位记号）
  0100 0010
+ 1100 0111
-----------
 10000 1001

由于这个数字溢出了 8 位，所以只取低位数的 8 位，得到的答案是 00001001，也就是十进制下的 9。补码这种非常巧妙的设计使得计算机可以化减为加。但是谈论到补码时必须要确定总位数，例如 8 位下的有符号整数实质上是在 -128~127 之间形成了一个环

使用 memset 给 int 数组初始化时，如果想要精准的初始化，只能初始化为 0 或 -1（而给一个其他数字，则不会将数组初始化为这个数字），因为 memset 只能将一片数组区域的每一个字节初始化为这个数字（小于 255），而一个 int 是由 4 字节组成的，所以只能填充成全 0（最后的值还是 0）或者全 1（最后的值是 -1），所以通常只使用 memset(a, 0, sizeof(a)) 或者 memset(a, -1, sizeof(a)) 这样的写法将整个数组初始化为 0 或 -1。而如果写出 memset(a, 3, sizeof(a)) 这样的代码时，实际上是把每个元素初始化成了 0x03030303

小数转二进制

将实数从十进制转换为二进制，可以将整数部分和实数部分分别处理。如 3.14，整数部分的 3 是二进制的 11；而小数部分 0.14 如下图所示处理

将原来的小数数字，每次都乘 2，如果得到的整数部分是 1，则答案记录一个 1，并去掉这个整数部分，然后继续运算；如果得到的结果中的整数部分还是 0，那么答案记录一个 0，继续计算。因此 3.14 表示为二进制数是 11.00100011···，在二进制下是一个无限小数。因此，这就是计算机浮点数类型无法精确表示很多实数的原因

那么，如何将一个二进制小数转换成十进制呢？例如 101.101，同样将整数部分和小数部分分开，整数部分十进制是 5，小数部分的计算方式和整数转换方式差不多：\(1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} = 0.625\)，所以整个数的十进制就是 5.625

逻辑命题

在逻辑学中，命题指的是判断一件事情的陈述句，且有明确的真伪。一般用 1 表示真命题，用 0 表示伪命题

多个命题可以进行复合，进行与、或、非、异或等操作

1. 或：\(A \vee B\)，两个命题中至少有一个真命题时，其复合命题为真

2. 与：\(A \wedge B\)，两个命题必须全为真命题，其复合命题才是真命题

3. 非：\(\lnot A\)，将原命题取反

4. 异或：\(A \oplus B\)，两个命题一真一假时复合命题为真，等价于 \((A \wedge \lnot B) \vee (\lnot A \wedge B)\)

有时为了简化逻辑表达式，可以将或运算变成加号，与运算变成乘点（甚至可以省略），而非运算变成上划线。例如，\(\lnot ((A \wedge \lnot B) \vee (\lnot A \wedge B))\) 可以表示为 \(\overline{A \overline{B} + \overline{A} B}\)

之所以能将或运算变成加号、与运算变为乘号，是因为逻辑运算有和普通代数运算有类似的性质，而且与运算的优先级高于或运算

1. 交换律：AB=BA, A+B=B+A

2. 结合律：(AB)C=A(BC), (A+B)+C=A+(B+C)

3. 分配律：\(A(B+C)=AB+AC\)

除此之外，还有一些显然的性质：

4. A+1=1, 0A=0

5. \(AA=A, A+A=A, A + \overline{A} = 1\)

还有一个非常重要的德·摩根定律，使得与运算和或运算可以在一定条件下互相转化：

6. \(\overline{A} + \overline{B} = \overline{AB}, \overline{A} \cdot \overline{B} = \overline{A+B}\)

以上逻辑运算性质可以化简一个复杂的逻辑表达式，便于求出逻辑表达式的值

化简逻辑表达式为最简与或式。由“与运算”连接的一组变量（或者带非运算的变量）叫“与项”，将一些“与项”用“或运算”连接的表达式为与或式。最简与或式是指与项数量最少，同时每项数量也最少的与或式

编程时有时会出现一些比较复杂的条件判断语句，可以使用化简逻辑运算的方法与技巧来化简判断语句，或者明确有些判断语句是等效的。例如 !((x <= 0 || x > 5) && (y <= 0 || y > 10)) 等价于 x > 0 && x <= 5 || y > 0 && y <= 10

位运算

#include <cstdio>
int main()
{
    int a = 85, b = 51;
    int p = a & b;
    int q = a | b;
    int r = a ^ b;
    int s = ~a;
    int u = a << 2;
    int v = a >> 3;
    printf("%d %d %d %d %d %d\n", p, q, r, s, u, v);
    return 0;
}

运行程序，得到的结果是

17 119 102 -86 340 10

这里涉及到了 C++ 中的位运算，也就是直接对整数在内存中的二进制位进行按位操作

& 运算是按位与，注意只有一个符号，&& 是逻辑与。该符号将前后两个操作数按位对齐，然后每一位上都进行与运算，最后得到位运算的结果。例如，85 的二进制数为 1010101，51 的二进制数为 110011，计算过程是这样的（int 类型是 32 位二进制数）：

   a 0000 0000 0000 0000 0000 0000 0101 0101
&  b 0000 0000 0000 0000 0000 0000 0011 0011
--------------------------------------------
   p 0000 0000 0000 0000 0000 0000 0001 0001 

可以发现，每一位都进行了与运算，最后得到的结果是 10001，也就是十进制的 17

| 符号是按位或；^ 符号是按位异或。异或运算符的优先级高于按位或运算，但是低于按位与运算

而 ~ 符号是取反；<< 符号是按位左移；>> 符号是按位右移，它们运行的机理是这样的：

   a: 00000000000000000000000001010101
  ~a: 11111111111111111111111110101010
a<<2: 00000000000000000000000101010100
a>>3: 00000000000000000000000000001010

可见，取反就是将这个数字的二进制数 0 变 1、1 变 0，然后根据前面介绍的补码，就可以知道转换后的数字。对于带符号整数来说，~a 的值和 -a-1 的值是一样的。而左移是将这个二进制数的所有位数往左移动指定的位数，右边用 0 补齐，左边截掉。而右移则是将这个二进制数的所有位数往右移动指定的位数，右边截掉。右移时，如果原数是非负数，则左边补 0，否则左边补 1，因此 a<<n 等于 a 乘 2 的 n 次方，a>>n 等于 a 整除 2 的 n 次方

已知一个正整数变量 a，对这个数的二进制数列进行以下操作，尝试用位运算符号写出操作方式：

1） 将最后一位的右边加上一个 1，例如 101 变为 1011

2）将最后一位变为 0，例如 1010 或者 1011 处理后都变成 1010

3）取末 5 位序列，例如 11011010 处理后得到 11010

4）去掉序列中最右边的 1 的左边所有数字，例如 11011000 取到右边的 1000