（数）& （-数） [英] meaning of (number) & (-number)

问题描述

（number）& （-number）？我已搜索，但无法找到含义

我想使用 i&（ - i） for循环：

  for（i = 0; i <= n; i + = i&（ -  i））
  

&是位运算符

解决方案

假设2的补码（或 i unsigned）， -i 等于〜i + 1 。

$ b b

i& （〜i + 1）是提取 i 的最低设置位的技巧。

它的工作原理，因为+1实际上是设置最低清除位，并清除所有低于该位。因此，在 i 和〜i + 1 中设置的唯一位是从 i （即〜i 中最低的清除位）。在〜i + 1 中清除低于该位的位，并且 i 和〜i 。

在循环中使用它看起来很奇怪，除非循环体修改 i ，因为 i = i& （-i）是一个幂等操作：重复两次给出相同的结果。

代码实际上是 i + = i& （-i）。那么非零 i 的作用是清除 i 的最低位的一组位，并设置对于 i ，没有清除位高于最低设置位（包括 i = 0 ），它将 i 设置为0.因此，如果不是因为 i 开始于 0 ，每个循环将通过至少增加 i 上一个循环，有时更多，直到最终它超过 n ，并断开或转到 0 p>

这样写代码通常是不可原谅的，但是根据问题的域，也许这是一个明显的序列的值循环。]

What is the meaning of (number) & (-number)? I have searched it but was unable to find the meaning

I want to use i&(-i) in for loop like:

for(i=0;i<=n;i+=i&(-i))  

& is the bitwise operator

解决方案

Assuming 2's complement (or that i is unsigned), -i is equal to ~i+1.

i & (~i + 1) is a trick to extract the lowest set bit of i.

It works because what +1 actually does is to set the lowest clear bit, and clear all bits lower than that. So the only bit that is set in both i and ~i+1 is the lowest set bit from i (that is, the lowest clear bit in ~i). The bits lower than that are clear in ~i+1, and the bits higher than that are non-equal between i and ~i.

Using it in a loop seems odd unless the loop body modifies i, because i = i & (-i) is an idempotent operation: doing it twice gives the same result again.

[Edit: in a comment elsewhere you point out that the code is actually i += i & (-i). So what that does for non-zero i is to clear the lowest group of set bits of i, and set the next clear bit above that, for example 101100 -> 110000. For i with no clear bit higher than the lowest set bit (including i = 0), it sets i to 0. So if it weren't for the fact that i starts at 0, each loop would increase i by at least twice as much as the previous loop, sometimes more, until eventually it exceeds n and breaks or goes to 0 and loops forever.

It would normally be inexcusable to write code like this without a comment, but depending on the domain of the problem maybe this is an "obvious" sequence of values to loop over.]

这篇关于（数）& （-数）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！