《计算机原理》复习之位运算

我们以java语言为例,先来看下各种数据类型所占用的内存大小:

类型              存储需求        bit数                  取值范围     

byte              1字节           8         （-2的31次方到2的31次方-1）
short             2字节           16               －32768～32767
int               4字节           32         （-2的63次方到2的63次方-1）
long              8字节           64                 －128～127
float             4字节           32         float类型的数值有一个后缀F(例如：3.14F)
double            8字节           64       没有后缀F的浮点数值(如3.14)默认为double类型
char              2字节           16
boolean           1字节           8                 false、true

java中的数字类型为有符号数字,最高位是符号位,符号位为0表示正数,1表示负数,拿short来说:

01111111 11111111
这就是两个字节,16位,最高位是0,表示正数,所以上面就是short的最大值,2^15-1=32767
00000000 00000000就是数字0
10000000 00000000  因为0已经有了,所以这个-0被当做最小的负数,也就是-32768
10000000 00000001  这就是-32767(可以认为是从最小的负值上+1)
11111111 11111111 这就是最大的负值,也就是-1

所以如果是无符号数,那么对于一个2个字节的整数来说:

11111111 11111111 这就是最大的整数,也就是2^16-1
00000000 00000000 也就是最小的整数0

进制之间的转换,如果是二进制转为n进制,可以记住,3位2进制就是1个8进制,4位2进制就是1位16进制

位运算:

1.&运算(与运算):相同位上,都为1才是1,否则为0
 10011
&10110
-------
 10010

2.|运算(或运算):相同位上,都是0才是0,否则为1
 10011
|10110
-------
 10111
3.^运算(异或运算):相同位上,相同为0，不同则为1（对于任何数与 0 异或都会保持不变，与 -1 即 0xffffffff 进行异或就相当于对此数进行取反）
 10011
^10110
-------
 00101
4.~运算(取反运算):相同位上,1变0,0变1
~10110
-------
 01001
5.<<运算(左移运算):向左进行移位操作,超出的高位丢弃,缺少的低位补0
10110 << 3 = 10000
也就是这样:
   10110
10110000
----------
   10000(丢弃超出的高位,缺少的低位补0) 
6.>>运算(有符号右移运算):向右进行移位操作,超出的低位丢弃,如果是正数缺少的高位补0,负数则补1
如果是有符号数(负数):
10110 >> 3 = 11110
也就是这样:
10110
11110110
----------
11110(丢弃超出的低位,缺少的高位补1) 

如果是有符号数(正数):
00110 >> 3 = 00010
也就是这样:
10110
00010110
----------
00010(丢弃超出的低位,缺少的高位补0) 


7.>>>运算(无符号右移运算):向右进行移位操作,超出的低位丢弃,无论正数或负数都按照无符号来补位,也就是按照正数来,也就是补0
如果是有符号数(负数):
10110 >>> 3 = 00010
也就是这样:
10110
00010110
----------
00010(丢弃超出的低位,缺少的高位补0) 

如果是有符号数(正数):
00110 >> 3 = 00010
也就是这样:
10110
00010110
----------
00010(丢弃超出的低位,缺少的高位补0)

常见位运算应用:

左移1位相当于乘2,无符号右移1位或者无符号数右移相当于除2

int a = 2;
a >> 1; ---> 1
a << 1; ---> 4

两数交换(不使用第三个变量)

首先,使用普通运算也可以实现:
void swap(int a,int b){
    a = a + b;
    b = a - b;
    a = a - b;
}
但是使用二进制位运算效率更高:
void swap(int a,int b){
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}
或
void swap(int a,int b){
    a ^= b;
    b ^= a;
    a ^= b;
}
因为异或操作就相当于拿到两个比较方的不同点,拿着不同点和其中任何一个比较方便再次比较(异或),得到的结果就是另一个比较方

判断奇偶数

如果一个数的最低位是1，那么这个数一定是奇数，否则一定是偶数
void isEven(int num){
    if(0 == num & 1){
        //偶数
    }else{
    //奇数
    }
}

获取一个数的相反数

          1110  1111   0000   0001   0010   0011
----------|------|------|------|------|------|--------->
          -2     -1     0      1      2      3
可以 看到，只需要将该数取反之后加1即可
int reverse(int a){
    return ~a + 1;
}

求取绝对值

方法一：
非负数的绝对值就是其本身，负数的绝对值就是其相反数，所以只要判断是否为非负数，如果是就用上面的取相反数方法就可以了,下面就是针对32位int型数据进行的获取绝对值操作：
int abs(int a){
    int i = a >> 31;
    return    (i == 0) ? a : (~a+1);
}
方法二：
上面的方法1中的正负判断也可以省略，首先，任何数与0异或，都等于其本身，任何数与-1(0xffffffff)异或都等于其取反
int abs(int a){
    int i = a >> 31;
    return    i^a - i;//如果a是负数，那么i=-1，那么i^a就是a的取反，而取反后+1就是其相反数，负数的绝对值就是其相反数，所以这里-i就是-（-1)=+1,如果a是非负数,那么i=0,那么i^a就是a本身，-i就是0，所以没有影响
}

以上两种方法我个人觉得效率差不多，因为方法1多了判断，方法二少了判断多了非负数的异或操作

高位和低位交换

对于一个无符号数：11000100 10111110
怎样将其高低八位互换，也就是变为10111110 11000100
int swapInt(int a){
    return a>>8 | a<<8;
}

统计二进制数中1出现的次数

统计二进制1的个数可以分别获取每个二进制位数，然后再统计其1的个数，此方法效率比较低。这里介绍另外一种高效的方法，同样以 34520 为例，我们计算其 a &= (a-1)的结果：
第一次：计算前：1000 0110 1101 1000 计算后：1000 0110 1101 0000
第二次：计算前：1000 0110 1101 0000 计算后：1000 0110 1100 0000
第三次：计算前：1000 0110 1100 0000 计算后：1000 0110 1000 0000 
我们发现，没计算一次二进制中就少了一个 1，则我们可以通过下面方法去统计：
count = 0  
while(a){  
  a = a & (a - 1);  
  count++;  
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2022/12/04 20:27