机器数与位运算

一.机器数和真值

1.机器数

一个数在计算机中的二进制表示形式,叫做这个数的机器数

机器数是带符号的,在计算机用一个数的最高位存放符号,正数为0,负数为1

比如,十进制中的数 +3 ,计算机字长为8位,转换成二进制就是0000 0011.如果是 -3,就是1000 0011

那么,这里的 00000011 和 10000011 就是机器数

2.真值

因为第一位是符号位,所以机器数的形式值就不等于真正的数值

例如上面的有符号数 10000011,其最高位1代表负,其真正数值是 -3 而不是形式值131（10000011转换成十进制等于131

所以,为区别起见,将带符号位的机器数对应的真正数值称为机器数的真值

例如：0000 0001的真值 = +000 0001 = +1,1000 0001的真值 = –000 0001 = –1

二. 原码, 反码, 补码的基础概念和计算方法

在探求为何机器要使用补码之前, 让我们先了解原码, 反码和补码的概念

对于一个数, 计算机要使用一定的编码方式进行存储. 原码, 反码, 补码是机器存储一个具体数字的编码方式

1.原码

原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制:

[+1]原=0000 0001 [-1]原=1000 0001

第一位是符号位. 因为第一位是符号位, 所以8位二进制数的取值范围就是:

[1111 1111 , 0111 1111]即[-127 , 127]

2.反码

反码的表示方法是:

正数的反码是其本身

负数的反码是在其原码的基础上, 符号位不变,其余各个位取反

[+1] = [00000001]原 = [00000001]反

[-1] = [10000001]原 = [11111110]反

3.补码

补码的表示方法是:

正数的补码就是其本身

负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1. (即在反码的基础上+1)

[+1] = [00000001]原 = [00000001]反 = [00000001]补

[-1] = [10000001]原 = [11111110]反 = [11111111]补

4.为何要使用反码/补码?

1.用于负数减法
计算机操作指令简化,1-1可以表示为 1+(-1),即加法替代减法
1.利用原码计算 -> 1(0000 0001)原 + -1(1000 0001)原 = (1000 0010)原 = -2 计算不符
2.利用反码计算 -> 1(0000 0001)反 + -1(1111 1110)反 = (1111 1111)反 = (1000 0000)原 = -0 计算不符
3.利用补码计算 -> 1(0000 0001)补 + -3(1111 1010)补 = (1111 1011)补 = (1000 0011)原 = -2 计算正确
反码/补码的出现解决了0的符号位和正确计算

三.运算符

1111 1111 1111 1111 1111 1111 1111 1000
1000 0000 0000 0000 0000 0000 0000 0110

1.按位与运算符(&)

1.运算规则

参加运算的两个数据,按二进制位进行”与”运算

运算规则:0&0=0; 0&1=0; 1&0=0; 1&1=1;

即:两位同时为”1”,结果才为”1”,否则为0

例如:

3&4 即0000 0011& 0000 0100 = 0000 0000 因此,3&4的值为0

3&5 即0000 0011& 0000 0101 = 0000 0001 因此,3&5的值为1

注:负数按补码形式参加按位与运算,结果如果是负数也以补码形式呈现

例如:

-3 原码1000 0011 补码 1111 1101

-4 原码1000 0100 补码 1111 1100

-3&-4 即1111 1101&1111 1100 =1111 1100 补码1000 0100 因此-3&-4的值为-4

2.”与运算”的特殊用途

(1)清零.如果想将一个单元清零,即使其全部二进制位为0,只要与一个各位都为零的数值相与,结果为零

例如:n&0=0

(2)取一个数中指定位

方法：取数字n中特定的位,设置一个数字该数的对应位为1,其余位为零,此数与n进行”与运算”可以得到n中的特定位

例如:设n=1110 0010

取n的后4位,用 n & 0000 1111 = 0000 0010 即可

2.按位或运算符(|)

1.运算规则

参加运算的两个对象,按二进制位进行”或”运算

运算规则: 0|0=0; 0|1=1; 1|0=1; 1|1=1；

即:参加运算的两个对象只要有一个为1,其值为1

例如:

3|4 即0000 0011 | 0000 0100 = 0000 0111 因此,3|4的值为7

3|5 即0000 0011 | 0000 0101 = 0000 0111 因此,3|5的值为7

注:负数按补码形式参加按位或运算,结果如果是负数也以补码形式呈现

-3 原码1000 0011 补码 1111 1101

-4 原码1000 0100 补码 1111 1100

-3|-4 即1111 1101|1111 1100 = 1111 1101 补码 1000 0011 因此-3|-4的值为-3

2.”或运算”特殊用途

(1)常用来对一个数据的特定位置为1.

方法:将数字n中特定位置为1,设置一个数字该数的对应位为1,其余位为零.此数与n进行”或运算”可使n中的特定位置为1

例如:将n=1110 0000的后4位置为1,用n| 0000 1111 = 1100 1111即可

