迦南地
所有文章 标签 分类 实验室 关于
迦南地

目录

java位运算

 收录于 技术
   约 5072 字   预计阅读 11 分钟    次阅读  

基本介绍

日常开发中位运算不是很常用，但是巧妙的使用位运算可以大量减少运行开销，优化算法。举个例子，翻转操作比较常见，比如初始值为1，操作一次变为0，再操作一次变为1。可能的做法是使用三目运算符，判断原始值为1还是0，如果是1，设置为0，否则设置为1。但是使用位运算，不用判断原始值，直接改变值就可以：

1
2
3
4
5
6

int num = 0;
        while (true) {
            num = num ^ 1;
            System.out.println(num);
            Thread.sleep(1000);
        }

当然，一条语句可能对代码没什么影响，但是在高重复，大数据量的情况下将会节省很多开销。

相关概念

java中各种进制的表达方式

  • 二进制

    由0，1组成。以0b开头。

  • 八进制

    由0,1,…7组成。以0开头。

  • 十进制

    由0,1,…9组成。默认整数是十进制。

  • 十六进制

    由0,1,…9,a,b,c,d,e,f(大小写均可)组成。以0x开头。

原码、反码、补码

计算机中只有有符号数采用补码表示。比如8位有符号数表示范围是-128到127，而无符号数就可以表示0到255。计算机采用补码是为了有符号数中0的表示的唯一性，并且可以把减法转换成加法来运算。除了数字，计算机中还有很多其他的数据，比如说字符等，这些都不用补码表示。

正数的补码与原码相同，负数的补码除符号位外逐位取反，然后末位加一，如：原码10010(这是负数)= 反码11101=补码11110

原码-> 补码： 符号位不变，取反再+1 补码-> 原码： 符号位不变，-1再取反

**注意：**溢出也不能影响符号位原则

java中byte有8位(包括符号位)，表示范围从-128到+127，补码表示:

  • +127： 0 1111111
  • -128： 1 0000000

-127 补码表示是10000001

原码11111111 减1(11111110)取反(10000001)，

再减1 就是10000000，转换成原码就是-0， 也就是+0/-0 都表示0，在计算机中没必要使用两个不同形式的8位数表示0，于是规定把10000000当做-128的补码(事实上它也是-128的原码表示)。

1
2
3
4
5
6
7
8

byte b = (byte) Integer.parseInt("10101000", 2);
/**
* 10101000 是补码表现形式，求原码是-1再取反
* -1 10100111
* 取反 11011000
* 所以原码是 11011000 也就是-88 (2^3 + 2^4 + 2^6 = 8 + 16 + 64 = 88)
*/
System.out.println(b); // -88

数据类型

https://gitee.com/lienhui68/picStore/raw/master/null/20200729082529.png

其中基本数据类型为：

https://gitee.com/lienhui68/picStore/raw/master/null/20200729082555.png

注意：byte,short,char之间不会相互转换，他们三者在计算时首先转换为int类型。

1
2
3
4
5
6
7

char // 16位 2个字节
byte // 8位 1个字节，
short // 16位 2个字节 ，
int // 32位 4个字节
long // 64位 8个字节, 声明 long 型常量须后加 ‘l’ 或 ‘L’。
float // 32位 4个字节，
double // 64位 8个字节

