Java가 10에서 99까지의 모든 숫자의 곱이 0이라고 생각하는 이유는 무엇입니까?
다음 코드 블록은 출력을 0으로 제공합니다.
public class HelloWorld{
public static void main(String []args){
int product = 1;
for (int i = 10; i <= 99; i++) {
product *= i;
}
System.out.println(product);
}
}
왜 이런 일이 발생했는지 설명해 주시겠습니까?
각 단계에서 프로그램이 수행하는 작업은 다음과 같습니다.
1 * 10 = 10
10 * 11 = 110
110 * 12 = 1320
1320 * 13 = 17160
17160 * 14 = 240240
240240 * 15 = 3603600
3603600 * 16 = 57657600
57657600 * 17 = 980179200
980179200 * 18 = 463356416
463356416 * 19 = 213837312
213837312 * 20 = -18221056
-18221056 * 21 = -382642176
-382642176 * 22 = 171806720
171806720 * 23 = -343412736
-343412736 * 24 = 348028928
348028928 * 25 = 110788608
110788608 * 26 = -1414463488
-1414463488 * 27 = 464191488
464191488 * 28 = 112459776
112459776 * 29 = -1033633792
-1033633792 * 30 = -944242688
-944242688 * 31 = 793247744
793247744 * 32 = -385875968
-385875968 * 33 = 150994944
150994944 * 34 = 838860800
838860800 * 35 = -704643072
-704643072 * 36 = 402653184
402653184 * 37 = 2013265920
2013265920 * 38 = -805306368
-805306368 * 39 = -1342177280
-1342177280 * 40 = -2147483648
-2147483648 * 41 = -2147483648
-2147483648 * 42 = 0
0 * 43 = 0
0 * 44 = 0
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
0 * 97 = 0
0 * 98 = 0
일부 단계에서 곱셈은 더 작은 숫자 (980179200 * 18 = 463356416) 또는 잘못된 부호 (213837312 * 20 = -18221056)를 초래하여 정수 오버플로가 있음을 나타냅니다. 그러나 0은 어디에서 오는가? 읽어.
것을 염두에두고 int데이터 타입이 서명 한 32 비트이며 , 2의 보수 정수, 여기에 각 단계에 대한 설명입니다 :
Operation Result(1) Binary Representation(2) Result(3)
---------------- ------------ ----------------------------------------------------------------- ------------
1 * 10 10 1010 10
10 * 11 110 1101110 110
110 * 12 1320 10100101000 1320
1320 * 13 17160 100001100001000 17160
17160 * 14 240240 111010101001110000 240240
240240 * 15 3603600 1101101111110010010000 3603600
3603600 * 16 57657600 11011011111100100100000000 57657600
57657600 * 17 980179200 111010011011000101100100000000 980179200
980179200 * 18 17643225600 100 00011011100111100100001000000000 463356416
463356416 * 19 8803771904 10 00001100101111101110011000000000 213837312
213837312 * 20 4276746240 11111110111010011111100000000000 -18221056
-18221056 * 21 -382642176 11111111111111111111111111111111 11101001001100010101100000000000 -382642176
-382642176 * 22 -8418127872 11111111111111111111111111111110 00001010001111011001000000000000 171806720
171806720 * 23 3951554560 11101011100001111111000000000000 -343412736
-343412736 * 24 -8241905664 11111111111111111111111111111110 00010100101111101000000000000000 348028928
348028928 * 25 8700723200 10 00000110100110101000000000000000 110788608
110788608 * 26 2880503808 10101011101100010000000000000000 -1414463488
-1414463488 * 27 -38190514176 11111111111111111111111111110111 00011011101010110000000000000000 464191488
464191488 * 28 12997361664 11 00000110101101000000000000000000 112459776
112459776 * 29 3261333504 11000010011001000000000000000000 -1033633792
-1033633792 * 30 -31009013760 11111111111111111111111111111000 11000111101110000000000000000000 -944242688
-944242688 * 31 -29271523328 11111111111111111111111111111001 00101111010010000000000000000000 793247744
793247744 * 32 25383927808 101 11101001000000000000000000000000 -385875968
-385875968 * 33 -12733906944 11111111111111111111111111111101 00001001000000000000000000000000 150994944
150994944 * 34 5133828096 1 00110010000000000000000000000000 838860800
838860800 * 35 29360128000 110 11010110000000000000000000000000 -704643072
-704643072 * 36 -25367150592 11111111111111111111111111111010 00011000000000000000000000000000 402653184
402653184 * 37 14898167808 11 01111000000000000000000000000000 2013265920
2013265920 * 38 76504104960 10001 11010000000000000000000000000000 -805306368
-805306368 * 39 -31406948352 11111111111111111111111111111000 10110000000000000000000000000000 -1342177280
-1342177280 * 40 -53687091200 11111111111111111111111111110011 10000000000000000000000000000000 -2147483648
-2147483648 * 41 -88046829568 11111111111111111111111111101011 10000000000000000000000000000000 -2147483648
-2147483648 * 42 -90194313216 11111111111111111111111111101011 00000000000000000000000000000000 0
0 * 43 0 0 0
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
0 * 98 0 0 0
- 는 IS 올바른 결과
- 결과의 내부 표현 (64 비트가 설명에 사용됨)
- 하위 32 비트의 2의 보수로 표현되는 결과
숫자에 짝수를 곱하면 다음과 같습니다.
- 비트를 왼쪽으로 이동하고 0 비트를 오른쪽으로 추가
- 짝수의 결과
따라서 기본적으로 프로그램은 짝수에 다른 숫자를 반복하여 곱하여 오른쪽에서 시작하여 결과 비트를 0으로 만듭니다.
추신 : 곱셈에 홀수 만 포함 된 경우 결과는 0이되지 않습니다.
컴퓨터 곱셈은 실제로 모듈로 2 ^ 32입니다. 곱하기에 2의 거듭 제곱이 충분히 쌓이면 모든 값이 0이됩니다.
여기에 시리즈에 모든 짝수가 있고, 숫자를 나누는 2의 최대 거듭 제곱과 2의 누적 거듭 제곱이 있습니다.
num max2 total
10 2 1
12 4 3
14 2 4
16 16 8
18 2 9
20 4 11
22 2 12
24 8 15
26 2 16
28 4 18
30 2 19
32 32 24
34 2 25
36 4 27
38 2 28
40 8 31
42 2 32
최대 42의 곱은 x * 2 ^ 32 = 0 (mod 2 ^ 32)과 같습니다. 2의 거듭 제곱의 순서는 회색 코드와 관련이 있으며 https://oeis.org/A001511로 나타납니다 .
편집 :이 질문에 대한 다른 응답이 불완전한 이유를 보려면 홀수 정수로만 제한된 동일한 프로그램이 모든 오버플로에도 불구하고 0으로 수렴 하지 않는다는 사실을 고려하십시오 .
정수 오버플로 처럼 보입니다 .
이것 좀 봐
BigDecimal product=new BigDecimal(1);
for(int i=10;i<99;i++){
product=product.multiply(new BigDecimal(i));
}
System.out.println(product);
산출:
25977982938941930515945176761070443325092850981258133993315252362474391176210383043658995147728530422794328291965962468114563072000000000000000000000
출력은 더 이상 int값이 아닙니다 . 그런 다음 오버플로로 인해 잘못된 값을 얻습니다.
오버플로가 발생하면 최소값으로 돌아가서 계속 진행됩니다. 언더 플로가 발생하면 최대 값으로 돌아가서 계속 진행합니다.
더 많은 정보
편집 .
다음과 같이 코드를 변경하자
int product = 1;
for (int i = 10; i < 99; i++) {
product *= i;
System.out.println(product);
}
넣어 :
10
110
1320
17160
240240
3603600
57657600
980179200
463356416
213837312
-18221056
-382642176
171806720
-343412736
348028928
110788608
-1414463488
464191488
112459776
-1033633792
-944242688
793247744
-385875968
150994944
838860800
-704643072
402653184
2013265920
-805306368
-1342177280
-2147483648
-2147483648>>>binary representation is 11111111111111111111111111101011 10000000000000000000000000000000
0 >>> here binary representation will become 11111111111111111111111111101011 00000000000000000000000000000000
----
0
정수 오버플로 때문입니다. 많은 짝수를 곱하면 이진수는 많은 후행 0을 얻습니다. 에 대한 후행 0이 32 개가 넘으면로 int롤오버됩니다 0.
이를 시각화하는 데 도움이되도록 오버플로하지 않는 숫자 유형에 대해 16 진수로 곱한 값이 있습니다. 후행 0이 느리게 커지는 방법 int을 확인하고 마지막 8 자리 16 진수로 구성된 것을 주목하십시오 . 42 (0x2A)를 곱하면 32 비트의 모든 int0이 0입니다!
1 (int: 00000001) * 0A =
A (int: 0000000A) * 0B =
6E (int: 0000006E) * 0C =
528 (int: 00000528) * 0D =
4308 (int: 00004308) * 0E =
3AA70 (int: 0003AA70) * 0F =
36FC90 (int: 0036FC90) * 10 =
36FC900 (int: 036FC900) * 11 =
3A6C5900 (int: 3A6C5900) * 12 =
41B9E4200 (int: 1B9E4200) * 13 =
4E0CBEE600 (int: 0CBEE600) * 14 =
618FEE9F800 (int: FEE9F800) * 15 =
800CE9315800 (int: E9315800) * 16 =
B011C0A3D9000 (int: 0A3D9000) * 17 =
FD1984EB87F000 (int: EB87F000) * 18 =
17BA647614BE8000 (int: 14BE8000) * 19 =
25133CF88069A8000 (int: 069A8000) * 1A =
3C3F4313D0ABB10000 (int: ABB10000) * 1B =
65AAC1317021BAB0000 (int: 1BAB0000) * 1C =
B1EAD216843B06B40000 (int: 06B40000) * 1D =
142799CC8CFAAFC2640000 (int: C2640000) * 1E =
25CA405F8856098C7B80000 (int: C7B80000) * 1F =
4937DCB91826B2802F480000 (int: 2F480000) * 20 =
926FB972304D65005E9000000 (int: E9000000) * 21 =
12E066E7B839FA050C309000000 (int: 09000000) * 22 =
281CDAAC677B334AB9E732000000 (int: 32000000) * 23 =
57BF1E59225D803376A9BD6000000 (int: D6000000) * 24 =
C56E04488D526073CAFDEA18000000 (int: 18000000) * 25 =
1C88E69E7C6CE7F0BC56B2D578000000 (int: 78000000) * 26 =
43C523B86782A6DBBF4DE8BAFD0000000 (int: D0000000) * 27 =
A53087117C4E76B7A24DE747C8B0000000 (int: B0000000) * 28 =
19CF951ABB6C428CB15C2C23375B80000000 (int: 80000000) * 29 =
4223EE1480456A88867C311A3DDA780000000 (int: 80000000) * 2A =
AD9E50F5D0B637A6610600E4E25D7B00000000 (int: 00000000)
가운데 어딘가에 0제품이 있습니다. 따라서 전체 제품은 0이됩니다.
귀하의 경우 :
for (int i = 10; i < 99; i++) {
if (product < Integer.MAX_VALUE)
System.out.println(product);
product *= i;
}
// System.out.println(product);
System.out.println(-2147483648 * EvenValueOfi); // --> this is the culprit (Credits : Kocko's answer )
O/P :
1
10
110
1320
17160
240240
3603600
57657600
980179200
463356416
213837312
-18221056
-382642176
171806720
-343412736
348028928
110788608
-1414463488
464191488
112459776
-1033633792
-944242688
793247744
-385875968
150994944
838860800
-704643072
402653184
2013265920
-805306368
-1342177280 --> Multiplying this and the current value of `i` will also give -2147483648 (INT overflow)
-2147483648 --> Multiplying this and the current value of `i` will also give -2147483648 (INT overflow)
-2147483648 -> Multiplying this and the current value of 'i' will give 0 (INT overflow)
0
0
0
현재 값에 출력 i할 수있는 숫자 를 곱할 때마다0
Since many of the existing answer point to implementation details of Java and debug output, lets have a look at the math behind binary multiplication to really answer the why.
The comment of @kasperd goes in the right direction. Suppose you do not multiply directly with the number but with the prime factors of that number instead. Than a lot of numbers will have 2 as a prime factor. In binary this is equal to a left shift. By commutativity we can multiply with prime factors of 2 first. That means we just do a left shift.
When having a look at binary multiplication rules, the only case where a 1 will result in a specific digit position is when both operand values are one.
So the effect of a left shift is that the lowest bit position of a 1 when further multiplying the result is increased.
Since integer contains only the lowest order bits, they all will be set to 0 when the prime factor 2 is cotnained often enough in the result.
Note that two's complement representation is not of interest for this analysis, since the sign of the multiplication result can be computed independently from the resulting number. That means if the value overflows and becomes negative, the lowest order bits are represented as 1, but during multiplication they are treated again as being 0.
If I run this code What I get all -
1 * 10 = 10
10 * 11 = 110
110 * 12 = 1320
1320 * 13 = 17160
17160 * 14 = 240240
240240 * 15 = 3603600
3603600 * 16 = 57657600
57657600 * 17 = 980179200
980179200 * 18 = 463356416 <- Integer Overflow (17643225600)
463356416 * 19 = 213837312
213837312 * 20 = -18221056
-18221056 * 21 = -382642176
-382642176 * 22 = 171806720
171806720 * 23 = -343412736
-343412736 * 24 = 348028928
348028928 * 25 = 110788608
110788608 * 26 = -1414463488
-1414463488 * 27 = 464191488
464191488 * 28 = 112459776
112459776 * 29 = -1033633792
-1033633792 * 30 = -944242688
-944242688 * 31 = 793247744
793247744 * 32 = -385875968
-385875968 * 33 = 150994944
150994944 * 34 = 838860800
838860800 * 35 = -704643072
-704643072 * 36 = 402653184
402653184 * 37 = 2013265920
2013265920 * 38 = -805306368
-805306368 * 39 = -1342177280
-1342177280 * 40 = -2147483648
-2147483648 * 41 = -2147483648
-2147483648 * 42 = 0 <- produce 0
0 * 43 = 0
Integer Overflow cause -
980179200 * 18 = 463356416 (should be 17643225600)
17643225600 : 10000011011100111100100001000000000 <-Actual
MAX_Integer : 1111111111111111111111111111111
463356416 : 0011011100111100100001000000000 <- 32 bit Integer
Produce 0 cause -
-2147483648 * 42 = 0 (should be -90194313216)
-90194313216: 1010100000000000000000000000000000000 <- Actual
MAX_Integer : 1111111111111111111111111111111
0 : 00000000000000000000000000000000 <- 32 bit Integer
Eventually, the calculation overflows, and eventually that overflow leads to a product of zero; that happens when product == -2147483648 and i == 42. Try this code out to verify it for yourself (or run the code here):
import java.math.BigInteger;
class Ideone {
public static void main (String[] args) throws java.lang.Exception {
System.out.println("Result: " + (-2147483648 * 42));
}
}
Once it's zero, it of course stays zero. Here's some code that will produce a more accurate result (you can run the code here):
import java.math.BigInteger;
class Ideone {
public static void main (String[] args) throws java.lang.Exception {
BigInteger p = BigInteger.valueOf(1);
BigInteger start = BigInteger.valueOf(10);
BigInteger end = BigInteger.valueOf(99);
for(BigInteger i = start; i.compareTo(end) < 0; i = i.add(BigInteger.ONE)){
p = p.multiply(i);
System.out.println("p: " + p);
}
System.out.println("\nProduct: " + p);
}
}
It is an integer overflow.
The int data type is 4 bytes, or 32 bits. Therefore, numbers larger than 2^(32 - 1) - 1 (2,147,483,647) cannot be stored in this data type. Your numerical values will be incorrect.
For very large numbers, you will want to import and use the class java.math.BigInteger:
BigInteger product = BigInteger.ONE;
for (long i = 10; i < 99; i++)
product = product.multiply(BigInteger.valueOf(i));
System.out.println(product.toString());
NOTE: For numerical values that are still too large for the int data type, but small enough to fit within 8 bytes (absolute value less than or equal to 2^(64 - 1) - 1), you should probably use the long primitive.
HackerRank's practice problems (www.hackerrank.com), such as the Algorithms practice section, (https://www.hackerrank.com/domains/algorithms/warmup) include some very good large-number questions that give good practice about how to think about the appropriate data type to use.
'Programing' 카테고리의 다른 글
| ListView가 비어있을 때 빈보기 표시 (0) | 2020.06.29 |
|---|---|
| HttpServletRequest에서 getRequestURI와 getPathInfo 메소드의 차이점은 무엇입니까? (0) | 2020.06.29 |
| LogCat에 필터 옵션이 없습니다. (0) | 2020.06.29 |
| Emacs Ruby 자동 완성 거의 작동 (0) | 2020.06.29 |
| 3 개의 스택으로 큐를 구현하는 방법은 무엇입니까? (0) | 2020.06.29 |