her 8 milyon yinelemeyi duraklatıyor - neden?

Question

Aşağıdaki kodu 1000000000000 girişi ile Intellij'de çalıştırdığımda işlem her 8 milyon döngüde bir an tutar.

Neden böyle? Neden sonuna kadar akıcı bir şekilde akmaz?

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

orada n ve i hiçbir örtüşen bitleri bu durumda ek beri vardır ve XOR temelde aynı şey olduğunda

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

çoğunlukla meydana gelecektir koşulu. Örneğin

, n == 4 ve i == 3, o zaman ikili n == 100 ve i == 011 yılında, yani

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

Ben koşulu da sahip olduğu ve ortak bit ile numara bulunmayan tereddütlerim var; ama bunlar doğru olduğu "bariz" durumlardır.

1000000000000 ikili bir şekilde

1110100011010100101001010001000000000000 

burada en az önemli bit, (sağ sıfır th başlayarak) 12 bit.

2'nin 12. gücü 4096'dır. Yani, 4096'dan küçük tüm sayıların n ile ortak bitleri yoktur, dolayısıyla 0-4095 arasındaki tüm sayıları sayabilirsiniz. Bu noktadan, sadece 12. bit kümesine sahip olmayan sayıları sayarsınız. Yani, sayma oranı yavaşlar.

Ardından, 16. LSB'ye basacaksınız. Şimdi, sadece 12. ve 16. bitler olmadan sayıları sayarsınız. Yani, sayma oranlarının oranı biraz daha yavaşlayacaktır.

vs vs

bu "duraklar" tek nedeni n kadar olan tüm sayıların üzerine safça yineler döngü için dış iyisidir: sadece koşul tutan bir sonraki numaraya atlamak olmaz.