java - 为什么这个算法使用Java中的按位与运算符？

Question

我看到一个算法，例如:

    for (int i = 1; i < sums.length; i++) {
        /*
         * dynamic programming:
         * 1. remove a single block from the current subset of blocks
         * 2. the corresponding block sum was already calculated
         * 3. add the number on the removed block to it
         *
         * here: always choose the block corresponding
         * to the least significant bit of i
         */
        int t = Integer.numberOfTrailingZeros(i & -i);
        sums[i] = sums[i & ~(1 << t)] + block[t];

        //only add block subsets that add up to a face
        if (masks.containsKey(sums[i]))
            masks.get(sums[i]).add(i);
    }

根据注释，这行(int t = Integer.numberOfTrailingZeros(i & -i);)作者的意思是根据最低有效位在 block 数组中选择一个元素编号 i。

为什么作者在 i 和 -i 上使用按位与运算符？他们不能只使用 i (例如，Integer.numberOfTrailingZeros(i))吗？

以下是上下文的较大代码体:http://pastebin.com/YB9wsdgD

Answer 1

是的，你可以做到。一些合理的解释:

• 原始版本移植到了具有自制版本的东西，他把这个技巧留在那里。
• 不明白 Integer.numberOfTrailingZeros() 不关心是否还有其他有效位，并且知道如何快速获取最高有效位的值。
• 或者最初有一个自制版本，只是使用 i 和 -i 并进行位移，直到值为零并将其设置为等于 t。有人只是用内置操作替换了该操作，却没有意识到 i & -i 是一个技巧，使删除的操作有效。对零进行检查比其他检查要快，尽管它不再那么重要了，因此一些 super 优化人员经常会安排一些事情来对零进行检查，特别是如果他们不需要做减法的话。

for (var i = 0; i < 1000; i++) {
  document.write(i & -i);
  document.write('<br>');
}

i & -i 返回 2 补码的二进制表示形式，也就是说翻转所有位并加 1。因此，最终只会得到进位的二进制金额。然后您可以确定二进制表示形式中 1 后面有多少个零。通常通过位移直到找到 1，位移的数量是该数字在最低有效位置有多少个零。这可用于进行位移，直到得到零。尽管该代码的 Integer 版本不需要它。