Java源码位操作技巧欣赏

最近有人问些逻辑位移,算术位移的区别和应用场景,翻了一些旧材料,重新整理一下发出来,给大家欣赏一下java源码中涉及的位操作技巧,摘取的是Integer的源码实现。

整数二进制左边1最早出现的位置

public static int highestOneBit(int i) {
        // HD, Figure 3-1
        i |= (i >>  1);
        i |= (i >>  2);
        i |= (i >>  4);
        i |= (i >>  8);
        i |= (i >> 16);
        return i - (i >>> 1);
    }

画个图简单说明一下计算的原理,简化一下只用8位为例,做了右移1,2,4位之后的效果,最终的效果就是在最早出现1的位置后面都是1。 32位的int也是类似的,最终的效果就是从左边第一位是1开始后面都是1。

图例1

有点神奇,仔细想想,前面的多次移位就是最前面那个1填满后面所有位(无论后面是0还是1)。

整数二进制右边1最早出现的位置

public static int lowestOneBit(int i) {
        // HD, Section 2-1
        return i & -i;
    }

负数以补码形式存在,一个负数的补码,就是对应整数的二进制再取反加一。i和-i总有一个是正数,假设是i吧,由于两个数相加是0,在二进制角度来看,假设i最右边出现1的位置是k,那么在相同位置上-i必定也是1,并且-i在k以后的位也是0,这2位相加是0,并且进位1,那么要是k-1位相加得到0,两个数字在k-1位上只能是一个1,另外一个是0,以此类推,可以得到从左边第一位开始直到k-1位都是不同的。两个数进行与运算,只会在k位保留1,其他位都变成0。

整数二进制左边开头有连续多少个0

public static int numberOfLeadingZeros(int i) {
        // HD, Figure 5-6
        if (i == 0)
            return 32;
        int n = 1;
        if (i >>> 16 == 0) { n += 16; i <<= 16; }
        if (i >>> 24 == 0) { n +=  8; i <<=  8; }
        if (i >>> 28 == 0) { n +=  4; i <<=  4; }
        if (i >>> 30 == 0) { n +=  2; i <<=  2; }
        n -= i >>> 31;
        return n;
    }

以移动16位为例子,如果左移16位之后是0,那么前16位都是0,那么就只要判断后面16位就可以了。 如果不是0,那么只要判断前面16位就可以了,和前面的区别就是,它不需要移位。后面的移位操作,以此类推就可以了。

整数二进制右边结束有连续多少个0

public static int numberOfTrailingZeros(int i) {
        // HD, Figure 5-14
        int y;
        if (i == 0) return 32;
        int n = 31;
        y = i <<16; if (y != 0) { n = n -16; i = y; }
        y = i << 8; if (y != 0) { n = n - 8; i = y; }
        y = i << 4; if (y != 0) { n = n - 4; i = y; }
        y = i << 2; if (y != 0) { n = n - 2; i = y; }
        return n - ((i << 1) >>> 31);
    }

和上面的差不多,假设右移16位不等于0,那么说明只需要判断右边16位就可以了。如果等于0,那说明要判断左边16位。后面的移位操作,以此类推就可以了。

整数二进制总共有多少个1

public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }

这个算法我是看呆了,神乎其技,它的做法是分别计算每2位,每4位,每8位,每16位,每32位..这样的顺序计算。

以第一行为例,0x55555555刚好每2位是01,而每2位有4种情况,分别是00,01,10,11, 计算i-((i»>1) & 01) 可以得到00,01,01,10, 就对应表示1的个数。是不是很神奇。

整数向左滚动X位

public static int rotateLeft(int i, int distance) {
        return (i << distance) | (i >>> -distance);
    }

这是基本的移位操作,注意的是右边要采用算术右移。

整数向右滚动X位

public static int rotateRight(int i, int distance) {
        return (i >>> distance) | (i << -distance);
    }

和上面的一样,就不再详述了。

整数二进制反转

public static int reverse(int i) {
        // HD, Figure 7-1
        i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
        i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
        i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
        i = (i << 24) | ((i & 0xff00) << 8) |
            ((i >>> 8) & 0xff00) | (i >>> 24);
        return i;
    }

