二进制与位运算

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

二进制

下面这个是一个二进制数 \(101011\) , 我们把它转化成 \(10\) 进制 \[ (101011)_2 \] 怎么转化, 我们从右往左看 \[ \begin{aligned} (101011)_2&= 1*2^5 +0*2^{4}+1*2^{3}+0*2^{2}+1*2^{1}+ 1*2^{0}\\ &=1+2+8+32 \\ &=43 \end{aligned} \] 把一个十进制数转化成二进制 \[ \begin{aligned} 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{aligned} \]

位运算

接下来我们介绍位运算。

与 and \(\&\)

对于单个的二进制位来说 \[ 1 \& 1=1 \\ 1\& 0 = 0 \\ 0 \& 1 = 0 \\ 0 \& 0 = 0 \] 对于两个整数的 $ & $ 操作，我们对于它二进制的每一位进行 $ &$ 操作得出来的结果

或 or \(|\)

\[ 1 | 1=1 \\ 1 | 0 = 1 \\ 0 | 1 = 1 \\ 0 | 0 = 0 \]

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

异或 xor \(\oplus\)

\[ 1 \oplus1 = 0 \\ 1 \oplus 0 = 1 \\ 0 \oplus 1 =1 \\ 0 \oplus 0 = 0 \]

对于两个整数的 \(\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 \] 从数学的角度来说 \[ x<<1 = x*2 \\ x>>1 = x /2 \]

常用结论

若干公式

\[ a \oplus b \oplus b = a \\ \]

\[ a+b=(a\oplus b)+ 2*(a \&b) \]

证明：把相加拆成进位和不进位 \[ a+b=(a|b) + (a\&b) \] 证明类似

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

简单练习：

例1、二进制转换

把一个 \(281\) 转化成二进制

把一个 \((100101011)_2\)转换成十进制

把 \((10010)_2\) 与 \((11011)_2\) 相加

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

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

将一个数\(*2\)

将一个数\(/2\)

得到 \(2^k\)

例3、编写下面函数

求某数二进制的第 \(k\) 位是不是 \(1\)

把一个数的第 \(k\) 位设置成 \(1\)

把一个数的第 \(k\) 位设置成 \(0\)

计算二进制中 \(1\) 的个数