3.异或运算符(^)

1.运算规则

参加运算的两个数据,按二进制位进行”异或”运算.

运算规则:0^0=0; 0^1=1; 1^0=1; 1^1=0；

即:参加运算的两个对象,如果两个相应位为”异”(值不同),则该位结果为1,否则为0.

例如:

3^4 即0000 0011 ^ 0000 0100 = 0000 0111 因此,3^4的值为7

3^5 即0000 0011 ^ 0000 0101 = 0000 0110 因此,3^5的值为6

注:负数按补码形式参加按位与运算,结果如果是负数也以补码形式呈现

例如:

-3 原码1000 0011 补码 1111 1101

-4 原码1000 0100 补码 1111 1100

-3^-4 即1111 1101^1111 1100 =0000 0001 因此-3&-4的值为1

2.”异或运算”的特殊用途

(1)对一个数字特定位翻转,设置一个数字该数的对应特定位为1,其余位为零,此数与进行”异或运算”即可

例如:n=1110 1110,使n后4位翻转,用n ^0000 1111 = 1110 0001即可

(2)与0相异或,保留原值,n ^ 00000000 = 1010 1110.

下面重点说一下按位异或,异或其实就是不进位加法,如1+1=0,0+0=0,1+0=1.

异或的几条性质:

1、交换律

2、结合律（即(ab)c == a(bc))

3、对于任何数x,都有xx=0,x0=x

4、自反性: abb=a^0=a;

异或运算最常见于多项式除法,不过它最重要的性质还是自反性

即A XOR B XOR B = A,即对给定的数A,用同样的运算因子(B)作两次异或运算后仍得到A本身

应用举例1:

例如设有A,B两个变量,存储的值分别为a,b,则以下三行表达式将互换他们的值

a=a^b;

b=b^a;

a=a^b;

应用举例2(综合&和^):

一系列数中,除两个数外其他数字都出现过两次,求这两个数字,并且按照从小到大的顺序输出.

  int[] a = { 2, 2, 1, 1, 4, 5 };
        int x = 0;
        for (int i = 0; i < a.length; i++)
            x ^= a[i];
        int temp = 1;
        while ((temp & x) == 0) {
            temp <<= 1;
        }
        int num1 = 0, num2 = 0;
        for (int i = 0; i < a.length; i++) {
            if ((temp & a[i]) != 0)
                num1 ^= a[i];
            else
                num2 ^= a[i];
        }
        System.out.println(min(num1, num2) + " " + max(num1, num2));

例如 2 2 1 1 4 5.最后输出的就是4 5

1.得到两个数异或的乘积,就比如上例中x=4^5

2.分离两个数字(找到两个数字不相同的末置位数为分界线)

4.左移运算符（<<）

将一个运算对象的各二进制位全部左移若干位(左边的二进制位丢弃,右边补0)

若左移时舍弃的高位不包含1,则每左移一位,相当于该数乘以2

例如:a = a<< 2将a的二进制位左移2位,右补0

int a=3;

a=a<<2;

0000 0011 -> 0000 1100

即a=12;

5.右移运算符（>>）

将一个数的各二进制位全部右移若干位,正数左补0,负数左补1,右边丢弃

操作数每右移一位,相当于该数除以2

例如:a = a>>2 将a的二进制位右移2位 左补0

int a=24;

a=a>>2;

0001 1000 -> 0000 0110

即a=6

int a=-24

a=a>>2;

1001 1000 -> 1000 0110

即a=-6

6.复合赋值运算符

位运算符与赋值运算符结合,组成新的复合赋值运算符

例如:&= a&=b 相当于 a=a& b

运算规则:和前面讲的复合赋值运算符的运算规则相似

7.不同长度的数据进行位运算

如果两个不同长度的数据进行位运算时,系统会将二者按右端对齐,然后进行位运算

以”与”运算为例说明如下:

以C语言中long型占4个字节,int型占2个字节举例

如果一个long型数据与一个int型数据进行”与”运算,右端对齐后,左边不足的位依下面三种情况补足

(1）如果整型数据为正数,左边补16个0.

(2)如果整型数据为负数,左边补16个1.

(3)如果整形数据为无符号数,左边也补16个0.

例如：long a=123;int b=1;计算a&b

a = 0000 0000 0000 0000 0111 1011

b = 0000 0000 0000 0000 0000 0001

a&b= 0000 0000 0000 0000 0000 0001 =1;

例如：long a=123;int b=-1;计算a&b

a = 0000 0000 0000 0000 0111 1011

b 补码 1111 1111 1111 1111 1111 1111

a&b = 0000 0000 0000 0000 0111 1011

例如：long a=123;unsigned intb=1;计算a&b

a = 0000 0000 0000 0000 0111 1011

b = 0000 0000 0000 0000 0000 0001

a&b= 0000 0000 0000 0000 0000 0001 =1;