Rocket - diplomacy - enumerateMask

分手后的思念是犯贱 2021-12-18 14:03 137阅读 0赞

[https://mp.weixin.qq.com/s/s3hr5JJX2\_pwNgdu8WqV0Q][https_mp.weixin.qq.com_s_s3hr5JJX2_pwNgdu8WqV0Q]

介绍enumerateMask的实现。（仅供理解，非严谨证明）

![0][]

**1. 基本定义**

enumerateMask的意思是枚举掩码。其功能是把mask中为1的位的所有组合枚举出来。

enumerateMask方法的功能比较简单独立，可以直接执行进行验证：

![0 1][]

执行结果如下：

![0 2][]

**2. helper(id, tail)**

helper方法有两个参数：

a. id：指当前枚举的mask；

b. tail：包含已经枚举的mask；

第一个被枚举的mask为0，即不包含任何比特位。

所以helper的初始调用为：helper(0, Nil)

**3. id == mask**

若id == mask，则id中已经包含了mask中所有的为1的比特，所以可以结束枚举过程了。

可以看出，枚举的过程是从0到mask，逐渐增加id中1的位数，id成递增变化，搜集所有组合。

**4. id != mask**

若id != mask，则把id加入到tail中，计算下一个id，并继续进行枚举。

![0 3][]

**5. mask中为0的位**

![0 4][]

next\_id = ((~mask | id) + 1) & mask

因为最后都是要和mask相与，所以mask中为0的位，在next\_id中也同样为0。

所以：

a. mask中为0的位，在id中对应的位始终为0。

b. id中为1的位，在mask中对应的位一定为1。

另外：

c. mask中为0的位，直接向高位透传被加的1。

**6. mask为全1**

![0 5][]

即next\_id = id + 1。

**7. mask中的0：相当于不存在**

next\_id = ((~mask | id) + 1) & mask

a. ~mask：mask取反会将其中为1的位也取反，但最后&mask之后会被清除，不在最终结果中出现；

b. |id：id中为1的位在mask中也都为1，所以“|id”的逻辑运算不涉及mask中为0的位；

c. +1：mask中为0的位，向高一位透传加1的动作，自己本身的值在加1之后虽然有变化，但不在最终结果中体现；加1的动作必定在mask中某一个为1的位结束；

所以，可以忽略mask中0的存在，直接把mask中为1的位提取出来进行运算（如同第6节所述），然后再把0填到结果的相应位中即可。

**8. 附录**

**def enumerateMask(mask: BigInt): Seq\[BigInt\] = \{**

**def helper(id: BigInt, tail: Seq\[BigInt\]): Seq\[BigInt\] =**

**if (id == mask) (id +: tail).reverse else helper(((~mask | id) + 1) & mask, id +: tail)**

helper(0, *Nil)*

\}

转载于:https://www.cnblogs.com/wjcdx/p/10669793.html

[https_mp.weixin.qq.com_s_s3hr5JJX2_pwNgdu8WqV0Q]: https://mp.weixin.qq.com/s/s3hr5JJX2_pwNgdu8WqV0Q
[0]: /images/20211218/16472781f89046daadd40477a6a4837c.png
[0 1]: /images/20211218/1dda424b34ef4ab1a5b3829cc23185cf.png
[0 2]: /images/20211218/956e3a2c35f7489fa2d8b61481a4d6fc.png
[0 3]: /images/20211218/bd1e0b1142994ae0857a72800376c019.png
[0 4]: /images/20211218/62af05c63d654a6bb6dfc73e7556b067.png
[0 5]: /images/20211218/7eb6c007dd4e416f905dbf0bff1a8814.png

发表评论取消回复

表情：

评论列表（有 0 条评论，137人围观）

还没有评论，来说两句吧...

相关阅读

相关 Rocket 架构设计

1 技术架构 ![img][] RocketMQ架构上主要分为四部分，如上图所示: Producer：消息发布的角色，支持分布式集群方式部署。Producer通

我会带着你远行/ 2022年10月18日 12:42/ 0 赞/ 26 阅读

相关 Rocket - util - HeterogeneousBag

[https://mp.weixin.qq.com/s/5hNM4yeQjaLvAJzgMG9PGQ][https_mp.weixin.qq.com_s_5hNM4yeQjaL

ゞ浴缸里的玫瑰/ 2021年12月18日 14:05/ 0 赞/ 202 阅读

相关 Rocket - util - Repeater

[https://mp.weixin.qq.com/s/xyEq3DgYuf2QuNjssv8pkA][https_mp.weixin.qq.com_s_xyEq3DgYuf2

逃离我推掉我的手/ 2021年12月18日 14:05/ 0 赞/ 210 阅读

相关 Rocket - util - IDPool

[https://mp.weixin.qq.com/s/Pe7FGKzfRufzzYDrl0fQ7g][https_mp.weixin.qq.com_s_Pe7FGKzfRuf

不念不忘少年蓝@/ 2021年12月18日 14:05/ 0 赞/ 171 阅读

相关 Rocket - util - Broadcaster

[https://mp.weixin.qq.com/s/ohBVNAXZUA538qSxfBGMKA][https_mp.weixin.qq.com_s_ohBVNAXZUA5

小咪咪/ 2021年12月18日 14:03/ 0 赞/ 165 阅读

相关 Rocket - diplomacy - enumerateMask

[https://mp.weixin.qq.com/s/s3hr5JJX2\_pwNgdu8WqV0Q][https_mp.weixin.qq.com_s_s3hr5JJX2_

分手后的思念是犯贱/ 2021年12月18日 14:03/ 0 赞/ 138 阅读

相关 Rocket - tilelink - Broadcast

[https://mp.weixin.qq.com/s/-pjCLzzincJz0Z66orx8kg][https_mp.weixin.qq.com_s_-pjCLzzincJ

╰+攻爆jí腚メ/ 2021年10月29日 11:36/ 0 赞/ 265 阅读

相关 Rocket - tilelink - fastProperty

[https://mp.weixin.qq.com/s/9nikweQUGG5FO3Z8t6feaw][https_mp.weixin.qq.com_s_9nikweQUGG5

迈不过友情╰/ 2021年10月19日 04:22/ 0 赞/ 224 阅读

相关 C. Basic Diplomacy （思维、贪心）

[题目][Link 1] 思路：首先为NO的情况只有，某一天只可以选一个人且某人在只可以选他的情况下被选了>⌈m2⌉次。除了这种情况，其它情况不可能为NO，看一个极端的例

谁践踏了优雅/ 2021年07月16日 23:17/ 0 赞/ 397 阅读

相关 Rocket - util - MultiWidthFifo

基本介绍实现一个输入宽度为inW，输出宽度为outW，可存n个outW宽度元素的FIFO。 a. 如果inW == outW，直接使用队列（Queue）实现； b....

系统管理员/ 2021年03月28日 12:58/ 0 赞/ 491 阅读