这个代码也很神奇,完全看不懂。以第一行为例,它的作用就是两两交换,可以通过下图分析可得。

图例2

同理,第二行是每2位交换,第三行是每4位交换,假设原来是b1b2b3b4b5b6b7b8,那么三行执行后,结果就是b8b7b6b5b4b3b2b1,就是一个字节的位进行反转了。最后一句就是按字节反转一下,最终结果就是按位反转了。

整数的符号,0返回0,正数返回1,负数返回-1

public static int signum(int i) {
        // HD, Section 2-7
        return (i >> 31) | (-i >>> 31);
    }

感觉这个实现有点多此一举,直接大小判断很简单,也很直观,为什么不采用?

还是画个图说明一下吧。

图例3

整数按字节反转

public static int reverseBytes(int i) {
        return ((i >>> 24)           ) |
               ((i >>   8) &   0xFF00) |
               ((i <<   8) & 0xFF0000) |
               ((i << 24));
    }

这个算法很好理解,第一个字节右移24位就跑到第四个字节去了,第二个字节右移8位到了第三位,和FF00与运算就抹掉对第四个字节的影响。后面的就不解释了。

从Integer的方法实现看,有些位操作的技巧实在很巧妙,能想出来真的不容易。像java之类的源代码还是有很多有趣,实用的技巧的,有机会再分享一些。

我们从不缺流程和措施

最近部门内要做研讨,针对项目交付压力大,加班比较严重的问题。个人思前想后,有感而发整理一下思绪,记录如下。

做个类比,当前的情况就好比抗日初期。抗日初期国内充斥着速胜论和速亡论,作为对比就类似于”有措施立竿见影,迅速登上人巅峰”,”怎么弄都是瞎折腾,大不了挪个窝”的想法。但教员说抗日是持久战,我们的情况也是类似的,冰封三尺非一曰之寒,也是持久战。

论持久战,讲究战略/战术。

在战术上只能先保住基本盘,我们定义的基本盘不是交付进度,而是交付质量。抓核心交付件质量,无非首要就是代码质量,这里只谈需求-开发-测试中整套基本流程中的开发环节,开发人员从开发实现,到最终交付,正常是有两道坎的,一道是MR合并评审,一道是线下代码评审。线下代码评审,其实更多是整体上看需求实现,更偏流程的后期,很多时候对小问题能不改就不改,作用是有的,但不利于培养好的开发习惯,而且很多项目做得不到位(要和谐)或根本不做(反正跳过也能发布)。而关于MR合并评审,从公司平台上披露的统计信息看到,效果是无限趋向于零的。

这种情况,合理的解释是: 代码特别紧急(你不合并系统就要跪) 或者 人人都是开发者(我的代码就是BUG FREE) 。这涉及到两个方面,速度与激(质)情(量)。从经验角度看,代码晚两天合并也没问题,急于合并主要是因为测试驱动开发,后面可预见的修改还不少。至于质量嘛,人总会犯错的,人人都是开发者没错,但不是”人人都是合格的开发者”。

那为什么还是这样,还是要回到能力和意愿两个维度看,评审人员除了要有代码欣赏能力,也要有意愿(其实是坚持底线)。所以我们的建议是:

1.代码评审。审视各个项目的代码合入情况,对合入进行抽查。如果是不具备代码评审能力,可以进行专门培训、结对训练。如果是过于随意,考虑取消合入权限。

交付上线或多或少会遇到一些问题,特别当前项目战线长,交付频率高的情况,遇到问题怎么快速定位是关键,而且我们能依靠的手段主要是日志,日志打不打,怎么打是有规范的,所以关注点是有没有落到项目去。所以建议是:

2.应用日志 。项目可以用上日志平台的,要上日志平台、服务调用链。各项目需要自证符合日志规范,不符合的要进行修改。

回到战略,我们是谋求长治久安,还是得回到人身上。员工的期望的是:人来了能学到东西持续成长。项目的期望是:人跑了能留下东西造福后人。 所以这东西,靠人也不靠人,一方面需要靠人去完成项目,一方面要靠培训机制、知识管理来减少对人的依赖。所以建议是:

3.培训计划。以教促学,去年有开展,可以持续收集开展。有些同事觉得分享的内容有一定的项目局限性,所以没有太强的意愿参与,可以根据受众不同(有些内容针对个别项目,可以提高参与度)来优化。

4.知识管理**。当前有部分项目是集中后补的,这个要落到项目日常管理动作中去。可能PM要关心一下知识管理的周期性进展,落到开发组长,可能就更细致一下,例如小到某个配置,某个问题后要及时总结。对好的知识管理也要宣传,我个人就对当前每周的知识管理推荐就不大满意。

惭愧,回头来看,好像什么都是老生常谈。以前就有相关的要求呀,能不能来点干货? 干货是拿不出来了,因为我们从不缺流程和措施。

2020年GOPS深圳站参会分享

9.25-9.26去深圳参加了GOPS做一些总结。 我们参加了3个会场的分享,25号下 AiOps午是相关,26号上 DevOps午是相关,26号下午是基础设施相关的。参考自身业务, AiOps主要看方向,看差距, DevOps看实践,看套路,基础设施看的是其他人怎么理解PAAS

AiOps的分享主要是Ai的应用场景,内容就是蜻蜓点水,可能是考虑大家的背景吧。比较有印象的只能运维架构是擎创科技的夏洛克平台,从官网上再找了个图,看看。 夏洛克平台

还有华为消费者云服务SRE的分享,日志每日高达1.5PB,提到个观点比较有印象,虽然就一句话,尽量多收集日志。无论是何种运维模式,说到底还是数据,没数据就成无米之炊了。回到我们的系统,最近也出了不少问题,流程怎么走,走进去了没有,没有相关的日志。日志对运维来说太重要了,日志收集、服务调用链,都很有用,但业务的日志呢,关键点的日志呢,还是要自上而下落到项目去,按计划要求完成。(发散一下,就像送检一样,对日志也可以提各种要求,例如哪些地方要打日志,要打哪些日志,最后要求项目改造完成后自证)。

DevOps专场,总体上印象没有太深,大多是运维人员参会,更多的内容关注Ops,而不是Dev。有个提到 DevSecOps就是把安全融入 DevOps过程中,例如漏洞扫描,第三方检测之类,跟可信有点像,我们都依托公司平台,就没有太关注了。 JFrog的单一数据源分享,我个人感觉 JFrog的商业版应该是比较强大的,有很多有用的特性,但就是社区版实在太鸡肋了,一方面我们现在更多是依赖公司的平台,或许后续就不需要自建仓库了,另一方面像我们的场景,没法完全的 DevOps,很多功能也要打折扣。光大证券的IPV6改造应该是干货最多的分享了,基本是一个比较成型的PV6改造方案框架了,可以参

基础设施专场,主要是基础平台构建的内容,不少PAAS相关的内容,主要是看看其他人对PAAS是怎么理解的。旷视科技的私有云交付分享,其实是有一定参考意义的,也是开发和运维不是一拨人,没法直接操作的场景。 devops平台

总体来说,他们是构建了一个 DevOps平台(和PAAS有点像把),更多是在易用性上发力。不过采用的部署编排工具不是k8s,而是自研的一套,但是和k8s的部署yaml语法有点类似,是参考 dockercompose格式定义的。 我主要关注了他们的监控告警能力,是如何构建的。对比我们的系统,特别是上云之后,监控告警还没建立,应用监控接口还比较弱(应用都要开放监控接口,这套模式是谷歌SRE宣传的),这些都是参考的地方。 监控平台

接上面的监控,再补充一下另外一个分享,提到 DevOps平台要进行集中化中间件管理的,这是类似于共有云的开箱即用的平台,这个是有价值的。我这里想说的是,项目中间件技术日益增多,有必要先提供统一的、标准的监控能力,然后再谋求进一步发展。 中间件监控平台

腾讯的tars分享更多是围绕tars微服务框架的,提到他们的SET模型还是有适应场景的,如果有这种应用场景,还是可以参考这个方案的,其他倒是没有太多印象。