有符号 & 无符号

  1. 有符号和无符号的概念如下

    最明显的区别就是二者表示的范围不同： 无符号数中，所有的位都用于直接表示该值的大小。

    有符号数中最高位用于表示正负，所以，当为正值时，该数的最大值就会变小。

    我们举一个字节的数值对比：

    无符号数： 1111 1111 值：255 1* 27 + 1* 26 + 1* 25 + 1* 24 + 1* 23 + 1* 22 + 1* 21 + 1* 20

    有符号数： 0111 1111 值：127 1* 26 + 1* 25 + 1* 24 + 1* 23 + 1* 22 + 1* 21 + 1* 20

    同样是一个字节，无符号数的最大值是255，而有符号数的最大值是127。 原因是有符号数中的最高位被挪去表示符号了。 并且，我们知道，最高位的权值也是最高的（对于1字节数来说是2的7次方=128），所以仅仅少于一位，最大值一下子减半。

    不过，有符号数的长处是它可以表示负数。 因此，虽然它的在最大值缩水了，却在负值的方向出现了伸展。 我们仍一个字节的数值对比： 无符号数： 0 —————– 255 有符号数： -128 ——— 0 ———- 127 同样是一个字节，无符号的最小值是 0 ，而有符号数的最小值是-128。 所以二者能表达的不同的数值的个数都一样是256个。 只不过前者表达的是0到255这256个数，后者表达的是-128到+127这256个数 有

    有符号数包括负数，无符号数只有正数而已，在同一数据类型中，由于内存长度是一样的，所以无符号数比有符号数的最大值大1倍。

  2. java没有无符号类型，都是有符号类型的数据类型

    在实际开发中，可能要与c写的硬件接口，网络接口相互直接数据交互，此时由于java没有无符号的数据类型，导致java与c看似相同的数据类型，其实存储空间确是不同的，这个问题解决方法是java用更高的存储数据类型，如果c用int，你的java就要考虑用Long或者BigInteger了

运算符优先级

https://gitee.com/lienhui68/picStore/raw/master/null/20200729094702.png

位运算基本操作

乘除法是很消耗时间的，只要对数左移一位就是乘以2，右移一位就是除以2，传说用位运算效率提高了60%。

  • 位运算是针对整数类型的二进制进行的位移操作

  • 在Java中，整数的二进制是以补码的形式存在的

  • 字符、short、byte 进行位运算会先转成整型

  • 位运算计算完，还是补码的形式，要转成原码，再得出十进制值

  • 也支持复合运算， 同+=、*=，位运算也有复合运算， 如 <<=、>>>=、&=、^= 等等。

    eg -4 * 2

    -4 补码 11111111 11111111 11111111 11111100

    左移一位 11111111 11111111 11111111 11111000 （这时候还是补码）

    如果最高位符号位为0，就不需要继续操作了，因为正数的补码=原码，如果最高位是1，继续往下走

    转成反码 11111111 11111111 11111111 11110111 （补码-1）

    转成原码 10000000 00000000 00000000 00001000 （忽略符号位取反）

    转十进制 -8

移位运算

移位运算符java移位运算符不外乎就这三种：<<（左移）、>>（带符号右移）和>>>（无符号右移）。

位运算

左移 <<

整体左移，右边空出位补零，左边位舍弃 （-4 << 1 = -8）

正数左移一定位数会变成负数，比如 1 « 31 此时1被位移到了整个int的首位，也就是符号位就会变成负数

右移 >>

整体右移，左边空出位补零或补1（负数补1，整数补0），右边位舍弃 （-4 >> 1 = -2）

无符号右移 >>>

同>>,但不管正数还是负数都左边位都补0 （-4 >>> 1 = 2147483646）

右移不改变数的正负。对于一个正数，无符号右移不会变成负数(相当于除以1再取整)；但是对于一个负数，无符号右移会将负数变成正数；

跟右移运算不同的是，无符号左移和左移是一样的。因此java没有无符号左移运算。(«<和«<=将报错)

因为无右移运算需要考虑符号位的右移，而符号位只存在于二进制表示的最左边，最右边没有。

所以不用区分无符号左移和左移运算。

位运算符

与 &

每一位进行比较，两位都为1，结果为1，否则为0（-4 & 1 = 0）

或 |

或（ | ）每一位进行比较，两位有一位是1，结果就是1（-4 | 1 = -3）

非 ~

每一位进行比较，按位取反（符号位也要取反）（~ -4 = 3）

异或 ^

每一位进行比较，相同为0，不同为1（-4 ^ 1 = -3）

