雪花算法（02）算法中的位运算

客官°小女子只卖身不卖艺 2021-10-18 16:28 211阅读 0赞

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

一个是

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

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

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NTc4NTE_size_16_color_FFFFFF_t_70][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NTc4NTE_size_16_color_FFFFFF_t_70 1][]

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

来看一下合并的代码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NTc4NTE_size_16_color_FFFFFF_t_70 2][]

上面的“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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NTc4NTE_size_16_color_FFFFFF_t_70]: /images/20211018/b2e2b5cef78247a086dc5c54b9ffadc5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NTc4NTE_size_16_color_FFFFFF_t_70 1]: /images/20211018/8c01f9313f124532b17260aaecd52007.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE4NTc4NTE_size_16_color_FFFFFF_t_70 2]: /images/20211018/c6acefdbc5c7432d9ab6c04e731715db.png