总体内容是比较丰富的,大多数是只讲思路,说说方向,展现的细节不多,基本都吹吹牛逼,夹带私货做做宣传。分享的有传统行业也有大厂、创业公司,有展台的基本都是创业公司,当然都是细分领域做得不错的。 另外时间很紧凑,密集轰炸,像我们几个包场的几个小时下来听的都累了,到后面没太多印象就忘记了,下次有机会还是要挑一些感兴趣的重点关注。 我PPT收集得比较少,后面看看有没有其他人分享出来。另外,说好是运维大会,建议运维的同事也参加一下,看看别人家的运维是怎么过的。

另外时间很紧凑,密集轰炸,像我们几个包场的几个小时下来听的都累了,到后面没太多印象就忘记了,下次有机会还是要挑一些感兴趣的重点关注。 我PPT收集得比较少,后面看看有没有其他人分享出来。另外,说好是运维大会,建议运维的同事也参加一下,看看别人家的运维是怎么过的。

俄罗斯方块转弯算法实现

关于俄罗斯方块程序对战程序中实现方块转弯的算法描述。

为了方便描述算法的原理,以方块的左上角为基准,简化问题为一个11的小方块,在rowcol的矩阵中可以最终移动到哪个位置。

现在来看看位置(x y)是否可以移动到(即使是临时的)。 如果它可以被移动到,那么它从哪个位置移动过来。也很简单。 首先,如果上面位置(x-1 y)可以被移动到,那么(x y)也是可以的。 其次,如果左边(x y-1)或右边(x y+1)的位置可以被移动到,那么(x y)也是可以的。

那么评估位置是否可以移动到(即使是临时的)的算法,就可以这么描述:

1.定义一个二维数组,表示某个格是否移动到(即使是临时的),默认为false不可以。
2.初始化第一行的状态,如果方块在(0 i)可放置(和当前矩阵没冲突)则设置state[0][i]为true。
3.从第二行开始遍历,针对每一行i进行以下处理
3.1.对当前行的列j进行遍历,如果当前位置可放置,且同一列上一行的位置可移动到,则state[i][j]为true
3.2.对当前行的列j进行遍历,如果当前位置state[i][j]为true,则往左边(右边)一直检查
3.3.如果左边位置k可放置,则state[i][k]为true,直到k不可放置或k位置已经为true

最后,通过检查state就可以直到哪个位置可以被移动到。判断这个位置是否是最终移动的位置,则可以判断该位置是否最后一行,或同一列的下一个位置是否可以放置。

不过这里还有个问题,就是即使知道某个位置是可以被移动到的,但怎么还原出下落的路线呢?

其实,我们可以记住拐点,就可以知道路线了。 现在我们在(4,3)位置记录上一个拐点(3,3),然后在(3,3)记录再上一个拐点(3,2),以此类推就可以得到下落路线(反向的)。 我们想要的结果是

(0,0)(+,+)(+,+)(+,+)(+,+)
(0,0)(1,0)(1,0)(+,+)(+,+)
(+,+)(+,+)(1,2)(+,+)(+,+)
(+,+)(+,+)(1,2)(3,2)(+,+)
(+,+)(+,+)(+,+)(3,3)(+,+)

具体怎么记录这个拐点呢?可以在上面的算法基础上修改一下即可。 首先,考虑把(x,y)这个拐点值记录为x*ROW+y,这样修改state为整形二维数组。

1.定义一个二维数组,表示某个格是否移动到(即使是临时的),默认为MAX(ROW*COL,一个不可能的拐点),表示不可以。
2.初始化第一行的状态,如果方块在(0 i)可放置(和当前矩阵没冲突)则设置state[0][i]为拐点(0,i),即j。
3.从第二行开始遍历,针对每一行i进行以下处理
3.1.对当前行的列j进行遍历,如果当前位置可放置,且同一列上一行的位置不为MAX,则state[i][j]为state[i-1][j]
3.2.对当前行的列j进行遍历,如果当前位置state[i][j]不为MAX,则往左边(右边)一直检查
3.3.如果左边位置k可放置,则state[i][k]为拐点(i,j),即i*COL+j,直到k不可放置或k位置不为MAX

我眼中的uee黑科技

