JDK의 원래 이진 검색 알고리즘은 32 비트 정수를 사용했으며 다음과 같은 경우 오버플로 버그가 발생했습니다 (low + high) > INT_MAX
( http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html ) .
(부호있는) 64 비트 정수를 사용하여 동일한 이진 검색 알고리즘을 다시 작성하면 low + high
실제로 10 ^ 18 바이트의 메모리를 갖는 것이 불가능하기 때문에 INT64_MAX를 초과하지 않는다고 가정 할 수 있습니까?
물리 부호를 나타 내기 위해 (부호있는) 64 비트 정수를 사용할 때 언더 플로 및 오버플로가 발생할 수 없다고 가정하는 것이 합리적입니까?
답변
짧은 대답은 ‘아니요’입니다. 그러나 일부 응용 프로그램의 경우 가정이 정확할 수 있습니다.
부호가있는 int (2 ^ 63)를 가정하면 명확성을 위해 쉼표가 추가되어 = 9,223,372,036,854,775,808입니다. 대략 9 * 10 ^ 18입니다. 10 ^ 18은 “Exa”입니다.
Wikipedia에 따르면 “2013 년 현재 월드 와이드 웹은 4 제타 바이트에 도달 한 것으로 추정됩니다. [12]”는 4000 엑사 바이트입니다. 따라서 WWW는 2 ^ 63 바이트보다 약 400 배 더 큽니다 .
따라서 부호있는 (또는 부호없는) 64 비트 정수보다 훨씬 큰 물리량이 하나 이상 있습니다. 단위가 바이트라고 가정합니다 . 단위가 GigaBytes와 같이 훨씬 더 크다면 문제는 없지만 측정 정확도는 떨어집니다.
다른 예를 들어, 멀리 떨어진 은하를 고려하십시오. 안드로메다 은하는 실제로 가장 가까운 것 중 하나이며 2.5 * 10 ^ 6 광년 떨어져 있습니다. 단위가 마일 인 경우 14.5 * 10 ^ 18이며 64 비트 부호있는 정수 이상입니다. 이제는 측정에 사용하는 단위에 따라 다르지만 일부 은하계는 안드로메다보다 훨씬 멀리 떨어져 있습니다. ( 가장 알려진 것 중 13 * 10 ^ 9 LY 거리입니다. ) 측정하려는 정밀도에 따라 64 비트 정수가 오버플로 될 수 있습니다.
( 추가 ) 그렇습니다. 마일은 천문학적 거리를위한 눈에 띄는 단위입니다. 보다 일반적인 단위는 대략 93 백만 마일 인 천문 단위 일 수 있습니다 . 이 측정 단위를 사용하면 가장 먼 알려진 은하계는 대략 10 ^ 15 AU (수학이 옳다면)이며 64 비트 int에 맞습니다. 그러나 달, 근처의 궤도 위성까지의 거리를 측정하려는 경우 해당 장치가 너무 큽니다.
전자 장치의 또 다른 예 : 커패시턴스 단위 인 Farad (F) . 큰 커패시터의 범위는 최대 5kF입니다. 그리고이 수치는 하이브리드 자동차, “스마트 그리드”등이 개선됨에 따라 시간이 지남에 따라 증가 할 것입니다. 일단 10 ^ -18F의 작은 커패시턴스를 측정 할 수 있습니다. 따라서 오늘날 측정 할 수있는 “실제”커패시턴스의 전체 범위는 5 * 10 ^ 21이며 64 비트 정수보다 큽니다.
답변
조합론이 관련되어있을 때 우주로 갈 필요조차 없습니다. 브릿지 게임 에는 2 ^ 95 개의 거래가있을 수 있으며 이는 복잡성의 작은 측면에 있습니다.
답변
귀하의 질문에 가장 적절한 물리량은 컴퓨터 RAM 입니다.
Windows Server 2012 는 최대 4TB 의 실제 메모리 를 지원합니다 . 2 42 바이트입니다. RAM 용량이 매년 약 두 배로 계속 증가하면 지금부터 17 년 만에 “Windows Server 2032″는 2 62 바이트의 실제 메모리를 지원할 것 입니다. 이때 low + high
2 63-2에 도달 하고 최대 부호있는 64 비트 정수에 키스합니다.
64 비트면 충분할 것이라고 가정하면서 안전에 중요한 시스템은 실패하지 않기를 바랍니다.
좀 더 일반적으로 사용하려면 가장 관련성이 높은 물리량은 메모리 주소 공간 입니다. (확장 할 여지가 많은 메모리에 많은 스택을 배치하는 것과 같이 실제 메모리보다 훨씬 큰 주소 공간을 갖는 것이 유용합니다.) 현재 x86-64 구현은 48 비트 가상 주소를 지원하므로 이러한 CPU가 도달하기까지 14 년 밖에 걸리지 않습니다. 2 62 바이트 주소 공간 한계
그리고 “(물리적으로 분리 된) 메모리가 하나의 (논리적으로 공유 된) 주소 공간으로 주소 지정 될 수있는” 분산 공유 메모리 가 있습니다.
답변
어떤 물리량도 오버플로나 언더 플로없이 64 비트 정수로 나타낼 수 있다고 가정하는 것이 합리적입니까?
정확히. 그보다 크고 작은 숫자가 많이 있으므로 부동 소수점 숫자가 있습니다. 부동 소수점 숫자는 더 나은 범위를 위해 정밀도가 떨어집니다.
언급 한 특정 예에서, 그보다 더 큰 숫자가 필요할 가능성은 거의 없습니다. 64 비트는 대략 18 개의 퀸 틸리 온 요소에 해당합니다. 그러나 결코 말하지 마십시오.
답변
부동 소수점 숫자로만 표현할 수있는 물리량은 가정하지 않습니다. 그리고 모든 숫자를 10000으로 곱하여 모든 숫자의 스케일을 결정하더라도 (값은 여전히 정수이지만 10만으로 표현할 수 있습니다),이 체계는 여전히 전자 질량과 같이 0에 매우 가까운 숫자에서는 실패합니다. (9.1094 * 10⎻³¹ kg).
그것은 매우 실제적인 (매우 작은) 물리량입니다 . 여기에 더 많은 문제가 있습니다. 그리고 그것이 실제 물리량이 아니라고 주장한다면 (kg 단위 임에도 불구하고), 다음을 고려하십시오 :
10 kg (obviously physical quantity)
1 kg (same)
10⎻² kg (1/100 kg, or about 1/3 ounce) (also quite real)
그래서 내가 어디로 가고 있는지 알 수 있습니다. 마지막으로 처리 할 수 없습니다.
물론, 정수 부분을 가변 승수로 늘리거나 줄이기 위해 숫자 내에 특수 필드를 가질 수 있습니다. 젠장 이제 방금 부동 소수점을 발명했습니다.
답변
먼저 정수로 나타낼 수있는 물리적 값은 무엇입니까?
정수는 컴퓨터 시스템에서 자연수 (및 그 차이)를 나타내므로 다른 것에 적용하는 것은 잘못입니다. 따라서 연속 영역에 속하는 거리 또는 다른 수량을 호출하는 것은 논쟁이 아닙니다. 이러한 수량에는 실수로 표현됩니다. 그리고 당신은 항상 엄청나게 큰 단위를 선택할 수 있으며 주어진 정밀도로 어떤 값에도 맞출 수 있습니다.
그렇다면 자연수 인 물리적 값은 무엇이며 64 비트 정수를 오버플로 할 수 있습니까?
두 가지를 생각할 수 있습니다. 원자와 같은 물리적 물체의 수와 양자 시스템이 가질 수있는 에너지 레벨. 이것은 엄격하게 정수인 두 가지입니다. 이제, 당신이 원자를 분리 할 수 있다는 것을 알고 있지만, 여전히 정수량을 생성하며 무기한으로 분리 할 수 없습니다. 둘 다 부호없는 정수의 64 비트 범위를 쉽게 능가 할 수 있습니다 . 원자의 수가 많고 하나의 원자가 둘 이상의 에너지 상태에있을 수 있습니다.
정보가 물리적이든 아니든간에 매우 논쟁의 여지가 있습니다. 나는 그렇지 않다고 말할 것입니다. 따라서 나는 많은 양의 정보가 물리적 인 것이라고 말하지 않을 것입니다. RAM의 양이나 그와 비슷한 것은 아닙니다. 이것을 허용한다면 오늘날의 기술로 1 비트를 저장하기 위해 하나 이상의 원자가 필요하기 때문에 쉽게 원자의 수가이 수를 능가합니다.
답변
Jerry101의 답변 외에도 정확성에 대한 매우 간단하고 실용적인 테스트를 제공하고 싶습니다.
malloc
64 비트 OS에서을 통해 메모리를 할당한다고 가정합니다 . 메모리 할당자가 요청한 크기의 63 비트 비트가 설정된 유효한 메모리 블록을 반환한다고 가정합니다.
다시 말해, 0xFFFFFFFFxxxxxxxx
호출에서 반환 될 수있는 합법적 인 메모리 범위 인 프로그래밍 환경이 있다고 가정 해 봅시다 malloc
.
문제는 코드가 여전히 의도 한대로 작동합니까?
32 비트 운영 체제와 유사한 상황이 발생하면 일부 소프트웨어에 “상위 절반”에 메모리 주소가 제공되면 제대로 작동하지 않은 것입니다. 원래 이러한 메모리 주소는 권한있는 코드 (운영 체제, 장치 드라이버 및 주변 장치 하드웨어)에서만 사용할 수있는 것으로 생각되었지만 32 비트 주소 공간 크런치 때문에 OS 공급 업체는 예약 된 공간의 일부를 그것을 요구하는 응용 프로그램.
다행히도,이 상황은 적어도 10 년이 아닌 한동안 64 비트 프로그램에서 일어날 가능성이 거의 없습니다.
이러한 상황이 마침내 발생하면 이는 128 비트 주소 지정 가능 프로세서 및 운영 체제가 그 당시 주류가되었고 “레거시 응용 프로그램”이 작동 할 수 있도록 “64 비트 에뮬레이션 환경”을 제공 할 수 있음을 의미합니다. 오늘날의 64 비트 운영 체제와 유사한 가정 하에서.
마지막으로이 설명은 메모리 주소에만 중점을 둡니다. 특정 타임 스탬프 형식은 마이크로 초에 많은 양의 정밀도를 할당하므로 향후 시간을 나타내는 데 사용할 수있는 비트 수가 더 적기 때문에 타임 스탬프와 유사한 문제를 더 예방해야합니다. 이러한 문제는 2038 년 문제 에 관한 Wikipedia 기사에 요약되어 있습니다 .