精灵王


  • 首页

  • 文章归档

  • 所有分类

  • 关于我

  • 搜索
设计模式-行为型 设计模式-创建型 设计模式-结构型 设计 系统设计 设计模式之美 分布式 Redis 并发编程 个人成长 周志明的软件架构课 架构 单元测试 LeetCode 工具 位运算 读书笔记 操作系统 MySQL 异步编程 技术方案设计 集合 设计模式 三亚 游玩 转载 Linux 观察者模式 事件 Spring SpringCloud 实战 实战,SpringCloud 源码分析 线程池 同步 锁 线程 线程模型 动态代理 字节码 类加载 垃圾收集器 垃圾回收算法 对象创建 虚拟机内存 内存结构 Java

Java 位运算技巧

发表于 2021-04-27 | 分类于 Java | 0

二进制

二进制(binary)通常用0和1来进行表示,在数字电子电路中,逻辑门直接采用了二进制,现代计算机和依赖计算机设备里面也都用到了二进制,而位运算就是直接对整数在内存中的二进制位进行操作。

比如二进制:0000 1000

对应的十进制是:8

Java 中进制的表示

在Java7之前,Java是不支持直接书写二进制的,但在Java7开始就支持直接书写二进制。

  • 二进制(前缀:0b/0B)
  • 8进制(前缀:0)
  • 16进制(前缀:0x/0X)

下面是10进制数32,在Java语言中的4种不同进制表示方式

public static void main(String[] args){
    // 二进制
    int a = 0b00100000;
    // 8进制
    int b = 040;
    // 十进制
    int c = 32;
    // 十六进制
    int d = 0x20;
    System.out.println(a);
    System.out.println(b);
    System.out.println(c);
    System.out.println(d);
}

负数如何用二进制表示

将其原码除符号位外的所有位取反(0变1,1变0,符号位变为1)后加1;

比如-9;

+9的原码为:1001;

-9为:先取反(+9)得到0110,符号位要变为1,得到10110,最后加上1,得到最后结果 10111;

Java 位运算

Java支持的位运算有:

  • 按位与(&)
  • 按位或(|)
  • 按位异或(^)
  • 按位取反(~)
  • 左位移(<<)
  • 右位移(>>)
  • 无符号右位移(>>>)

按位与(&)

计算规则:如果相对应位都是1,则结果为1,否则为0

运算示例:

System.out.println(32 & 16);
//  计算过程:
    0010 0000
  & 0001 0000
  = 0

按位或(|)

计算规则:如果相对应位都是 0,则结果为 0,否则为 1(只要有一个是1,那结果ji);

运算示例:

System.out.println(32 & 16);
    //  计算过程:
    0010 0000
  | 0001 0000
  = 0011 0000

按位异或(^)

计算规则:如果相对应位值相同,则结果为0,否则为1(不同才为1);

运算示例:

System.out.println(32 & 16);
    //  计算过程:
    0010 0000
  ^ 0001 0000
  = 0011 0000

按位取反(~)

计算规则:按位取反运算符翻转操作数的每一位,即0变成1,1变成0;

运算示例:

System.out.println(~16);
    //  计算过程:
  ~ 0001 0000
  = 1110 1111

左位移运算(<<)

计算规则:将一个二进制数中的每一位全部都向左方向移动指定位数;溢出的部分被舍弃,空缺的部分全部填0;

运算示例:

System.out.println(16 << 1);
    //  计算过程:
    0001 0000(十进制16)
  << 1(左位移1位)
  = 0010 0000(十进制32)

右位移运算(>>)

计算规则:将一个二进制数中的每一位全部都向右方向移动指定位数;溢出的部分被舍弃,空缺的部分全部填0;

运算示例:

System.out.println(16 << 1);
//  计算过程:
    0001 0000(十进制16)
  >> 1(右位移1位)
  = 0000 1000(十进制8)

无符号右位移(>>>)

计算规则:忽略操作数的符号向右移动指定的位数;溢出的部分被舍弃,空缺的部分全部填0;

运算示例:

System.out.println(16 << 1);
    //  计算过程:
    0001 0000(十进制16)
  >>> 1(无符号右位移1位)
  = 0000 1000(十进制8)

Java 哪些地方用到了位运算

位运算在某些时候不仅能够提升我们的运算速度,还能基于二进制位运算计数来简化我们的业务设计。

1.HashMap源码

在HashMap的源码中,初始容量和最大容量,以及索引定位,都是通过位运算计算而来的。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;

// 使用位运算计算位置索引(传统的计算是hash % n),位运算算余数要求(n-1)中的n必须是2的幂
// 这也是为什么HashMap 要求桶的个数的2的N次方-1的一个原因
int index = (n - 1) & hash

2.StampedLock源码

在升级版的读写锁StampedLock中,仅用一个state字段就表示了读锁、写锁的状态和版本,就是通过二进制位的思想来完成的。

// 用来计算state值的常量
private static final long RUNIT = 1L;  // 读单位
// 写锁的标识位 十进制:128  二进制位标示:1000 0000 
private static final long WBIT  = 1L << LG_READERS;  
// 读状态标识 admol 十进制:127  二进制: 0111 1111
private static final long RBITS = WBIT - 1L;   
// 读锁的最大标识  十进制:126 二进制 :0111 1110 
private static final long RFULL = RBITS - 1L;  
// 用来读取读写状态  十进制:255 二进制:1111 1111
private static final long ABITS = RBITS | WBIT;

