二进制与位运算

数的表示有很多种，我们最常用的是 $10$ 进制。也就是缝 $10$ 进位。在计算机中，数都是由二进制的形式存储的。而二进制的意思就是缝 $2$ 进位。因此二进制的数中，只有 $0$ 和 $1$

二进制

下面这个是一个二进制数 $101011$ , 我们把它转化成 $10$ 进制

$$(101011{)}_2$$

怎么转化, 我们从右往左看

$$\begin{array}{rl}(101011{)}_2& =1\ast 2^5+0\ast 2^4+1\ast 2^3+0\ast 2^2+1\ast 2^1+1\ast 2^0\\ & =1+2+8+32\\ & =43\end{array}$$

把一个十进制数转化成二进制

$$\begin{array}{rl}43/2=21...& 1\\ 21/2=10...& 1\\ 10/2=5...& 0\\ 5/2=2...& 1\\ 2/2=1...& 0\\ 1/2=0...& 1\end{array}$$

位运算

接下来我们介绍位运算。

与 and $\mathrm{\&}$

对于单个的二进制位来说

$$\begin{gathered} 1\mathrm{\&}1=1 \\ 1\mathrm{\&}0=0 \\ 0\mathrm{\&}1=0 \\ 0\mathrm{\&}0=0 \end{gathered}$$

对于两个整数的 操作，我们对于它二进制的每一位进行 操作得出来的结果

或 or $|$

$$\begin{gathered} 1|1=1 \\ 1|0=1 \\ 0|1=1 \\ 0|0=0 \end{gathered}$$

对于两个整数的 $|$ 操作，我们对于它二进制的每一位进行 $|$ 操作得出来的结果

异或 xor $\oplus$

$$\begin{gathered} 1\oplus 1=0 \\ 1\oplus 0=1 \\ 0\oplus 1=1 \\ 0\oplus 0=0 \end{gathered}$$

对于两个整数的 $\oplus$ 操作，我们对于它二进制的每一位进行 $$ 操作得出来的结果 s

x ^ y // 计算 x 异或 y

取反

$0$ 取反为 $1$

$1$ 取反为 $0$

~x // 对x取反

左移 <<

$x<<k$ 的意思是，把数 $x$ 的二进制表示向左移动 $k$ 位，右边补上 $0$ ,左边位数不够的话，左边舍弃

$$(101011{)}_2<<3=(101011000{)}_2$$

右移 >>

右移的意思是，把数的二进制位向右移动，左边补上0, 右边舍弃

$$(101011{)}_2>>4=(000010{)}_2$$

从数学的角度来说

$$\begin{gathered} x<<1=x\ast 2 \\ x>>1=x/2 \end{gathered}$$

常用结论

若干公式

$$a\oplus b\oplus b=a$$

$$a+b=(a\oplus b)+2\ast (a\mathrm{\&}b)$$

证明：把相加拆成进位和不进位

$$a+b=(a|b)+(a\mathrm{\&}b)$$

证明类似

两个数的大小只取决于二进制的最高不同位

简单练习：

例1、二进制转换

把一个 $281$ 转化成二进制

把一个 $(100101011{)}_2$转换成十进制

把 $(10010{)}_2$ 与 $(11011{)}_2$ 相加

例2、用位运算实现下面操作

判断一个数是奇数还是偶数

将一个数$\ast 2$

将一个数$/2$

得到 $2^k$

例3、编写下面函数

求某数二进制的第 $k$ 位是不是 $1$

把一个数的第 $k$ 位设置成 $1$

把一个数的第 $k$ 位设置成 $0$

计算二进制中 $1$ 的个数