なぜそう

Question

Leetcodeの問題を超えて時間を制限するint型、長いません：valid perfect square

私の答えは次のとおりです。

public class Solution { 
    public boolean isPerfectSquare(int num) { 
     int l = 0; 
     int r = (num>>1)+1; 
     while(l<=r) { 
      int mid = (l+r)>>1; 
      long temp = mid*mid;// why long 
      if(temp == num) return true; 
      else if(temp< num) l = mid+1; 
      else r=mid-1; 
     } 
     return false; 
    } 
} 

この回答の制限時間は（とき入力2^31-1）を超えています。しかし、もし私がl、r、中から長時間（intではない）変更した場合、それは動作します。どうして？ ありがとう

Answer 1

コードをデバッグすると、何が問題になっているかを確認できます。 、これは、4つの値lを印刷r、mid、及び六角と小数の両方でtempます

System.out.printf("l=%1$08x=%1$-10d r=%2$08x=%2$-10d mid=%3$08x=%3$-10d temp=%4$016x=%4$d%n", l, r, mid, temp); 
if (temp < 0) 
    throw new IllegalStateException(); 

：「デバッグ」への一つの方法は、print文を挿入し、その右temp割り当てた後、次のコードを挿入することです比較を容易にするために整列される。 明白な内部エラーが発生すると、ifステートメントがループを終了するために挿入され、起動します。

出力isPerfectSquare(Integer.MAX_VALUE)を呼び出す：

l=00000000=0   r=40000000=1073741824 mid=20000000=536870912 temp=0000000000000000=0 
l=20000001=536870913 r=40000000=1073741824 mid=30000000=805306368 temp=0000000000000000=0 
l=30000001=805306369 r=40000000=1073741824 mid=38000000=939524096 temp=0000000000000000=0 
l=38000001=939524097 r=40000000=1073741824 mid=3c000000=1006632960 temp=0000000000000000=0 
l=3c000001=1006632961 r=40000000=1073741824 mid=3e000000=1040187392 temp=0000000000000000=0 
l=3e000001=1040187393 r=40000000=1073741824 mid=3f000000=1056964608 temp=0000000000000000=0 
l=3f000001=1056964609 r=40000000=1073741824 mid=3f800000=1065353216 temp=0000000000000000=0 
l=3f800001=1065353217 r=40000000=1073741824 mid=3fc00000=1069547520 temp=0000000000000000=0 
l=3fc00001=1069547521 r=40000000=1073741824 mid=3fe00000=1071644672 temp=0000000000000000=0 
l=3fe00001=1071644673 r=40000000=1073741824 mid=3ff00000=1072693248 temp=0000000000000000=0 
l=3ff00001=1072693249 r=40000000=1073741824 mid=3ff80000=1073217536 temp=0000000000000000=0 
l=3ff80001=1073217537 r=40000000=1073741824 mid=3ffc0000=1073479680 temp=0000000000000000=0 
l=3ffc0001=1073479681 r=40000000=1073741824 mid=3ffe0000=1073610752 temp=0000000000000000=0 
l=3ffe0001=1073610753 r=40000000=1073741824 mid=3fff0000=1073676288 temp=0000000000000000=0 
l=3fff0001=1073676289 r=40000000=1073741824 mid=3fff8000=1073709056 temp=0000000040000000=1073741824 
l=3fff8001=1073709057 r=40000000=1073741824 mid=3fffc000=1073725440 temp=0000000010000000=268435456 
l=3fffc001=1073725441 r=40000000=1073741824 mid=3fffe000=1073733632 temp=0000000004000000=67108864 
l=3fffe001=1073733633 r=40000000=1073741824 mid=3ffff000=1073737728 temp=0000000001000000=16777216 
l=3ffff001=1073737729 r=40000000=1073741824 mid=3ffff800=1073739776 temp=0000000000400000=4194304 
l=3ffff801=1073739777 r=40000000=1073741824 mid=3ffffc00=1073740800 temp=0000000000100000=1048576 
l=3ffffc01=1073740801 r=40000000=1073741824 mid=3ffffe00=1073741312 temp=0000000000040000=262144 
l=3ffffe01=1073741313 r=40000000=1073741824 mid=3fffff00=1073741568 temp=0000000000010000=65536 
l=3fffff01=1073741569 r=40000000=1073741824 mid=3fffff80=1073741696 temp=0000000000004000=16384 
l=3fffff81=1073741697 r=40000000=1073741824 mid=3fffffc0=1073741760 temp=0000000000001000=4096 
l=3fffffc1=1073741761 r=40000000=1073741824 mid=3fffffe0=1073741792 temp=0000000000000400=1024 
l=3fffffe1=1073741793 r=40000000=1073741824 mid=3ffffff0=1073741808 temp=0000000000000100=256 
l=3ffffff1=1073741809 r=40000000=1073741824 mid=3ffffff8=1073741816 temp=0000000000000040=64 
l=3ffffff9=1073741817 r=40000000=1073741824 mid=3ffffffc=1073741820 temp=0000000000000010=16 
l=3ffffffd=1073741821 r=40000000=1073741824 mid=3ffffffe=1073741822 temp=0000000000000004=4 
l=3fffffff=1073741823 r=40000000=1073741824 mid=3fffffff=1073741823 temp=ffffffff80000001=-2147483647 
Exception in thread "main" java.lang.IllegalStateException 
    at Test.isPerfectSquare(Test.java:14) 
    at Test.main(Test.java:4) 

