for loop makes pause every 8 million iterations - why?

Question

When I run the following code on Intellij with input 1000000000000 the process holds a moment every 8 million loops.

Why is it like this? Why doesn't run in one smoothly flow until the end?

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

The condition

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

will occur mostly when there are no overlapping bits in n and i, since in that case addition and XOR are basically the same thing.

For example, if n == 4 and i == 3, then in binary n == 100 and i == 011, so

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

I'm not convinced that there are no numbers with bits in common for which the condition also holds; but these are the "obvious" cases for which it is true.

The binary form of 1000000000000 is

1110100011010100101001010001000000000000

The least significant set bit here is the 12th bit (starting from zero-th at the right).

The 12th power of 2 is 4096. So, all of the numbers less than 4096 have no bits in common with n, so you'll count all the numbers 0-4095. From that point on, you'll only count the numbers which don't have the 12th bit set. So, the rate of counting numbers will slow down.

Then, you'll hit the 16th LSB. Now, you'll only count numbers without the 12th and 16th bits set. So, the rate of counting numbers will slow down some more.

etc etc.

The only reason for these "pauses" is the outer for loop naively iterates over all numbers up to n: it doesn't simply skip to the next number for which the condition holds.