位运算符的应用

  1. 推断int型变量a是奇数还是偶数

    a & 1 = 0 偶数

    a & 1 = 1 奇数

    取a二进制的最后一位，如果为1则肯定是奇数，因为其他位都是2的整数次幂

  2. 取int型变量a的第k位 (k=1,2……sizeof(int))

    a » k & 1

    先左移K,把k移动到低1位，然后&1得到低一位的值

  3. 将int型变量a的第k位清0

    a = a & ~(1 « k)

  4. 将int型变量a的第k位置1

    a=a | (1 « k)

  5. int型变量循环左移k次

    a = a « k | a » 16-k (设sizeof(int)=16)

  6. int型变量a循环右移k次

    a = a » k | a « 16-k (设sizeof(int)=16)

  7. 整数的平均值

    对于两个整数x,y，假设用 (x+y)/2 求平均值。会产生溢出。由于 x+y 可能会大于INT_MAX，可是我们知道它们的平均值是肯定不会溢出的。我们用例如以下算法：

    1
2
3
4

    int average(int x, int y)  //返回X,Y 的平均值 
{    
    return (x & y) + ((x ^ y) >> 1); 
}

    (x & y) + ((x ^ y) » 1)，把x和y里对应的每一位（指二进制位）都分成三类，每一类分别计算平均值，最后汇总。

    第一类

    x,y对应位都是1，用x&y计算其平均值

    x,y对应位均为1，相加后再除以2还是原来的数，如两个00001111相加后除以2仍得00001111

    第二类

    x,y中对应位有且只有一位是1，用(x^y)»1计算其平均值

    对应位有且只有一位为1，用“异或”运算提取出来，然后»1(右移一位，相当于除以2）

    第三类

    x,y中对应位均为0，无须计算

    汇总

    (x & y) + ((x ^ y) » 1)

  8. 判断一个正整数是否是2的幂

    1
2
3

    public static boolean isPower(int n){
        return n&(n-1) == 0 && n >0;
    }

    如果一个数是2的n次方，那么这个数对应的二进制表示中只有一位是1，其余都是0. 因此判断一个数是否是2的n次方，可以转换为判断这个数对应的二进制表示是否只有一位为1. 如果一个数的二进制表示只有一位是1， 如 num = 00010000, 那么 num-1 的二进制为 num-1 = 00001111 由于num与num-1二进制表示中每一位都不相同，因此num&(num-1)的运算结果为0 可以用来判断一个数是否为2的n次方。

  9. 不用temp交换两个整数

    1
2
3
4
5
6
7
8
9

    public static void main(String[] args) {
        int a = 3, b = 5;
        System.out.println("before swap：" + "a=" + a + ",b=" + b);
        // 开始交换位置
        a = a ^ b; 
        b = a ^ b; // b=a^b^b=a
        a = a ^ b; // a=a^b^a=b
        System.out.println("after swap：" + "a=" + a + ",b=" + b);
    }

  10. 计算整数绝对值

    1
2
3

    private int abs(int i) {
        return (i ^ (i >> 31)) - (i >> 31);
    }

    1. 如果value是正数，右移31位之后就变成了0x00000000，

      value和0x00000000异或，仍然是value，

      异或之后的value-0x00000000仍然是value,

    2. 如果value是负数，右移31位就变成了0xffffffff，

      value和0xffffffff异或，变成了value连着符号位全部取反，也就是实现了补码取反，

      补码取反-0xffffffff也就是补码取反再+1，是就上就对应着value的绝对值

    因为这里value和value的绝对值实际上只有最高位，也就是符号位不同， 这样移位就可以将最高位的符号位1变成0，实现绝对值的快速计算。

  11. 取模运算转化成位运算 (在不产生溢出的情况下)

    a%$(2^n) $ 等价于 a & ($2^n$ - 1)

    来源自 HashMap 中的 indexFor 方法：

    1
2
3
4
5
6

    /**
* 使用哈希值对链表数组的长度取模，得到值所在的索引位置，里面使用位运算（&）代替普通的（%）运算
*/
static int (int h, int length) {
   return h & (length-1);
}

    原理：

    对于所有 $2^n$ 的数，二进制表示为：

    1000…000，1 后面跟 n 个 0

    而 $2^n - 1$ 的二进制为：

    0111…111，0 后面跟 n 个 1

    $X / 2^n$ 是 X » n，那么 X & ($2^n$ - 1) 就是取被移掉的后 n 位，也就是 X % $2^n$。

  12. 乘法运算转化成位运算 (在不产生溢出的情况下) $a * (2^n)$ 等价于 a « n

  13. 除法运算转化成位运算 (在不产生溢出的情况下) $a / (2^n)$ 等价于 a» n

  14. a % 2

    等价于 a & 1

  15. x 的 相反数

    取反+1： ~x+1

  16. 使用位掩码表示权限

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

    public class NewPermission {
    // 是否允许查询，二进制第1位，0表示否，1表示是
    public static final int ALLOW_SELECT = 1 << 0; // 0001
    
    // 是否允许新增，二进制第2位，0表示否，1表示是
    public static final int ALLOW_INSERT = 1 << 1; // 0010
    
    // 是否允许修改，二进制第3位，0表示否，1表示是
    public static final int ALLOW_UPDATE = 1 << 2; // 0100
    
    // 是否允许删除，二进制第4位，0表示否，1表示是
    public static final int ALLOW_DELETE = 1 << 3; // 1000
    
    // 存储目前的权限状态
    private int flag;
    
    /**
     *  重新设置权限
     */
    public void setPermission(int permission) {
        flag = permission;
    }
    
    /**
     *  添加一项或多项权限
     */
    public void enable(int permission) {
        flag |= permission;
    }
    
    /**
     *  删除一项或多项权限
     */
    public void disable(int permission) {
        flag &= ~permission;
    }
    
    /**
     *  是否拥某些权限
     */
    public boolean isAllow(int permission) {
        return (flag & permission) == permission;
    }
    
    /**
     *  是否禁用了某些权限
     */
    public boolean isNotAllow(int permission) {
        return (flag & permission) == 0;
    }
    
    /**
     *  是否仅仅拥有某些权限
     */
    public boolean isOnlyAllow(int permission) {
        return flag == permission;
    }
}

    可以替代位域的更好的方案 在《Effective Java》一书中，更推荐用EnumSet来代替位域：位域表示法也允许利用位操作，有效的执行像union和intersection这样的集合操作。但位域有着int枚举常量所有的缺点，甚至更多。当位域以数字形式打印时，翻译位域比翻译简单的int枚举常量要困难很多。甚至要遍历位域表示的所有元素也没有很容易的方法。

    改成EnumSet的写法是：

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    public class Text {

    public enum Style {
        BOLD, ITALIC, UNDERLINE, STRIKETHROUGH
    }

    public void applyStyles(Set<Style> styles) {
        System.out.println(styles);
    }
}

    1. 老鼠试毒药

      有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有一瓶是毒药。任何喝下毒药的生物都会在一星期之后死亡。现在，你只有 10 只小白鼠和一星期的时间，如何检验出哪个瓶子里有毒药？

      根据2^10=1024，所以10个老鼠可以确定1000个瓶子具体哪个瓶子有毒。具体实现跟3个老鼠确定8个瓶子原理一样。 000=0 001=1 010=2 011=3 100=4 101=5 110=6 111=7 一位表示一个老鼠，从左到右分别代表老鼠3，老鼠2，老鼠1。0-7表示8个瓶子。也就是分别将1、3、5、7号瓶子的药混起来给老鼠1吃，2、3、6、7号瓶子的药混起来给老鼠2吃，4、5、6、7号瓶子的药混起来给老鼠3吃，哪个老鼠死了，相应的位标为1。如老鼠1死了、老鼠2没死、老鼠3死了，那么就是101=5号瓶子有毒。同样道理10个老鼠可以确定1000个瓶子

参考

一张图看懂原码/反码/补码之间的关系

更新于 2020-06-08
 java基础
返回 | 主页