StampedLock源码分析可以查看之前的文章:StampedLock源码分析

位运算常用技巧

通过位运算可以实现很多计算上的骚操作,比如:

整乘或整除2的N次方

右移N位相当于除以2的N次方,左移N位相当于乘以2的N次方;

10 * 2 可以写成 10 << 1;

10 / 2 可以写成 10 >> 1;

快速求余数:当两个整数a % b , 恰好b等于2的N次方的时候, 可以使用a & (b-1)计算,比如: 9 % 4 = 9 & 3;

不借助第三个变量交换两个变量的值

传统的做法:

int a= 3; int b = 5;
a = a + b;
b = a - b;
a = a - b;

虽然使用传统的做法也可以实现功能,但是其中在做a = a + b加法运算的时候,结果可能会溢出,超出int的最大值,从而导致BUG的产出。

使用位运算:

int a= 3; int b = 5;
a = a ^ b; 
b = a ^ b ; 
a = a ^ b;

使用位运算不会有溢出的问题。

判断一个数是否是 2 的幂次方

这是LeetCode上面的一道题:2的幂;通过位运算技巧可以实现O(1)的时间复杂度解决问题;

两种方法:

  1. 获取二进制中最右边的 1

    x & (-x)
    具体原理为什么可以,可以查看LeetCode的分析;
    然后通过(x & (-x)) == x; 即可判断数是否是 2 的幂次方。

  2. 去除二进制中最右边的 1

    x & (x - 1)
    具体原理为什么可以,可以查看LeetCode的分析;
    因此判断是否为 2 的幂可以用:判断 x & (x - 1) == 0

判断一个数是奇数还是偶数

因为在二进制的表示方式下偶数的最低位肯定是0,奇数的最低位肯定是1。

所以可以使用(x & 1) == 0 来判断一个数的奇偶性。

异或技巧

  1. 两个相同的数异或后为0

    n ^ n => 0

  2. 任何数于0异或后仍为任何数

    0 ^ n => n

实战技巧

一、位运算符实现一个简单的用户权限控制功能

假设一个系统希望可以赋予不同用户有不同的操作权限,分别是可查看权限、可新增权限、可修改权限、可删除权限。

传统的做法可能需要用到用户表、权限表、用户权限表;

位运算的方式可以使用一个字段(p_value)即可表示一个用户拥有的功能。

用二进制的4位来分别代表可查看权限、可新增权限、可修改权限、可删除权限。

  • 0001:表示拥有可查看权限(十进制1)
  • 0010:表示拥有可新增权限(十进制2)
  • 0100:表示拥有可修改权限(十进制4)
  • 1000:表示拥有可删除权限(十进制8)

假如一个用户张三同时拥有4种权限,那用二进制表示就是:1111(十进制15)

1.如何给用户添加权限?

假如张三之前的权限是0000,现在要给他添加可查看权限(0001);

计算过程就是:p_value =(old_p_value | 0001)

假如张三已经拥有了可查看权限(0001),现在要给他添加可修改权限(0100);

计算过程就是:p_value =(old_p_value | 0100)

所以添加权限的计算过程就是:p_value =(old_p_value | 添加的权限值)

2.如何删除用户的某一权限?

假如张三拥有所有的操作权限(1111),现在要将他的删除权限给下掉;

计算思路就是要把代表删除权限的第4位给置为0;这里要用到位运算取反和与;

计算过程是:p_value = (1111 & (~1000)) ⇒ 0111;也就代表没有删除权限;

3.如何校验用户是否拥有删除权限?

加入张三现在只有可查看、可新增、可修改权限,也就是(0111);

现在要校验张三是否有可新增权限:

计算思路:校验第2位是否为1即可。

计算过程:return (0111 & 0010) == 1,如果计算为false,表示没有新增的权限;

总结

  1. 二进制是计算机中数据表示的基础,位运算必不可少
  2. 特殊的运算使用位运算的方式可以提升效率,尤其是有乘除运算时
  3. 二进制可以用来表示多种状态的组合,结合位运算使用效果最佳
精 灵 王 wechat
👆🏼欢迎扫码关注微信公众号👆🏼
  • 本文作者: 精 灵 王
  • 本文链接: https://jinglingwang.cn/archives/bitoperation
  • 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!
# 设计模式-行为型 # 设计模式-创建型 # 设计模式-结构型 # 设计 # 系统设计 # 设计模式之美 # 分布式 # Redis # 并发编程 # 个人成长 # 周志明的软件架构课 # 架构 # 单元测试 # LeetCode # 工具 # 位运算 # 读书笔记 # 操作系统 # MySQL # 异步编程 # 技术方案设计 # 集合 # 设计模式 # 三亚 # 游玩 # 转载 # Linux # 观察者模式 # 事件 # Spring # SpringCloud # 实战 # 实战,SpringCloud # 源码分析 # 线程池 # 同步 # 锁 # 线程 # 线程模型 # 动态代理 # 字节码 # 类加载 # 垃圾收集器 # 垃圾回收算法 # 对象创建 # 虚拟机内存 # 内存结构 # Java
(十)操作系统-文件系统
ConcurrentHashMap 使用示例
  • 文章目录
  • 站点概览
精 灵 王

精 灵 王

青春岁月,以此为伴

106 日志
14 分类
48 标签
RSS
Github E-mail
Creative Commons
Links
  • 添加友链说明
© 2023 精 灵 王
渝ICP备2020013371号
0%