Debug 2025 Freshman - C Programing

Chapter05 - Bitwise operation and Basic Math

Number systems

我们都知道，计算机底层当中所有的数字都是以二进制存储的。

我们生活中使用的十进制是逢十进一，而二进制的意思就是逢二进一，也就是说二进制中有。

为什么要这样使用呢？我们人有十个手指，因此使用十进制较为符合直觉。计算机中只有高电平和低电平，因此使用二进制表示数据更为方便。

我们之前的作业有提到过如何将一个十进制整数按位拆开，得到这个十进制整数的每一位。

const int N = 1e4;
int s[N + 10];
int toDex(int num){
  	// 当前位
    int digit = 0;
    while (num > 0) {
      	// 获取到当前数的个位
        s[digit++] = num % 10;
      	// 通过整除，将当前数的十位转换为个位，方便下一次获取
        num /= 10;
    }
    return digit;
}

类比十进制的转换，我们就可以写出十进制转换为二进制的算法，当然也适用于其他进制

const int N = 1e4;
int s[N + 10];
int toBin(int num){
    int digit = 0;
    while (num > 0) {
      	// 只是将上文的 mod 和整除 10 换成了 2
        s[digit++] = num % 2;
        num /= 2;
    }
    return digit;
}

而将二进制转换为十进制也同样简单，只需要根据定义转换即可。

const int N = 1e4;
int s[N + 10];
int toNum(int digit){
    int res = 0;
    for(int i = digit; i >= 0; i--){
        res = res * 2 + s[i];
    }
    return res;
}

为了方便区分，我们在 C 语言中通过在数前面加上 0b 表示一个二进制数字，其中 b 表示二进制的英文 binary 也缩写作 bin。

我们叫 0b1011010 这样的二进制数的每一位叫做一个 位（bit）。将每一个 bit 分开来表示进行计算显然不够系统，于是计算机内将 8 个 bit 组成一个 byte，称为字节（byte）。

另外我们注意到当一个二进制数只有首位是 1 其余位是 0 的时候，这个二进制的值等于 $ 2^n $ ，其中 $ n $ 为任意整数。

为了方便表示，科学家发明了 16 进制和 8 进制，用 A B C D E F 表示 16 进制的不能用阿拉伯数字表示的另外六位。

相应的，十进制也缩写为 dec（decimal），十六进制缩写为 hex（hexadecimal），八进制缩写为 oct（octal）

同样，在 C 语言中，我们使用 0x 开头表示一个十六进制数，使用 0 开头表示一个八进制数。

这样我们使用十六进制表示一个 Byte 就很容易了。例如 0xFF 就表示二进制为 0b11111111。

下面这段代码可以体现这几种进制的转换：

int bin = 0b11111111;
int hex = 0xff;
int oct = 0377;
int dec = 255;
printf("bin = %d, hex = %d, oct = %d, dec = %d", bin, hex, oct, dec);

尽管定义时的写法不同，但是他们打印出的十进制值都是一样的。

bin = 255, hex = 255, oct = 255, dec = 255

你会发现二进制和十六进制表示一个 Byte 的时候形式上是高度对齐的，在嵌入式开发当中我们也经常会使用二位十六进制表示一个 Byte。

在 printf 中，我们也可以使用 %x 和 %o 分别表示十六进制和八进制输出。

在你系统的计算器中，可以切换到程序员模式，就能很方便地在这几个进制下进行计算。

Bitwise Operations

由于二进制是计算机系统中最为常见的表示，相比于十进制的加减乘除和取模运算，C 语言提供了更为丰富的操作符，用来直接操作一个数的二进制。

C 语言中的位运算（bitwise operation）就是直接对整数的二进制位进行操作，而不是像普通算术那样按数值计算。这类操作在嵌入式、加密、图像处理和性能优化中非常常见，因为它们比算术运算速度更快，也更接近硬件本身。

C 语言提供了六种基本的位运算符：

