进制与位运算

进制与位运算

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

二进制：由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)转换成二进制。

(3rightarrow 011) (7rightarrow 111) (4rightarrow 100) (1rightarrow 001) (6rightarrow110)

故((37.416)_8rightarrow(22222.10000111)_2).

? 将((5DF.9)_{16})转换成二进制。

(5rightarrow0101) (Drightarrow1101) (Frightarrow 1111) (9rightarrow 1001)

故((5DF.9)_{16}rightarrow (10111022222.1001)_2).

一般地，将(k)进制(a)的每一位乘以(k^i)次（其中(i)为当前位位数，个位位数为(0)），这样就可以将其转换为十进制。

例：将((11010.01)_2)转换为十进制。

((11010.01)_2=1times2^4+1times2^3+0times2^2+1times2^1+0times2^0+0times2^{-1}+1times2^{-2}=16+8+2+0.25=(26.25)_{10})

一般地，将十进制数(a)的整数部分不断除以(k)取余，倒序输出；小数部分不断乘(k)取整，这样就可以转换为(k)进制。

例：将((89.625)_{10})转换为二进制。

整数部分：

(89/2=44cdotscdots1)

(44/2=22cdotscdots0)

(22/2=11cdotscdots0)

(11/2=5cdotscdots1)

(5/2=2cdotscdots1)

(2/2=1cdotscdots0)

(1/2=0cdotscdots1)

小数部分：

(0.625times2=0.25+1)

(0.25times2=0.5+0)

(0.5times2=0.0+1)

故((89.625)_{10}=(1011001.101)_2).

计算机中数的表示

计算机中数位一般为8的倍数，我们规定最高位为符号位，0表示正数，1表示负数，这叫做机器数。这其中又分为原码，补码和反码。

原码：正常的符号数值表示。

例：设(x=7)，则([x]_原=00000111)；(x=-7)，则([x]_原=10000111).

反码：正数的反码是它本身，负数是对符号位以外各数取反。

例：设(x=-7)，则([x]_反=22222000).

补码：正数的补码是它本身，负数是它本身的反码加1。

例：设(x=-7)，则([x]_补=22222001).

综上，对于正数(x)，([x]_原=[x]_反=[x]_补)；对于负数(x)，([x]_补=[x]_反+1，[x]_反=[x]_原)数值位取反。

浮点数E(e)表示法：形如(1e7,3e6)的数，表示(1times10^7),(3times10^6)。

C++的位运算

按位与&：把两个数转化为二进制后逐位比较，两个对应数都为1时才为1

例：110&504=104

(begin{split}1101110&222221000&1101000end{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&222221000&222221110end{split})

按位异或^：把两个数转化为二进制后逐位比较，两个对应数不同时才为1

例：110^504=406

(begin{split}1101110&222221000&110010110end{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=22222010_补=22222001_反=10000110_原=-6)

~-7=6

(begin{split}&设x=(-7)_{10}=(-111)_2&[x]_原=10000111&[x]_补=22222001 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取整