郭艺宾 · 2019年08月14日

雪花算法(02)算法中的位运算

前面介绍了雪花算法的理论基础,可以对大概的算法有个了解,但是细节上可能还是模糊,下面来说一下雪花算法中用到的位运算。这里先介绍两个,一个是:

<<

一个是

|

<<的作用是将数字向左移动,这里的数字指的是二进制中的数,并不是字面上的长整型数字,当然移动后数字字面值肯定发生变化,但是这里对这个操作的主要理解要放在二进制数字向左移动上,而不是字面值扩大2的n次方倍。

“|” 的作用是或运算,两个数对应的位上只要有一个是1就是1,这样的官方解释不太明显,放在雪花算法中的作用就是合并数字,下面会详细演示。也就是说,三个需要生成的部分,分别由三个数来生成,然后利用 <<往左移动到对应的位置,最后将三个数字用 | 合并。这就是雪花算法中两个位移操作的作用。

介绍一个例子比如有三个数字,分别打印出这三个数字的二进制形式:

可以看到,5对应的二进制就是101,8对应的2进制就是1000,10对应的二进制就是1010。这三个数字转换成二进制后,所有的0和1自然还是在最右边的末尾,下面就来进行位移操作a向左移动20位,b向左移动10位,c不变:

通过a和b位移结果的前后对比,可以发现在二进制的形式下,位移操作的意义浅显易懂,就是把代表值的所有数字向左移动了对应的位数。我们把雪花算法生成的数字也分成了三部分,这三部分可以分别按照规则生成,然后用<<操作向左移动对应的位数,就可以到达对应的位置,最后再合并即可。

来看一下合并的代码:

上面的“a|b|c”操作就是合并三个数字,怎么合并呢?就是多个64位的数字对应的合在一起,在这64中,只要对应位数上有一个位置是1,合并后这个位上的数字就是1,否则就是0,根据这个结果,我们看到数字d的二进制形式确实包含了abc三个的所有数字。虽然最后的结果d是一个难以猜到的数字,但是我们进行位运算一定要看二进制,不要看整数字面值,这三个数字放在了各自对应的位数范围内,只要三个数字的范围不越界,也就是说a永远在从右向左20位以后,b永远在10到20之间,c永远在0到10之间,那么这三个数字就可以各管各的,并且结果是合法合理的。

当然这种操作也是有底线的,比如b,他的数字大小转换成2进制后如果长度比10位大,那么它就会和a互相影响,导致结果不可预料,这就是范围的由来。我们再来考虑一下雪花算法,除了第一位0之外,第一部分是时间部分,占41位,也就是说生成的时间数字要向左移动(64-1-41=)22位,第二部分是机器信息,占10位,也即是说代表机器信息的数字生成后要向左移动(64-1-41-10=)12位,当然第三部分在末尾,就不用位移了。这三部分计算出来并且向左位移完成后,直接用“|”运算合成即可,就是我们最终要的分布式唯一id。

代码地址:https://gitee.com/blueses/sno... 02

推荐阅读
关注数
2
文章数
50
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息