あなたが見ることができるように、あなたの問題はtempが0に計算された最初の反復、すでに発生します。

これは、0x2000_0000を二乗するときの数値のオーバーフローが原因です。 0x0400_0000_0000_0000である必要がありますが、です。なぜなら、乗算はint数式を使用して行われるからです。

long数学に変更するには、少なくとも1つをlongにキャストします。行をlong temp = (long)mid * mid;に変更します。その変更に伴い

、あなたのデバッグ出力は次のようになります。

l=00000000=0   r=40000000=1073741824 mid=20000000=536870912 temp=0400000000000000=288230376151711744 
l=00000000=0   r=1fffffff=536870911 mid=0fffffff=268435455 temp=00ffffffe0000001=72057593501057025 
l=00000000=0   r=0ffffffe=268435454 mid=07ffffff=134217727 temp=003ffffff0000001=18014398241046529 
l=00000000=0   r=07fffffe=134217726 mid=03ffffff=67108863 temp=000ffffff8000001=4503599493152769 
l=00000000=0   r=03fffffe=67108862 mid=01ffffff=33554431 temp=0003fffffc000001=1125899839733761 
l=00000000=0   r=01fffffe=33554430 mid=00ffffff=16777215 temp=0000fffffe000001=281474943156225 
l=00000000=0   r=00fffffe=16777214 mid=007fffff=8388607 temp=00003fffff000001=70368727400449 
l=00000000=0   r=007ffffe=8388606 mid=003fffff=4194303 temp=00000fffff800001=17592177655809 
l=00000000=0   r=003ffffe=4194302 mid=001fffff=2097151 temp=000003ffffc00001=4398042316801 
l=00000000=0   r=001ffffe=2097150 mid=000fffff=1048575 temp=000000ffffe00001=1099509530625 
l=00000000=0   r=000ffffe=1048574 mid=0007ffff=524287  temp=0000003ffff00001=274876858369 
l=00000000=0   r=0007fffe=524286  mid=0003ffff=262143  temp=0000000ffff80001=68718952449 
l=00000000=0   r=0003fffe=262142  mid=0001ffff=131071  temp=00000003fffc0001=17179607041 
l=00000000=0   r=0001fffe=131070  mid=0000ffff=65535  temp=00000000fffe0001=4294836225 
l=00000000=0   r=0000fffe=65534  mid=00007fff=32767  temp=000000003fff0001=1073676289 
l=00008000=32768  r=0000fffe=65534  mid=0000bfff=49151  temp=000000008ffe8001=2415820801 
l=00008000=32768  r=0000bffe=49150  mid=00009fff=40959  temp=0000000063fec001=1677639681 
l=0000a000=40960  r=0000bffe=49150  mid=0000afff=45055  temp=0000000078fea001=2029953025 
l=0000b000=45056  r=0000bffe=49150  mid=0000b7ff=47103  temp=00000000843e9001=2218692609 
l=0000b000=45056  r=0000b7fe=47102  mid=0000b3ff=46079  temp=000000007e8e9801=2123274241 
l=0000b400=46080  r=0000b7fe=47102  mid=0000b5ff=46591  temp=0000000081629401=2170721281 
l=0000b400=46080  r=0000b5fe=46590  mid=0000b4ff=46335  temp=000000007ff79601=2146932225 
l=0000b500=46336  r=0000b5fe=46590  mid=0000b57f=46463  temp=0000000080acd501=2158810369 
l=0000b500=46336  r=0000b57e=46462  mid=0000b53f=46399  temp=0000000080522581=2152867201 
l=0000b500=46336  r=0000b53e=46398  mid=0000b51f=46367  temp=000000008024d9c1=2149898689 
l=0000b500=46336  r=0000b51e=46366  mid=0000b50f=46351  temp=00000000800e36e1=2148415201 
l=0000b500=46336  r=0000b50e=46350  mid=0000b507=46343  temp=000000008002e631=2147673649 
l=0000b500=46336  r=0000b506=46342  mid=0000b503=46339  temp=000000007ffd3e09=2147302921 
l=0000b504=46340  r=0000b506=46342  mid=0000b505=46341  temp=0000000080001219=2147488281 
l=0000b504=46340  r=0000b504=46340  mid=0000b504=46340  temp=000000007ffea810=2147395600 
false 

Answer 2

整数はプリミティブと呼ばれるグループにあります。このため、Javaでは、整数は小数点以下の桁数を持つことができず、特定の数値を超えることができないという制限があります。そうしないと、スタックオーバーフローエラーが発生します。これを修正するには、変数を整数に設定する代わりに、doubleまたはlongに設定します。ロングは、非常に大きいか小さい数を格納する必要があるときに通常使用されます。ダブルは、通常、2.5または7.78のような数字を使用する必要があるときに使用されます。これらの数値は非常に小さいか、または非常に大きいわけではありませんが、整数として格納できない小数点以下の数値です。これが助けて欲しい！