版本比较

标识

  • 该行被添加。
  • 该行被删除。
  • 格式已经改变。

...

这个公式可以返回x的二进制右侧第一个非0的部分,比如:0001,0010,0011,0100,0101,0110,01111000

提示

lowbit(x)的求法是x各位取反再加1,再与x本身进行与操作,比如i=20,其二进制表示为10100,取反之后为01011,加1之后为01100,再与20本身进行与操作,结果为01100&10100,得到结果为100。

Image Added

x各位取反再加1,刚好就是-x的补码表示,所以lowbit(x) = x & -x。

推导出元素个数后,就可以知道cx管理的元素范围为[x-lowbit(x)+1, x]。,比如c8管理的元素范围是[1, 8]

...