1. 按位与 &

   两个二进制位都为 1 时结果为 1，否则为 0。 例子：

   // 12
   int a = 0b1100;
   // 10
   int b = 0b1010;
   // 1000 -> 8
   int c = a & b;
   

   可以理解为：每一位都检查“我和你都亮吗？”，只有都亮才亮。

2. 按位或 |

   两个二进制位只要有一个为 1，结果就是 1。 例子：

   // 1110 -> 14
   int c = a | b;
   

   类似于：“我或者你亮就亮”。

3. 按位异或 ^

   两个二进制位不同则为 1，相同则为 0。 例子：

   // 0110 -> 6
   int c = a ^ b;
   

   可以理解为“谁和谁不一样就亮”，常用于加密或交换两个变量而不使用临时变量。

4. 按位取反 ~

   将二进制位全部取反，0 变 1，1 变 0。 例子：

   // 12
   int a = 0b1100;
   // -13 这个涉及到数据的二进制表示中补码的知识，感兴趣的同学可以自行了解一下
   int c = ~a;
   

   注意，C 语言中整数是用补码存储的，所以取反后数值看起来是负数。

5. 左移 <<

   将二进制整体向左移动若干位，右边补 0，相当于乘以 $ 2^n $。 例子：

   // 0000 0011
   int a = 3;
   // 0000 1100 -> 12
   int c = a << 2;
   

   左移 1 位就相当于乘以 2，左移 n 位就相当于乘以 $ 2^n $。

6. 右移 >>

   将二进制整体向右移动若干位，左边补 0（无符号数）或符号位（有符号数），相当于除以 $ 2^n $（整除）。 例子：

   // 0000 1100
   int a = 12;
   // 0000 0011 -> 3
   int c = a >> 2;
   

   右移 1 位就相当于除以 2（取整），右移 n 位相当于除以 $ 2^n $。

当然在运算符后面加上 = 符号，就可以用类似 += 符号的方法操作并进行赋值。

Basic Math

有关数学的比较拓展和进阶的部分，除了第一节以外，大家可以选看

位运算的高级用法

$ 2^n $ 可以表示为 1 << n，这种写法相比直接计算更为快速（从计算 n 次变为计算一次）

根据位运算的性质，我们可以写出直接操作一个数二进制位的写法：

// 二进制 1000
int x = 8;
// 提取第 2 位
int bit = (x >> 2) & 1;
// 设置第 2 位为 1
x |= (1 << 2);
// 清除第 2 位
x &= ~(1 << 2);
// 取反第 2 位
x ^= (1 << 2);

同样也可以通过类似的方法重构上面的十进制转二进制和二进制转十进制的代码。

模运算的性质

1. 加减法：(a + b) % m = [(a % m) + (b % m)] % m 减法同理
2. 乘法：(a × b) % m = [(a % m) × (b % m)] % m
3. 幂：(a^n) % m = [(a % m)^n] % m

也就是说我们常常会遇到例如 a x b 超过了 int 的表示范围的情况，如果在某个运算中取模之后运算性质不变，我们可以选择将取模的操作拆分开来，避免爆 int 的情况

异或运算的性质

异或有两条重要性质

1. a ^ a = 0即一个数异或它本身得到0
2. a ^ b == b ^ a即在一串异或运算中，改变异或的顺序结果不变

根据这以上两条性质，可以进行数据的去重。

例如，给定一个数组，除了其中某一个数以外，其他所有的数都是成对出现的。

要找出这个数，我们可以直接对整个数组进行异或，最后得到的值就是我们要找的数。

int n;
scanf("%d", &n);
int ans = 0;
for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    ans ^= x;
}

Bitmask

位掩码，是状压枚举的核心。

回顾我们高中学习的二项分布，对于每一个事件只有发生和不发生这两种情况。

那么这样的事件我们很容易用二进制表示，因此可以将这样的事件转换为使用二进制表示。

Bitmask 是一种思想，具体的应用有很多，大家可以自行学习。