V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
jiangxinlingdu
V2EX  ›  程序员

二进制实战技巧

  •  
  •   jiangxinlingdu · 2018-02-11 19:15:23 +08:00 · 1887 次点击
    这是一个创建于 2227 天前的主题,其中的信息可能已经有所发展或是发生改变。

    匠心零度 转载请注明原创出处,谢谢!

    说在前面

    看过稍微底层点的源码的人应该都会了解、熟悉里面多多少少会碰到二进制相关操作,因为这个之前还写了一篇java 二进制相关基础的基础篇,本篇准备写一些二进制实战技巧相关内容。

    主题

    • 判断一个数是否是 2 的幂次方的方法。
    • 操作位代表类型。
    • 非 2 的幂次方转换为 2 的幂次方。

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

    如果该数是无符号整数,可以使用:

    private static boolean isPowerOfTwo(int val) {
          return (val & (val-1)) == 0;
    }
    

    如果一个数是 2 的 n 次方,那么这个数用二进制表示时其最高位为 1,其余位为 0,(val-1)和 val 都错开了 0 和 1,那么&一定是 0。

    如果该数是无符号整数,也可以使用:

    private static boolean isPowerOfTwo(int val) {
          return (val & -val) == val;
    }
    

    如果一个数是 2 的 n 次方,那么这个数用二进制表示时其最高位为 1,其余位为 0,(val & -val)就是获取最右 1 的位,那么如果和 val 等于就是了。

    扩展下,如何判断一个无符号数是 2 的 n 次方-1

    private static boolean isPowerOfTwoLoseOne(int val) {
          return (val & (val+1)) == 0;
    }
    

    理由其实和上面类似了。

    操作位代表类型

    JDK SelectionKey 有四种操作类型,分别为:

    OP_READ = 1 << 0 ;
    OP_WRITE = 1 << 2 ;
    OP_CONNECT = 1 << 3 ;
    OP_ACCEPT = 1 << 4。
    

    由于只有四种网络操作类型,所以用 4 bit 就可以表示所有的网络操作位,由于 JAVA 语言没有 bit 类型,所以使用了整形来表示,每个操作位代表一种网络操作类型,分别为:00001、00100、01000、10000,这样做的好处是可以非常方便的通过位操作来进行网络操作位的状态判断和状态修改,提升操作性能。

    说明:依稀记得 RocketMQ 里面好像也是类似,有一个当磁盘空间大于 90%的时候不给写权限就是类似控制的,后续分析 RocketMQ 源码的时候会进行说明。

    非 2 的幂次方转换为 2 的幂次方

    在 jdk 很多集合框架里面,不知道你们还发现了,集合的大小都会是 2 的幂次方,哈哈,所以就引出了下面的话题。

     int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                       MAXIMUM_CAPACITY :
    
    
        private static final int tableSizeFor(int c) {
            int n = c - 1;
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }
    

    实例化 ConcurrentHashMap 时带参数时,会根据参数调整 table 的大小,确保 table 的大小总是 2 的幂次方,调用 tableSizeFor 的时候每次返回的都是大于等于离该数最近的 2 的幂次方的数。比如调用 tableSizeFor 传入 c 为 151 的时候 比 151 大的 2 的幂次方的数就是 256 了,核心就是上面的位运算操作。

    刚刚上面是求一个数离它最近的大于等于 2 的幂次方的数,如果求小于等于 2 的幂次方的数,我们应该怎么办呢?

     private static final int tableSizeFor(int n) {
            n |= n >>> 1;
            n |= n >>> 2;
            n |= n >>> 4;
            n |= n >>> 8;
            n |= n >>> 16;
            return  n-(n>>1);
        }
    

    说明:由于集合的大小都会是 2 的幂次方,那么求 table 大小的 0.75 倍的时候,可以使用( n - (n >>> 2))即可,取模的时候,可以使用 hash & 0x7FFFFFFF 来进行操作即可。

    结束语

    上面的都是零度发现的一些实战,如果你发现什么更好的二进制实战,欢迎在留言区积极留言评论。!!!


    如果读完觉得有收获的话,欢迎点赞、关注、加公众号 [匠心零度] ,查阅更多精彩历史!!!

    jiangxinlingdu
        1
    jiangxinlingdu  
    OP
       2018-02-11 19:50:43 +08:00
    不错的实践!
    Templ1
        2
    Templ1  
       2018-02-11 23:39:35 +08:00 via Android
    ```cpp
    int gethibit(int a)
    {
    !a?return -1:;
    int ret = 1;
    while(a>>=1)
    ret<<=1;
    return ret;
    }
    ```
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4925 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 09:54 · PVG 17:54 · LAX 02:54 · JFK 05:54
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.