进制与位运算

进制与位运算

二进制，八进制，十六进制和转换

二进制：由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(@R_616_9293@)
{
    return n&1;
}

将\(m\)对2的\(n\)次方取余：

int Mod(int m,@R_616_9293@)
{
    return m&(n-1);
}

判断一个数\(n\)是否是\(2\)的幂：

bool Fac(@R_616_9293@)
{
    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取整