备注: uee是我厂内部的一个前端框架.

这可能是最后一篇关于uee的文章了,因为已经不关注这个方面的技术很久了。术业有专攻,前端嘛,那可怕的前端摩尔定律,还是让专业人士去操心吧。

上个星期有一天,有同事反馈uee的watch不好使,变量已经修改,但watch回调方法不走进去。今天主要围绕这些类似的问题展开,不过呢,今天不对具体问题进行解析,今天主要讲讲uee的黑魔法,大道至简嘛,抽象(原理)和具体(使用)得两手抓,两手都要硬。

下面的内容,主要针对非专业前端(从其他领域过来的开发人员),或者对uee有兴趣的同事。专业人士请绕路。

先进行术语简介。ng1代表angular1.x版本,ng2代表angular2.x以上版本。

uee的本质是ng1

uee是一个前端mvvm框架,常用于SPA(single page application)的开发,虽然开发指南上没有明目张胆的宣传,但底层是ng1是事实,所以ng1.x的文档总是可以借鉴的,网上找到的关于ng1的吐槽也同样适用。关于什么是MVVM,参考阮大的博客http://www.ruanyifeng.com/blog/2015/02/mvcmvp_mvvm.html

ng1和ng2的区别,和雷锋、雷峰塔的区别差不多,外边新项目考虑ng的话,只会考虑ng2之后的版本。uee后来有个ts(typescript)版本,写法上高仿了ng2的写法,不过这里不关注。

ng1的核心概念比较多,DI,scope,双向绑定,指令,digest都是比较重要的,还是那句话,即使使用uee,熟悉ng1的核心概念没有任何坏处。

关于开发模式

这部分主要针对从传统MVC过来的童鞋,因为开发习惯的原因,总是会考虑操作页面,例如某个操作要让按钮高亮,有同学就可能贪方便直接操作style,但这不是正确的做法。mvvm关注的是数据的管理,界面的变化(dom)是自动的。习惯不纠正,写出来的代码可能很诡异。参考文章http://www.infoq.com/cn/news/2013/11/how-to-think-angularjs

变化来自watch

框架的第一印象就是一个页面上一个占位符,只要对应的变量发生变化,页面就会自动变化。这个特性是非常自然的,直到有一天你需要使用watch来监控一些变量,并在发生变化的时候做些什么。

其实,页面变化的魔法也是使用watch机制。所以某个页面上可能会生成非常多watch表达式。这个就是单向绑定的内容了。

例如下面的例子

