for循环使每800万次迭代暂停 - 为什么？

Question

当我在Intellij上运行以下代码并输入1000000000000时,该过程每隔800万个循环保持一个时刻.

为什么会这样？为什么直到最后都没有顺利流动？

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Please type a number");
        long n = in.nextLong();
        System.out.println("Thanks.");

        long count = 0;
        for (long i=0; i<=n; i++) {
            if ((n+i) == (n^i)) {
                count++;
                if (count % 1000000 == 0)
                System.out.println(count);
            }
        }
        System.out.println(count);
    }
}

Answer 1

条件

(n + i) == (n ^ i)

当没有重叠位将主要发生n和i,因为在这种情况下,除了和XOR基本相同的事情.

例如,如果n == 4和i == 3,则在二进制n == 100和i == 011,所以

 n + i == 100 + 011 == 111 == 7
 n ^ i == 100 ^ 011 == 111 == 7

我不相信这个条件也没有共同的位数; 但这些是"显而易见"的案例.

二进制形式为1000000000000

1110100011010100101001010001000000000000

这里最低有效位是第12位(从右边第0位开始).

2的12次幂是4096.因此,所有小于4096的数字都没有共同的位n,所以你将计算所有数字0-4095.从那时起,您将只计算没有设置第12位的数字.因此,计算数字的速度将会减慢.

然后,你将达到第16个LSB.现在,您只计算未设置第12和第16位的数字.因此,计算数字的速度会慢一些.

等等

这些"暂停"的唯一原因是外部for循环天真地遍历所有数字,直到n:它不会简单地跳到条件所适用的下一个数字.