Class 2

• 进制转换

   我们一般计算中常用 $10$ 进制，而电脑中的运输使用 $2$ 进制。还有许多进制（常见的如 $8$ 进制、$16$ 进制）。

  $\large1.$ $10$ 进制转 $k$ 进制。

   代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,k; char digit[35];
int d_change() {
    int m=0;
    while(n) {
        int r=n%k;
        if(r<10) digit[++m]=r+'0'; //10 -> 9/8...
        else digit[++m]=(r-10)+'A'; //10 -> 11/12...
        n/=k;
    }
    for(int i=1,j=m;i<=j;i++,j--) 
        swap(digit[i],digit[j]);
    return m;
}
int main() {
 	scanf("%d%d",&n,&k);
 	int len=d_change();
 	for(int i=1;i<=len;i++)
	 	printf("%c",digit[i]);
	return 0;
}
//code by TheCedar

主要思路是短除法，每次都将原数 $n$ 对 $k$ 取余，用 $digit$ 数组存储下来，最后倒序输出即可。

  $\large2.$ $k$ 进制转 $10$ 进制。

   其实就是 $10$ 进制转 $k$ 进制的逆过程，其实是一样的。

• 原码，反码，补码及其之间的相互运算

   如下题：求整数 $-2022$ 的 $16$ 位二进制补码。

$-2022_{O} = \texttt{1000 0111 1110 0110}$

$-2022_{I} = \texttt{1000 1000 0001 1001}$

$-2022_{C} = \texttt{1000 1000 0001 1010}$

注：
原码： Original Code 上面简称 $O$

反码：Inverse Code 上面简称 $I$

补码：Complementary code 上面简称 $C$

   $\therefore -2022$ 的 $16$ 位补码为 $\texttt{1000 1000 0001 1010}$。

• 位运算的初步认识与使用

Example：位运算的一些特殊用法。

   1. 判断奇偶性。

if(x&1) cout<<"even"; //奇数
else cout<<"odd"; //偶数

   2. 判断整数 $x$ 的二进制中倒数第 $i$ 位是否为 $1$。

if(x&(1<<(i-1))) ... // x 的二进制中第 i 位为 1.
else ... // x 的二进制中第 i 位为 0.

   3. 将整数 $x$ 的二进制倒数第 $i$ 位变为 $1$

x=x|(1<<(i-1));

   4. 将整数 $x$ 的二进制中最后一个 $1$ 变为 $0$

x=x&(x-1);

• 计数基本原理

   如下题：由 $1,1,2,2,3$ 这五个数字组成不同的三位数有几种？

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \texttt{--- From CSP-J, 2021.}$

   易得，总共有一下几种序列，每个序列能组合出的三位数数都可以是符合题意的三位数，统计这些三位数的个数即可。

$\left< 1,2,3 \right> \to 6$

$\left< 1,1,2 \right> \to 3$

$\left< 1,1,3 \right> \to 3$

$\left< 2,2,1 \right> \to 3$

$\left< 2,2,3 \right> \to 3$

$\therefore 总方案数 = 6+3*4= 18 种$。

• 排列 & 组合

   如下题 $6$ 个人，两个人组一队，总共组成三队，不区分队伍的编号，问不同的组队情况有几种。

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \texttt{--- From CSP-J, 2021.}$

   易得，总方案数为如下式子：

$\dfrac{C_6^2 \times C_4^2 \times C_2^2}{A_3^3} = \dfrac{15 \times 6 \times 1}{6} = 15$