文档章节

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

 郭艺宾
发布于 08/14 13:39
字数 1083
阅读 41
收藏 0

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

<<

一个是

|

<<的作用是将数字向左移动,这里的数字指的是二进制中的数,并不是字面上的长整型数字,当然移动后数字字面值肯定发生变化,但是这里对这个操作的主要理解要放在二进制数字向左移动上,而不是字面值扩大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/snowflake-demo 02

© 著作权归作者所有

粉丝 0
博文 14
码字总数 8746
作品 0
私信 提问
LeetCode算法题-Reverse Bits(Java实现)

这是悦乐书的第185次更新,第187篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第44题(顺位题号是190)。给定32位无符号整数,求它的反转位。例如: 输入:43261596 输出:9...

小川94
2018/11/28
0
0
LeetCode算法题-Hamming Distance(Java实现)

这是悦乐书的第237次更新,第250篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第104题(顺位题号是461)。两个整数之间的汉明距离是相应位不同的位置数。给定两个整数x和y,...

小川94
01/21
0
0
LeetCode.868-二进制距离(Binary Gap)

这是悦乐书的第333次更新,第357篇原创 01看题和准备 今天介绍的是LeetCode算法题中Easy级别的第203题(顺位题号是868)。给定正整数N,找到并返回N的二进制表示中两个连续1之间的最长距离。...

小川94
05/14
0
0
LeetCode算法题-Convert a Number to Hexadecimal(Java实现)

这是悦乐书的第219次更新,第231篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第86题(顺位题号是405)。给定一个整数,写一个算法将其转换为十六进制。对于负整数,使用二进...

小川94
01/03
0
0
LeetCode算法题-Sum of Two Integers(Java实现)

这是悦乐书的第210次更新,第222篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第78题(顺位题号是371)。计算两个整数a和b的总和,但不允许使用运算符+和 - 。例如: 输入:...

小川94
2018/12/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部