<div>\{\{content\}\}</div>,就是会生成类似watch("content", function(){//修改div内容})的逻辑。

变化如何被感知 digest过程

现在页面有这么多watch,怎么鉴别有发生变化了?

客户端js是单线程执行的,所以不能写个死循环。可以想象到的做法有2种,一种就是死循环加个timeout或者interval,一种是被动触发。ng1是采用被动触发的,只是就是一些特殊的页面事件会导致检查的发生,这个检查的过程叫digest,俗称dirty check 脏检查。

主要的事件有,页面初始化,页面发生操作(例如点击,输入)等,至于一些异步行为,例如timeout,ajax等,正常是不会触发的,不过使用框架包装过的调用方式,也是会触发的。如果和其他框架例如jq插件等集成的话,或者需要确保调用到digest的话,就需要使用框架提供的apply这个功能,它会确保操作会被页面感知到,相信很多同学也见识过了。

不过,这里还有个细节: 联动更新,例如watch表达式a的时候改了表达式b,同时watch表达式b的时候又会修改a,那么页面中有一个表达式的值可能是旧的。ng1规避的做法比较简单,就是一次digest之后,发现有变更的话,再次执行一次digest,直到所有的表达式的值都稳定了,或者是超过了最大检查次数才停止。

示例伪代码如下:

watches =[] //保存所有的watch表达式和表达式的当前值
for each watch in watches //循环所有的watch表达式
    if watch中的变量发生变化(包括第一次初始化)
        记录表达式的新值
        执行回调,这个过程可能修改了其他变量

if 没有任何表达式发生变化
  exit
else
  重新执行一遍,直到检查达到最大次数

变化没起作用的常见原因

  • 跨页面修改数据

框架的作用域顶多就是一个html页面。但如果项目有复杂的集成方式,那么就可能有多个页面并存的情况,通过a页面去更新b页面的数据变得没那么自然。首先,无论是直接修改变量还是通过所谓的emit事件通知,都有可能没生效(要等b页面下一次digest才能感知到),直接修改dom的话,则存在其他一些问题。所以规避的方式,通常的做法只能调用b页面的某个方法,而这个方法通过嵌套apply来修改变量。

  • 修改数据但没有触发digest

这种常见于采用第三方js插件,或者直接使用普通的ajax,timeout异步操作等情况,同理只能使用apply。

  • ABA问题

ABA概念可以参考知乎文https://www.zhihu.com/question/23281499 就是修改了但没看出变化,例如改了之后又改回去。这种比较特殊,ng会认为你没有变化。开头提到的那个例子,就是某种情况下,一次digest过程中出现了变量又改回原值的情况。所以确实有这种需要,就得多点信息来标记你做了修改,例如增加个时间戳的字段。

  • 变量引用发生变化

意思就是说你修改的和你显示的,已经不是同一个对象了。这个涉及js对象和scope的一些特性,可以参考https://github.com/angular/angular.js/wiki/Understanding-Scopes 这个问题曾经也出现过

谈双向绑定

前面提到了单向绑定,当然双向绑定更是一个非常神奇的特性,特别是你写了一个页面控件,想和某个变量进行绑定,可能就需要考虑了。它的实现过程是这样的: 当变量发生变化的时候,需要修改页面,很明显这个可以通过建立watch表达式实现。另一方面,页面变化的时候,需要修改变量,这个可以通过dom事件,触发包裹在apply中的变量变更操作。掌握这个基本原理的话,在需要定位自带组件问题的情况下,就会减少很多阻碍。

谈自定义gadget

gadget是uee的概念,类似于ng2的component概念,是一种页面组件,包括页面,脚本,样式的大集合。需要了解一点,凡是自定义标签,在ng1中,都采用directive特性实现,只是directive以复杂难懂著称,在使用便利性上,gadget还是做得不错的。如果有需要调试gadget或者ui component的内部实现的情况,就需要掌握指令的各种奇怪接口。

业务开发中的同步与异步

在其他项目习惯了ajax同步操作带来的开发便利性,开始使用uee的时候,可能会发现强大如fire的请求,是没办法做同步的!例如请求a以后,再请求b,这种变得比较麻烦,实现通常是这样的,一是把请求合并,只搞一次就可以了,不过说的容易,实际处理会有很多限制。一种就是在回调方法中发起下一个请求,不过这么写少量还可以,多了就存在一个callback hell的问题。所以应该考虑引入异步控制库让代码更符合人的思维,例如这个async,https://caolan.github.io/async/docs.html

我的看法

uee作为一个前端框架,使用上还是可以的,gadget表现出来的特性也是不错的。不过,也有一些毛病(可能他们觉得是特性)。

一个比较奇怪的就是webroot占位符,宣称可以表示根路径,用来引用静态资源的时候很方便,这套路好难理解,硬生生和后端绑定一起了。而且处理静态资源分离的时候,规则也没那么自然。

另外一个类似fire这种大而全的怪物,源码长达数千行,我总感觉使用fire之后MVVM的边界反而更模糊了。

还有就是,其实uee不是完全定位在纯前端的框架,还包括一个gateway来对接(虽然不是强绑定),包括了一种类似mvc的绑定风格和一种服务总线的绑定实现。说白了,绑定实现是很忌讳的事情,如果它提供一个spring mvc的实现,我会觉得比较安心。

目前最流行的前端开源框架,有ng2,react,vue, ng2的套路比较深,是一个一站式框架,而其他两个更倾向于做好view这一块,其他由外部插件去实现。uee虽然也以时俱进,借鉴了ng2采用原生ts的方式,推出了ts版本,写法和ng2也比较像,不过累感不爱呀,这一次ng2的组件特性已经非常强大了,被人诟病的脏检查也改进了,窃以为直接native也是可以接受的。