雪花算法（06）再说几个位运算

lovXin 发布于2019-08-19 10:31 / 2374人阅读

摘要：位二进制表示的最大值雪花算法已经初步完成了。现在我们再来看几个位操作。前面我们说过两个位移操作，那两个我们主要是关注二进制形式的数字效果，这里我们就要看字面值的变化了。

n位二进制表示的最大值

雪花算法已经初步完成了。现在我们再来看几个位操作。先看第一个，还是左移操作，不过这里演示负数左移：

<<

看这个之前，我们先看一个关键的数字，最大的负整数，-1L转换为二进制后的形式：

这里注意二进制数字的思路是相反的，在负整数中，除去负号外，那个数字越大，这个负数就越小，在Java的二进制形式中，首位代表正负号，除去首位，剩下的数字值越大，真的就代表数字本身越大，无论正负。从上面打印可以看出，-1L的二进制形式就是一个最大负整数。

我们前面讨论位运算提到过左移运算 << ，那么负数左移会出现什么情况的呢？下面来看一个例子：

从字面值上来看，负整数左移和正整数左移效果是一样的，就是把字面值变小了，二进制的形式也能看出，所有的1左移后，右面直接补0，效果也是把数字变小了。

前面我们说过两个位移操作，那两个我们主要是关注二进制形式的数字效果，这里我们就要看字面值的变化了。-1L向左位移1位，字面值就变成

-1L * 2^1

如果向左位移n位，字面值就会变成：

-1L * 2^n

这就是-1L向左位移的字面值变化规律。

看完负数左移操作，再来看一个位移操作，取反操作：

取反的意思也是针对二进制形式的数字说的，因为所有位上的数字不是0就是1，所以取反的操作就是把0变成1，把1变成0，来看几个例子：

上面的正整数3L，取反后，字面值变成了-4L，二进制的数字中的0和1也彻底反了，0变成1,1变成0。而负整数-9L字面值变成了8L，二进制数字的变化也是一样的规律。大家可以多试几次，从上面的内容可以总结出取反的规律：

1、取反后，正整数变成了负整数，负整数变成了正整数

2、取反后，无论原来是正数还是负数，结果都会变成   (n+1) * -1L

取反操作我们也不看二进制数字的变化，但看字面值的变化，可以总结出上面的规律。

现在有个需求，如果有三位二进制数，那么能表示的最大正数就是 111，也就是7，如果有四位就是1111，也就是15，如果有n位如何用位运算表示？其实公式很容易推出来，就是

2^n-1

这个公式和上面的负数左移很相似，我们来使用-1L进行左移：

-1L << n

这样n如果是3和4就分别对应-8L和-16L，从字面值上看和我们的需求很接近，我们再来进行取反操作：

~(-1L << n)

这样3和4分别对应的就是7和15了！上面这个位运算公式，就是求出n位二进制数能表示的最大整数的公式！

再来看雪花算法中的限制，数据中心id和机器id分别占5位，最大数都是31，毫秒内序列占12位，最大值是4095，这个值直接定义上是最快的，现在也可以用高效的位运算计算出来了：

不超过最大值的序列递增

雪花算法的毫秒内序列有两个操作，一个是在同一毫秒内加一，另一个是如果超过最大值，就强制等到下一个不同的时间从新开始序列。这里也是可以用位操作实现的。这里首先讨论下面的位操作：

这个操作的意思是同一个位上，都是1，结果才是1，否则就是0.下面用二进制数字演示一下：

15L 转换为2进制形式后有个特点，就是前面所有位上都是1，那么这个时候，其实较小的数是多少结果就是多少。从而可以推理出，只要较大的数有这个特点，那么&操作的结果都和较小的数的值一样。如果超过最大值会怎么样呢？

可以看到，只要超过1，那么结果就会归0，再加上1， 15L & 17L的话，结果又会是1。这样的&操作可以防止数字超过某个最大限制。这种特性正好用在毫秒内序列的加一操作上。

seq = （seq + 1） & 4095；

像上面那种写法，其实最终值和

seq = seq + 1

效果是一样的，不同的是，一旦超过了4095，seq会从新变成0。

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

GPU云服务器云服务器 ruby06 再说 java怎么提出个位多彩雪花

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76172.html

雪花算法（07）雪花算法最终版

摘要：雪花算法初步完成后，我们讨论了几个位运算的写法，大家知道雪花算法一旦确定后，很多数字都是定死的，比如机器占多少位，或者时间向左位移多少，这些在算法具体逻辑确定后就不会变了。雪花算法初步完成后，我们讨论了几个位运算的写法，大家知道雪花算法一旦确定后，很多数字都是定死的，比如机器占多少位，或者时间向左位移多少，这些在算法具体逻辑确定后就不会变了。那么写成最后的数字和用位运算计算出来有什么...

piapia 2019-08-19 10:31 评论0 收藏0
雪花算法（03）生成时间

摘要：前面的理论基础和位运算都了解了，下面我们来生成雪花算法的第一部分，也就是时间部分。这个时候就有一个问题了，如果我们系统的时钟错了会不会有问题会所以要做判断而且系统的时钟错误也是雪花算法的一个致命问题，所以要一定要保证服务器的系统时间正确。前面的理论基础和位运算都了解了，下面我们来生成雪花算法的第一部分，也就是时间部分。时间部分的逻辑起始很简单，就是规定一个起始时间戳，然后用当前时间戳...

张红新 2019-08-19 10:30 评论0 收藏0
雪花算法（01）介绍

摘要：雪花算法生成的最终结果其实就是一个类型的长整型数字，这是一个大前提算法所有的内容都是针对这个数字进行运算的。根据上面的理论可以开始学习雪花算法。针对每个公司，随着服务化演进，单个服务越来越多，数据库分的越来越细，有的时候一个业务需要分成好几个库，这时候自增主键或者序列之类的主键id生成方式已经不再满足需求，分布式系统中需要的是一个全局唯一的id生成规则。既然号称在全局分布式系统中唯一...

or0fun 2019-08-19 10:29 评论0 收藏0
雪花算法（02）算法中的位运算

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

wangbjun 2019-08-19 10:30 评论0 收藏0
分布式id生成方案概述

摘要：序本文主要来聊聊分布式的生成方案。分布式的生成，以为代表的，系列算法采用的就是划分命名空间并行生成的思路。序本文主要来聊聊分布式id的生成方案。目标业务系统需要什么样的ID生成器中提出了几点目标：唯一性时间相关粗略有序可反解可制造主要思路对于每个标识，都需要有一个命名空间（namespace），来保证其相对唯一性。分布式的ID生成，以Twitter Snowf...

Terry_Tai 2019-08-16 10:42 评论0 收藏0