目录
- 进制与位运算
- 二进制，八进制，十六进制和转换
- 计算机中数的表示
- C++的位运算
进制与位运算
二进制，八进制，十六进制和转换
二进制：由0和1组成，“逢二进一”。
八进制：由0，1，2，3，4，5，6，7组成，“逢八进一”。
C/C++中，在数字前加上前缀"0"表示八进制。
十六进制：由0，1，2，3，4，5，6，7，8，9，A(10)，B(11)，C(12)，D(13)，E(14)，F(15)组成，“逢十六进一”。
C/C++中，在数字前加上前缀"0x"表示十六进制。
可以发现，二进制和八进制，二进制和十六进制可以简便地进行转换，因为八进制一位对应二进制三位，十六进制一位对应二进制四位。
例：将\((37.416)_8\)转换成二进制。
\(3\rightarrow 011\) \(7\rightarrow 111\) \(4\rightarrow 100\) \(1\rightarrow 001\) \(6\rightarrow110\)
故\((37.416)_8\rightarrow(11111.10000111)_2\).
? 将\((5DF.9)_{16}\)转换成二进制。
\(5\rightarrow0101\) \(D\rightarrow1101\) \(F\rightarrow 1111\) \(9\rightarrow 1001\)
故\((5DF.9)_{16}\rightarrow (10111011111.1001)_2\).
一般地，将\(k\)进制\(a\)的每一位乘以\(k^i\)次（其中\(i\)为当前位位数，个位位数为\(0\)），这样就可以将其转换为十进制。
例：将\((11010.01)_2\)转换为十进制。
\((11010.01)_2=1\times2^4+1\times2^3+0\times2^2+1\times2^1+0\times2^0+0\times2^{-1}+1\times2^{-2}=16+8+2+0.25=(26.25)_{10}\)
一般地，将十进制数\(a\)的整数部分不断除以\(k\)取余，倒序输出；小数部分不断乘\(k\)取整，这样就可以转换为\(k\)进制。
例：将\((89.625)_{10}\)转换为二进制。
整数部分：
\(89/2=44\cdots\cdots1\)
\(44/2=22\cdots\cdots0\)
\(22/2=11\cdots\cdots0\)
\(11/2=5\cdots\cdots1\)
\(5/2=2\cdots\cdots1\)
\(2/2=1\cdots\cdots0\)
\(1/2=0\cdots\cdots1\)
小数部分：
\(0.625\times2=0.25+1\)
\(0.25\times2=0.5+0\)
\(0.5\times2=0.0+1\)
故\((89.625)_{10}=(1011001.101)_2\).
计算机中数的表示
计算机中数位一般为8的倍数，我们规定最高位为符号位，0表示正数，1表示负数，这叫做机器数。这其中又分为原码，补码和反码。
原码：正常的符号数值表示。
例：设\(x=7\)，则\([x]_原=00000111\)；\(x=-7\)，则\([x]_原=10000111\).
反码：正数的反码是它本身，负数是对符号位以外各数取反。
例：设\(x=-7\)，则\([x]_反=11111000\).
补码：正数的补码是它本身，负数是它本身的反码加1。
例：设\(x=-7\)，则\([x]_补=11111001\).
综上，对于正数\(x\)，\([x]_原=[x]_反=[x]_补\)；对于负数\(x\)，\([x]_补=[x]_反+1，[x]_反=[x]_原\)数值位取反。
浮点数E(e)表示法：形如\(1e7,3e6\)的数，表示\(1\times10^7\),\(3\times10^6\)。
C++的位运算
按位与&：把两个数转化为二进制后逐位比较，两个对应数都为1时才为1
例：110&504=104
\(\begin{split}1101110&\\111111000&\\1101000\end{split}\)
应用：
判断一个数\(n\)的奇偶：
bool Odd(int n)
{
return n&1;
}
将\(m\)对2的\(n\)次方取余：
int Mod(int m,int n)
{
return m&(n-1);
}
判断一个数\(n\)是否是\(2\)的幂：
bool Fac(int n)
{
return n>0&&(n&(n-1))==0;
}
按位或|：把两个数转化为二进制后逐位比较，两个对应数有一个1就为1
例：110|504=510
\(\begin{split}1101110&\\111111000&\\111111110\end{split}\)
按位异或^：把两个数转化为二进制后逐位比较，两个对应数不同时才为1
例：110^504=406
\(\begin{split}1101110&\\111111000&\\110010110\end{split}\)
注：异或运算的逆运算是其本身，即(a ^ b) ^ b = a
交换两数\(a,b\)：
void Swap(int &a,int &b)
{
a=a^b;
b=a^b;
a=a^b;
}
取反~：对一个数的补码二进制位取反
例：
~5=-6
\(\begin{split}&设x=(5)_{10}=(101)_2\\&[x]_原=00000101\\&[x]_补=00000101\\ \end{split}\)
~\(x=11111010_补=11111001_反=10000110_原=-6\)
~-7=6
\(\begin{split}&设x=(-7)_{10}=(-111)_2\\&[x]_原=10000111\\&[x]_补=11111001\\ \end{split}\)
~\(x=00000110_补=00000110_反=0000110_原=6\)
左移<<右移>>：将一个数转换成二进制后向左(右)移动\(i\)位
例：5<<1=10，5>>1=2
\(\begin{split}5=00000101_{(2)}&\\5<<1=00001010_{(2)}&\\5>>1=00000010_{(2)}&\end{split}\)
应用：
\(n<<i\)相当于\(n\)乘\(2\)的\(i\)次方
\(n>>i\)相当于\(n\)除以\(2\)的\(i\)次方（\(n\)都要为整数)
注：右移为严格向下取整，\为向0取整