Блог

Когда я запускаю следующий код в Intellij с вводом 1000000000000, процесс задерживается на мгновение каждые 8 миллионов циклов.

Почему это так? Почему не выполняется в одном плавном потоке до конца?

 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);
    }
}
  

Условие

 (n   i) == (n ^ i)
  

будет происходить в основном, когда в and нет перекрывающихся битов 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-й бит (начиная с нулевого справа).

12-я степень 2 равна 4096. Итак, все числа меньше 4096 не имеют общих битов с n , поэтому вы будете считать все числа 0-4095. С этого момента вы будете считать только те числа, для которых не установлен 12-й бит. Таким образом, скорость подсчета чисел будет замедляться.

Затем вы попадете на 16-й LSB. Теперь вы будете считать только числа без набора 12-го и 16-го битов. Таким образом, скорость подсчета чисел еще немного замедлится.

и т.д. и т.п.

Единственная причина этих «пауз» заключается в том, что внешний цикл for наивно перебирает все числа вплоть до n : он не просто переходит к следующему числу, для которого выполняется условие.