c – 用于for循环的位操作

发布时间：2020-12-16 03:00:02 所属栏目：百科来源：网络整理

导读：我在算法的源代码中发现了这个循环.我认为这些问题的细节在这里是不相关的,因为这是解决方案的一小部分. void update(int i,int value,int array[],int n) { for(; i n; i += ~i (i + 1)) { array[i] += value; }} 我真的不明白在for循环中会发生什么,这是一

我在算法的源代码中发现了这个循环.我认为这些问题的细节在这里是不相关的,因为这是解决方案的一小部分.

void update(int i,int value,int array[],int n) {
        for(; i < n; i += ~i & (i + 1)) {
            array[i] += value;
        }
}

我真的不明白在for循环中会发生什么,这是一种技巧吗？我发现了类似的Fenwick树,但是它们看起来和我在这里有些不同.

任何想法这个循环意味着什么？

另外,发现这个：

“Bit Hack#9.隔离最右边的0位.

y =?x& (x 1)
“

解决方法

你是对的：bit-hack?我& (i 1)应该计算一个全为二进制0的整数,除了对应于i的最右边的零位的一个,它被设置为二进制1.

所以在for循环的每次通过结束时,它将此值添加到自身中.由于i中的相应位为零,这具有设置它的效果,而不影响i中的任何其他位.这将严格增加每次通过i的值,直到我溢出(或者如果您开始使用i <0,则为-1).在上下文中,您可能希望在i> = 0时调用它,n设置在你的索引离开数组之前终止循环.

整体功能应该具有通过从最初到最高有效值的i的原始值的零位进行迭代的效果,逐个设置它们,并递增数组的相应元素.

芬威克树是一种有效累积和查询统计数据的聪明方式;正如你所说,他们的更新循环看起来有点像这样,并且通常使用可比较的位黑客.必须有多种方式来完成这种点阵,所以您的源代码当然可以更新Fenwick树,或者可比较的东西.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!