楔子在看GC垃圾回收plan_phase的时候 ， 发现了一段特殊的代码，仔细研究下得知，获取当前数字bit位里面为1的个数 。
通过这个bit位为1的个数（count）,来确定挂接当前二叉树子节点的一个地方 。
算法size_t logcount (size_t word){ //counts the number of high bits in a 16 bit word. assert (word < 0x10000); size_t count; count = (word & 0x5555) + ( (word >> 1 ) & 0x5555); count = (count & 0x3333) + ( (count >> 2) & 0x3333); count = (count & 0x0F0F) + ( (count >> 4) & 0x0F0F); count = (count & 0x00FF) + ( (count >> 8) & 0x00FF); return count;}counts the number of high bits in a 16 bit word.这一段英文注释很有误导性，它的意思翻一下大致是：获取当前16位字里面的高位bit数 。如果按照这个理解，基本上不知道这个logcount函数是干嘛的 。
但实际上它做的事情非常简单 。
举个例子：5的二进制：0101,那么经过logcount函数计算之后，返回值为2 。因为5的二进制里面有两个1 。以此类推，6返回2,7返回3,8返回1 。
背景GC垃圾回收的计划阶段 ， 当plan_phase构建二叉树的时候，需要区分根节点，左子节点，和右子节点 。新加入的新节点作为根节点，新节点的左子节点(G)就是上一个根节点（C)的右子节点 。新节点本身又作为上一个根节点(C)的右子节点 。
图：
文章插图
上面这个算法的作用就是，把新加入的新节点挂接到二叉树深度N(logcount返回值）的地方 。图两个二叉树 ， 分别深度为2和3 。logcount返回其参数bit位里面为1的个数 ， 作为二叉树的深度 。然后进行一个挂接 。其行为逻辑是二叉树构建的核心 。
整体GC计划阶段（plan_phase）的二叉树构建主要是为后面的重定位，压缩和清扫做准备 。二叉树是其关键一步 。大致为：
1.区分固定对象和非固定对象，如果非固定对象后面跟着非固定对象就会形成一个堆段，如果后面继续有非固定对象，则继续加入这个小堆段 。如果后面跟着固定对象则到小堆段到此为止 。然后判断固定对象后面是否跟着固定对象 ， 如果是则把这两个固定对象形成一个小堆段 。后面继续判断，如果还是固定对象则加入到小堆段 。如没有，则此小堆段到此为止 。其逻辑跟非固定对象一样 。如此一直遍历完这个堆 ， 这样的话堆里面形成了一个个小堆段 。
2.这些小堆段，会被plan_phase当成一个个的节点，然后把这些节点通过相关的逻辑构建成一颗二叉树 。
3.如果二叉树过于庞大，则无论是在时间还是在空间上的复杂度都很高 。为了避免性能问题，于是引入了brick_table来分割这颗庞大的二叉树
结尾理解其行为，则需联系上下文，查看其整体构建，然后逐步推导 。
【GC plan_phase二叉树挂接的一个算法】
推荐阅读
- vulnhub靶场之THE PLANETS: EARTH
- PLAN 谣言检测——《Interpretable Rumor Detection in Microblogs by Attending to User Interactions》
- .Net CLR GC plan_phase二叉树和Brick_table
- 将 N 叉树编码为二叉树
- 飞机用英语怎么读 飞机用英语怎么读发音airplane
- cause、reason、excuse、explanation，这些英语高频近义词需掌握
- 什么是二叉树的遍历 什么是二叉树
- 飞机的资料 关于飞机的资料
- planning怎么读英语 planning怎么读
- eplan如何导出pdf图纸在哪里找 EPLAN如何导出PDF图纸