目录

java位运算

基本介绍

日常开发中位运算不是很常用,但是巧妙的使用位运算可以大量减少运行开销,优化算法。举个例子,翻转操作比较常见,比如初始值为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个瓶子

参考

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