shopkeeper/korean_wiki_content_only_120125 huggingface dataset:
이러한 각 숫자 체계는 위치 체계이지만, 십진법의 가중치가 10의 거듭제곱인 반면, 팔진법의 가중치는 8의 거듭제곱이고 16진법의 가중치는 16의 거듭제곱이다. 16진수나 팔진수를 십진수로 변환하려면, 각 자리에 대해 숫자의 값을 해당 위치의 값으로 곱한 다음 그 결과를 더한다. 예를 들어:
이진수로 분수 표현.
고정소수점 숫자.
고정소수점 형식은 이진수로 분수를 표현하는 데 유용할 수 있다.
원하는 정밀도와 범위에 필요한 비트 수는 숫자의 소수 부분과 정수 부분을 저장하기 위해 선택해야 한다. 예를 들어, 32비트 형식을 사용하는 경우, 정수 부분에 16비트, 소수 부분에 16비트를 사용할 수 있다.
8의 자릿수 다음에는 4의 자릿수, 그 다음에는 2의 자릿수, 그 다음에는 1의 자릿수가 온다. 소수 비트는 정수 비트가 설정한 패턴을 계속한다. 다음 비트는 1/2의 비트, 그 다음에는 1/4의 비트, 그 다음에는 1/8의 비트 등이다. 예를 들어:
이러한 인코딩 형식은 일부 값을 이진수로 나타낼 수 없다. 예를 들어, 십진수로 0.2인 분수 는 가장 가까운 근사치가 다음과 같다:
더 많은 자릿수를 사용하더라도 정확한 표현은 불가능하다. 십진수로 0.333333333...으로 쓰이는 숫자 은 무한히 계속된다. 일찍 종료되면 값은 을 정확하게 나타내지 않는다.
부동소수점 숫자.
디지털 시스템에서 부호 없는 정수와 부호 있는 정수 모두 사용되지만, 32비트 정수조차도 계산기가 처리할 수 있는 모든 범위의 숫자를 처리하기에 충분하지 않으며, 이는 분수를 포함하지도 않는다. 실수의 더 넓은 범위와 정밀도를 근사화하기 위해 우리는 부호 있는 정수와 고정 소수점 숫자를 버리고 "부동소수점" 형식으로 가야 한다.
십진법에서 우리는 다음과 같은 형태의 부동소수점 숫자에 익숙하다 (과학적 기수법):
또는 더 간결하게:
이는 "1.1030402 곱하기 1 뒤에 0이 5개"를 의미한다. 우리는 "유효 숫자"로 알려진 특정 숫자 값(1.1030402)을 가지며, 이는 "지수"로 알려진 10의 거듭제곱(E5, 즉 105 또는 100,000을 의미)으로 곱해진다. 음수 지수가 있으면 그 숫자는 소수점 오른쪽으로 그만큼의 자릿수만큼 1을 곱한다. 예를 들어:
이 방식의 장점은 지수를 사용하여 훨씬 더 넓은 범위의 숫자를 얻을 수 있다는 것이다. 비록 유효 숫자의 자릿수, 즉 "숫자 정밀도"가 범위보다 훨씬 작더라도 말이다. 유사한 이진 부동소수점 형식은 컴퓨터에 대해 정의될 수 있다. 이러한 방식은 여러 가지가 있으며, 가장 널리 사용되는 것은 IEEE에 의해 정의되었다. IEEE 754-2008 표준 사양은 다음과 같은 64비트 부동소수점 형식을 정의한다.
8바이트 메모리에 저장된 비트:
"S"는 부호 비트, "x"는 지수 비트, "m"은 유효 숫자 비트를 나타낸다. 여기서 추출된 비트는 다음 계산으로 변환된다.
이 방식은 약 15십진 자릿수까지 유효한 숫자를 제공하며, 숫자의 범위는 다음과 같다.
이 사양은 또한 정의되지 않은 여러 특수 값을 정의하며, "숫자가 아님"을 의미하는 NaN으로 알려져 있다. 이는 프로그램에서 유효하지 않은 연산 등을 지정하는 데 사용된다.
일부 프로그램은 32비트 부동소수점 숫자도 사용한다. 가장 일반적인 방식은 부호 비트와 23비트 유효 숫자를 사용하며, "excess-127" 형식의 8비트 지수를 사용하여 7개의 유효한 십진 자릿수를 제공한다.
비트는 다음 계산으로 숫자 값으로 변환된다.
다음과 같은 범위의 숫자가 생성된다.
이러한 부동소수점 숫자는 일반적으로 "실수" 또는 "부동소수점"으로 알려져 있지만, 여러 가지 변형이 있다.
32비트 부동소수점 값은 때때로 "real32" 또는 "single"이라고 불리며, "단정밀도 부동소수점 값"을 의미한다.
64비트 부동소수점은 때때로 "real64" 또는 "double"이라고 불리며, "배정밀도 부동소수점 값"을 의미한다.
숫자와 비트 패턴 사이의 관계는 컴퓨터 조작의 편의를 위해 선택된다. 컴퓨터 메모리에 저장된 8바이트는 64비트 실수, 두 개의 32비트 실수, 또는 네 개의 부호 있는 또는 부호 없는 정수, 또는 8바이트에 맞는 다른 종류의 데이터를 나타낼 수 있다. 유일한 차이점은 컴퓨터가 이를 해석하는 방식이다. 컴퓨터가 네 개의 부호 없는 정수를 저장한 다음 이를 64비트 실수로 메모리에서 다시 읽어들인다면, 거의 항상 완벽하게 유효한 실수이겠지만, 이는 쓰레기 데이터일 것이다.
주어진 비트 수로는 유한한 범위의 실수만 표현할 수 있다. 산술 연산은 오버플로 또는 언더플로가 발생하여 표현할 수 없을 정도로 너무 크거나 너무 작은 값을 생성할 수 있다.
표현은 제한된 정밀도를 갖는다. 예를 들어, 64비트 실수로는 15자리 십진수만 표현할 수 있다. 아주 작은 부동소수점 숫자가 큰 숫자에 더해지면 결과는 그냥 큰 숫자가 된다. 작은 숫자는 15자리 또는 16자리의 해상도에 나타나기에는 너무 작아서 컴퓨터는 효과적으로 이를 버린다. 제한된 정밀도의 영향을 분석하는 것은 잘 연구된 문제이다. 반올림 오류의 크기 추정 및 대규모 계산에서 그 영향을 제한하는 방법은 모든 대규모 계산 프로젝트의 일부이다. 정밀도 제한은 범위 제한과 다르다. 이는 지수에는 영향을 미치지 않고 유효 숫자에 영향을 미치기 때문이다.
유효 숫자는 십진 분수와 반드시 완벽하게 일치하지 않는 이진 분수이다. 많은 경우에 2의 역수 거듭제곱의 합은 특정 십진 분수와 일치하지 않으며, 계산 결과는 약간 오차가 있을 수 있다. 예를 들어, 십진 분수 "0.1"은 무한히 반복되는 이진 분수 0.000110011 ...과 동등하다.
프로그래밍 언어의 숫자.
어셈블리어로 프로그래밍하려면 프로그래머가 숫자의 표현을 추적해야 한다. 프로세서가 필요한 수학 연산을 지원하지 않는 경우, 프로그래머는 연산을 수행할 적절한 알고리즘과 명령어 시퀀스를 고안해야 한다. 일부 마이크로프로세서에서는 정수 곱셈조차도 소프트웨어로 수행해야 한다.
루비 및 파이썬과 같은 상위 프로그래밍 언어는 유리수, 큰 정수 또는 복소수와 같이 확장된 유형일 수 있는 추상 숫자를 제공한다. 수학 연산은 언어 구현에서 제공하는 라이브러리 루틴에 의해 수행된다. 소스 코드의 주어진 수학 기호는 연산자 오버로딩에 의해 숫자 유형의 표현에 적합한 다른 오브젝트 코드를 호출한다. 부호 있는, 부호 없는, 유리수, 부동소수점, 고정소수점, 정수 또는 복소수 등 어떤 숫자든 수학 연산은 정확히 동일한 방식으로 작성된다.
REXX 및 자바와 같은 일부 언어는 십진 부동소수점 연산을 제공하여 다른 형태의 반올림 오류를 발생시킨다.
정보기술과 컴퓨터 과학에서 시스템은 이전 이벤트나 사용자 상호작용을 기억하도록 설계된 경우 스테이트풀(stateful), 즉 상태 저장으로 설명된다. 기억된 정보를 시스템의 상태(state)라고 부른다.
시스템이 차지할 수 있는 상태 집합은 상태 공간으로 알려져 있다. 이산 시스템에서 상태 공간은 가산이고 종종 유한하다. 시스템의 내부 동작 또는 환경과의 상호작용은 입력 수락 또는 출력 생성과 같이 개별적으로 발생하는 개별 동작 또는 이벤트로 구성되며, 이는 시스템이 상태를 변경하게 할 수도 있고 하지 않을 수도 있다. 이러한 시스템의 예로는 디지털 논리 회로 및 구성 요소, 오토마타 및 형식 언어, 컴퓨터 프로그램 및 컴퓨터가 있다.
어떤 시점에서든 디지털 회로나 결정론적 컴퓨터 프로그램의 출력은 현재 입력과 상태에 의해 완전히 결정된다.
디지털 논리 회로 상태.
디지털 논리 회로는 두 가지 유형으로 나눌 수 있다. 출력 신호가 현재 입력 신호에만 의존하는 조합 논리와 출력이 현재 입력과 이전 입력 이력 모두의 함수인 순차 논리이다. 순차 논리에서 이전 입력 정보는 플립플롭과 같은 전자 메모리 요소에 저장된다. 특정 시점에서 이 메모리 요소의 저장된 내용은 집합적으로 회로의 상태라고 불리며 회로가 접근할 수 있는 과거에 대한 모든 정보를 포함한다.
플립플롭과 같은 각 이진 메모리 요소는 0 또는 1의 두 가지 가능한 상태만 가지며, 유한한 수의 메모리 요소가 있으므로 디지털 회로는 특정 유한한 수의 가능한 상태만 가진다. 회로의 이진 메모리 요소 수가 N이면 회로가 가질 수 있는 최대 상태 수는 2"N"이다.
프로그램 상태.
마찬가지로, 컴퓨터 프로그램은 변수에 데이터를 저장하며, 이는 컴퓨터의 메모리에 있는 저장 위치를 나타낸다. 프로그램 실행의 특정 시점에서 이 메모리 위치의 내용은 프로그램의 상태라고 불린다.
상태에 대한 보다 특수한 정의는 데이터 스트림에서 직렬 또는 순차적으로 작동하는 구문 분석기, 방화벽, 통신 프로토콜 및 암호화와 같은 컴퓨터 프로그램에 사용된다. 직렬 프로그램은 수신 데이터 문자 또는 패킷을 순차적으로 한 번에 하나씩 처리한다. 이러한 프로그램 중 일부에서는 이전에 수신된 데이터 문자 또는 패킷에 대한 정보가 변수에 저장되고 현재 문자 또는 패킷 처리에 영향을 미치는 데 사용된다. 이를 스테이트풀 프로토콜이라고 하며 이전 처리 주기에서 전달된 데이터를 상태라고 한다. 다른 프로그램에서는 이전 데이터 스트림에 대한 정보가 없으며 각 데이터 입력과 함께 새로 시작한다. 이를 무상태 프로토콜이라고 한다.
명령형 프로그래밍은 프로그램 상태와 프로그램 상태를 변경하는 문장 측면에서 계산을 설명하는 프로그래밍 패러다임 (프로그래밍 언어를 설계하는 방식)이다. 상태 변경은 프로그램 런타임에 의해 암묵적으로 관리되므로 서브루틴은 가시성을 가지며, 이는 부작용으로 알려진 프로그램의 다른 부분에 의해 이루어진 상태 변경을 볼 수 있다.
선언형 프로그래밍 언어에서는 프로그램이 원하는 결과를 설명하고 상태 변경을 직접 지정하지 않는다.
함수형 프로그래밍에서 상태는 일반적으로 시간 논리를 사용하여 프로그램 실행의 각 단계에서 프로그램 상태를 나타내는 명시적 변수로 표현된다. 상태 변수는 상태 변환 함수의 입력 매개변수로 전달되며, 업데이트된 상태는 반환 값의 일부로 반환된다. 순수 함수형 서브루틴은 해당 범위의 상태 변수로 표현되는 상태 변경에 대한 가시성만 가진다.
순차 회로나 컴퓨터 프로그램의 출력은 어떤 시점에서든 현재 입력과 현재 상태에 의해 완전히 결정된다. 각 이진 메모리 요소는 0 또는 1의 두 가지 가능한 상태만 가지므로 회로가 취할 수 있는 총 다른 상태의 수는 유한하며 메모리 요소의 수에 의해 고정된다. N개의 이진 메모리 요소가 있다면 디지털 회로는 최대 2N개의 고유한 상태를 가질 수 있다. 상태의 개념은 순차 디지털 회로와 컴퓨터 프로그램을 설계하는 데 사용되는 유한 상태 기계라고 불리는 추상 수학적 계산 모델에서 공식화된다.
상태를 가지는 일상적인 장치의 예로는 텔레비전 수상기가 있다. TV 채널을 변경하려면 사용자는 일반적으로 리모컨의 채널 올림 또는 채널 내림 버튼을 눌러 TV에 코딩된 메시지를 보낸다. 사용자가 원하는 새 채널을 계산하기 위해 텔레비전의 디지털 튜너에는 현재 채널 번호가 저장되어 있어야 한다. 그런 다음 이 번호에 1을 더하거나 1을 빼서 새 채널 번호를 얻고, TV를 해당 채널을 수신하도록 조정한다. 이 새 번호는 현재 채널로 저장된다. 마찬가지로 텔레비전은 스피커에서 생성되는 음량 수준을 제어하는 번호도 저장한다. 볼륨 올림 또는 볼륨 내림 버튼을 누르면 이 번호가 증가하거나 감소하여 새로운 볼륨 수준을 설정한다. 현재 채널 번호와 현재 볼륨 번호는 모두 TV 상태의 일부이다. 이들은 TV가 꺼졌을 때 정보를 보존하는 비휘발성 메모리에 저장되므로, 다시 켜졌을 때 TV는 이전 방송국과 볼륨 수준으로 돌아갈 것이다.
다른 예로, 마이크로프로세서의 상태는 누산기, 저장 레지스터, 데이터 캐시 및 플래그와 같이 그 안에 있는 모든 메모리 요소의 내용이다. 노트북과 같은 컴퓨터가 프로세서를 종료하여 에너지를 절약하기 위해 최대 절전 모드로 전환될 때, 프로세서의 상태는 컴퓨터의 하드 디스크에 저장되므로 컴퓨터가 최대 절전 모드에서 깨어났을 때 복원될 수 있으며 프로세서는 중단된 지점부터 작업을 다시 시작할 수 있다.
배정밀도 부동소수점수, 배정밀도 부동소수점 형식(Double-precision floating-point format, FP64 또는 float64)은 일반적으로 컴퓨터 메모리에서 64 비트를 차지하는 부동소수점 숫자 형식이다. 이는 부동 기수점을 사용하여 광범위한 숫자 값을 나타낸다.
배정밀도는 단정밀도의 범위나 정밀도가 불충분할 때 선택할 수 있다.
IEEE 754 표준에서 64비트 2진 형식은 공식적으로 binary64로 불리며, IEEE 754-1985에서는 double이라고 불렸다. IEEE 754는 32비트 2진 단정밀도와 최근에는 10진수 표현(10진수 부동소수점)을 포함한 추가적인 부동소수점 형식을 명시한다.
부동소수점 자료형을 제공한 최초의 프로그래밍 언어 중 하나는 포트란이었다. IEEE 754-1985가 널리 채택되기 전에는 부동소수점 자료형의 표현과 속성이 컴퓨터 제조업체와 컴퓨터 모델, 그리고 프로그래밍 언어 구현자의 결정에 따라 달라졌다. 예를 들어, GW 베이직의 배정밀도 자료형은 64비트 MBF 부동소수점 형식이었다.
IEEE 754 배정밀도 이진 부동소수점 형식: binary64.
배정밀도 이진 부동소수점은 성능 및 대역폭 비용에도 불구하고 단정밀도 부동소수점보다 넓은 범위를 제공하므로 PC에서 일반적으로 사용되는 형식이다. 이는 흔히 단순히 double이라고 알려져 있다. IEEE 754 표준은 binary64를 다음과 같이 지정한다.
부호 비트는 숫자의 부호를 결정한다 (이 숫자가 0일 때도 부호 있는 0을 포함한다).
지수 필드는 0부터 2047까지의 11비트 부호 없는 정수로, 바이어스 형식이다. 즉, 지수 값 1023이 실제 0을 나타낸다. 지수 범위는 −1022에서 +1023까지인데, 이는 −1023 (모든 비트가 0) 및 +1024 (모든 비트가 1)의 지수가 특수 숫자를 위해 예약되어 있기 때문이다.
53비트 유효숫자 정밀도는 15에서 17 유효 십진 자릿수 정밀도를 제공한다 (2−53 ≈ 1.11 × 10−16). 최대 15자리 유효 숫자를 가진 십진 문자열이 IEEE 754 배정밀도 형식으로 변환되어 정규 숫자가 되고, 다시 같은 자릿수의 십진 문자열로 변환되면 최종 결과는 원래 문자열과 일치해야 한다. IEEE 754 배정밀도 숫자가 최소 17자리 유효 숫자를 가진 십진 문자열로 변환되고, 다시 배정밀도 표현으로 변환되면 최종 결과는 원래 숫자와 일치해야 한다.
이 형식은 유효숫자가 값 1의 암묵적인 정수 비트를 가지도록 작성된다 (특수 데이터 제외, 아래 지수 인코딩 참조). 메모리 형식에 나타나는 52비트의 분수 (F) 유효숫자를 통해 총 정밀도는 53비트이다 (약 16 십진수 자릿수, 53 log10(2) ≈ 15.955). 비트는 다음과 같이 배치된다.
주어진 64비트 배정밀도 데이터가 주어진 바이어스 지수 formula_1와 52비트 분수를 가질 때의 실제 값은 다음과 같다.
252=4,503,599,627,370,496와 253=9,007,199,254,740,992 사이의 표현 가능한 숫자는 정확히 정수이다. 다음 범위인 253부터 254까지는 모든 것이 2를 곱하므로 표현 가능한 숫자는 짝수 등이 된다. 반대로 이전 범위인 251부터 252까지는 간격이 0.5 등이다.
2n부터 2n+1까지의 범위에서 숫자의 간격은 2n−52이다.
따라서 숫자를 가장 가까운 표현 가능한 숫자로 반올림할 때의 최대 상대 반올림 오차 (계산기 엡실론)는 2−53이다.
지수의 11비트 폭은 10−308에서 10308 사이의 숫자를 15–17자리 전체 십진수 정밀도로 표현할 수 있게 한다. 정밀도를 타협하면 비정규 표현은 약 5 × 10−324까지 더 작은 값을 허용한다.
배정밀도 이진 부동소수점 지수는 오프셋 이진 표현을 사용하여 인코딩되며, 0 오프셋은 1023이다. 이는 IEEE 754 표준에서 지수 바이어스로도 알려져 있다. 이러한 표현의 예는 다음과 같다.
지수 codice_1와 codice_2는 특별한 의미를 가진다.
여기서 F는 유효숫자의 소수 부분이다. 모든 비트 패턴은 유효한 인코딩이다.
위 예외를 제외하고 전체 배정밀도 숫자는 다음으로 설명된다.
비정규 숫자의 경우 (e = 0) 배정밀도 숫자는 다음으로 설명된다.
배정밀도 예시.
0 01111111111 00000000000000000000000000000000000000000000000000002
≙ 3FF0 0000 0000 000016
≙ +20 × 1
0 01111111111 00000000000000000000000000000000000000000000000000012
≙ 3FF0 0000 0000 000116
≙ +20 × (1 + 2−52)
≈ 1.0000000000000002220 (1보다 큰 가장 작은 숫자)
0 01111111111 00000000000000000000000000000000000000000000000000102
≙ 3FF0 0000 0000 000216
≙ +20 × (1 + 2−51)
≈ 1.0000000000000004441 (1보다 큰 두 번째로 작은 숫자)
0 10000000000 00000000000000000000000000000000000000000000000000002
≙ 4000 0000 0000 000016
≙ +21 × 1
= 2
1 10000000000 00000000000000000000000000000000000000000000000000002
≙ C000 0000 0000 000016
≙ −21 × 1
= −2
0 10000000000 10000000000000000000000000000000000000000000000000002
≙ 4008 0000 0000 000016
≙ +21 × 1.12
= 112
0 10000000001 00000000000000000000000000000000000000000000000000002
≙ 4010 0000 0000 000016
≙ +22 × 1
= 1002
= 4
0 10000000001 01000000000000000000000000000000000000000000000000002
≙ 4014 0000 0000 000016
≙ +22 × 1.012
= 1012
0 10000000001 10000000000000000000000000000000000000000000000000002
≙ 4018 0000 0000 000016
≙ +22 × 1.12
= 1102
= 6
0 10000000011 01110000000000000000000000000000000000000000000000002
≙ 4037 0000 0000 000016
≙ +24 × 1.01112
= 101112
= 23
0 01111111000 10000000000000000000000000000000000000000000000000002
≙ 3F88 0000 0000 000016
≙ +2−7 × 1.12
= 0.000000112
= 0.01171875 (3/256)
0 00000000000 00000000000000000000000000000000000000000000000000012
≙ 0000 0000 0000 000116
≙ +2−1022 × 2−52
= 2−1074
≈ 4.9406564584124654 × 10−324 (가장 작은 양수 비정규 숫자)
0 00000000000 11111111111111111111111111111111111111111111111111112
≙ 000F FFFF FFFF FFFF16
≙ +2−1022 × (1 − 2−52)
≈ 2.2250738585072009 × 10−308 (가장 큰 비정규 숫자)
0 00000000001 00000000000000000000000000000000000000000000000000002
≙ 0010 0000 0000 000016
≙ +2−1022 × 1
≈ 2.2250738585072014 × 10−308 (가장 작은 양수 정규 숫자)
0 11111111110 11111111111111111111111111111111111111111111111111112
≙ 7FEF FFFF FFFF FFFF16
≙ +21023 × (2 − 2−52)
≈ 1.7976931348623157 × 10308 (가장 큰 정규 숫자)
0 00000000000 00000000000000000000000000000000000000000000000000002
≙ 0000 0000 0000 000016
≙ +0 (양수 0)
1 00000000000 00000000000000000000000000000000000000000000000000002
≙ 8000 0000 0000 000016
≙ −0 (음수 0)
0 11111111111 00000000000000000000000000000000000000000000000000002
≙ 7FF0 0000 0000 000016
≙ +∞ (양수 무한)
1 11111111111 00000000000000000000000000000000000000000000000000002
≙ FFF0 0000 0000 000016
≙ −∞ (음수 무한)
0 11111111111 00000000000000000000000000000000000000000000000000012
≙ 7FF0 0000 0000 000116
≙ NaN (대부분의 프로세서, 예: x86 및 ARM에서 sNaN)
0 11111111111 10000000000000000000000000000000000000000000000000012
≙ 7FF8 0000 0000 000116
≙ NaN (대부분의 프로세서, 예: x86 및 ARM에서 qNaN)
0 11111111111 11111111111111111111111111111111111111111111111111112
≙ 7FFF FFFF FFFF FFFF16
≙ NaN (NaN의 대체 인코딩)
0 01111111101 01010101010101010101010101010101010101010101010101012
≙ 3FD5 5555 5555 555516
≙ +2−2 × (1 + 2−2 + 2−4 + ... + 2−52)
≈ 0.33333333333333331483 (1/3에 가장 가까운 근사치)
0 10000000000 10010010000111111011010101000100010000101101000110002
≙ 4009 21FB 5444 2D1816
≈ 3.141592653589793116 (π에 가장 가까운 근사치)
qNaN 및 sNaN의 인코딩은 IEEE 754에 완전히 명시되어 있지 않으며 프로세서에 따라 달라진다. X86 계열 및 ARM 계열 프로세서와 같은 대부분의 프로세서는 유효숫자 필드의 최상위 비트를 사용하여 quiet NaN을 나타낸다. 이는 IEEE 754에서 권장하는 방식이다. PA-RISC 프로세서는 이 비트를 사용하여 signaling NaN을 나타낸다.
기본적으로 1/3은 유효숫자의 홀수 비트 때문에 단정밀도처럼 올림이 아닌 내림으로 반올림된다.
더 자세히:
16진수 표현 3FD5 5555 5555 555516가 주어지면,
부호 = 0
지수 = 3FD16 = 1021
지수 바이어스 = 1023 (상수 값; 위 참조)
분수 = 5 5555 5555 555516
값 = 2(지수 − 지수 바이어스) × 1.분수 – 여기서 분수는 십진수로 변환해서는 안 된다
배정밀도 연산의 실행 속도.
배정밀도 부동소수점 변수를 사용하는 것은 일반적으로 단정밀도 변수를 사용하는 것보다 느리다. 이 문제가 특히 중요한 컴퓨팅 영역 중 하나는 GPU에서 실행되는 병렬 코드이다. 예를 들어, 엔비디아의 CUDA 플랫폼을 사용할 때 배정밀도 계산은 하드웨어에 따라 단정밀도를 사용한 계산에 비해 완료하는 데 2배에서 32배까지 더 오래 걸릴 수 있다.
또한, 많은 수학 함수 (예: sin, cos, atan2, log, exp 및 sqrt)는 정확한 배정밀도 결과를 제공하기 위해 더 많은 계산이 필요하므로 느리다.
Double은 다음과 같이 다양한 방식으로 많은 프로그래밍 언어에서 구현된다. SSE2 없이 (또는 호환성을 위해 SSE2를 사용하지 않을 때) X86과 같이 동적 정밀도만 있는 프로세서에서 확장 정밀도가 기본적으로 사용될 때, 소프트웨어는 일부 요구 사항을 충족하는 데 어려움을 겪을 수 있다.
C 및 C++는 다양한 산술 자료형을 제공한다. 배정밀도는 표준에서 요구되지 않지만 (IEEE 754 산술을 다루는 C99의 선택적 부록 F 제외), 대부분의 시스템에서 codice_7 형식은 배정밀도에 해당한다. 그러나 기본적으로 확장 정밀도를 사용하는 32비트 x86에서는 일부 컴파일러가 C 표준을 따르지 않거나 산술이 이중 반올림으로 인해 문제가 발생할 수 있다.
포트란은 여러 정수 및 실수 형식을 제공하며, 포트란의 내장 모듈 codice_8를 통해 접근 가능한 64비트 형식 codice_9는 배정밀도에 해당한다.
커먼 리스프는 SHORT-FLOAT, SINGLE-FLOAT, DOUBLE-FLOAT 및 LONG-FLOAT 유형을 제공한다. 대부분의 구현은 SINGLE-FLOAT 및 DOUBLE-FLOAT를 제공하며 다른 유형은 적절한 동의어로 사용된다. 커먼 리스프는 IEEE 754에 따라 부동소수점 언더플로우 및 오버플로우와 부정확한 부동소수점 예외를 포착하기 위한 예외를 제공한다. ANSI 표준에는 무한대와 NaN이 명시되어 있지 않지만, 여러 구현에서 이를 확장으로 제공한다.
버전 1.2 이전의 자바에서는 모든 구현이 IEEE 754를 준수해야 했다. 버전 1.2에서는 x87과 같은 플랫폼을 위해 중간 계산에서 추가 정밀도를 허용했다. 따라서 엄격한 IEEE 754 계산을 강제하기 위해 strictfp 수정자가 도입되었다. 엄격한 부동소수점은 Java 17에서 복원되었다.
ECMA스크립트 표준에 명시된 바와 같이, 자바스크립트의 모든 산술은 배정밀도 부동소수점 산술을 사용하여 수행되어야 한다.
JSON 데이터 인코딩 형식은 숫자 값을 지원하며, 숫자 표현이 준수해야 하는 문법에는 인코딩된 숫자의 정밀도나 범위에 제한이 없다. 그러나 RFC 8259는 IEEE 754 binary64 숫자가 널리 구현되어 있으므로, JSON을 처리하는 구현이 binary64가 제공하는 것 이상의 정밀도나 범위를 기대하지 않는다면 좋은 상호 운용성을 달성할 수 있다고 조언한다.
러스트 및 Zig.
러스트와 Zig는 codice_10 자료형을 가지고 있다.
단정밀도 부동소수점수, 단정밀도 부동소수점 형식(Single-precision floating-point format, FP32 또는 float32)은 일반적으로 주기억장치에서 32비트를 차지하는 컴퓨터 숫자 형식이다. 이는 부동소수점을 사용하여 넓은 동적 범위의 숫자 값을 나타낸다.
부동소수점 변수는 정밀도를 희생하는 대신 동일한 비트 너비의 고정소수점 변수보다 더 넓은 범위의 숫자를 표현할 수 있다. 부호 있는 32비트 정수형 변수의 최댓값은 231 − 1 = 2,147,483,647인 반면, IEEE 754 32비트 2진 부동소수점 변수의 최댓값은 (2 − 2−23) × 2127 ≈ 3.4028235 × 1038이다. 7자리 이하의 모든 십진 정수와 −149 ≤ n ≤ 127인 모든 정수 n에 대한 2n은 IEEE 754 단정밀도 부동소수점 값으로 정확하게 변환될 수 있다.
IEEE 754 표준에서 32비트 2진 형식은 공식적으로 binary32라고 불리며, IEEE 754-1985에서는 single이라고 불렸다. IEEE 754는 64비트 2진 배정밀도와 최근의 10진 표현과 같은 추가적인 부동소수점 유형을 지정한다.
단정밀도 및 배정밀도 부동소수점 자료형을 제공한 최초의 프로그래밍 언어 중 하나는 포트란이었다. IEEE 754-1985가 널리 채택되기 전에는 부동소수점 자료형의 표현과 속성이 컴퓨터 제조업체와 컴퓨터 모델, 그리고 프로그래밍 언어 설계자가 내린 결정에 따라 달라졌다. 예를 들어, GW 베이직의 단정밀도 자료형은 32비트 MBF 부동소수점 형식이었다.
단정밀도는 포트란에서는 REAL, 커먼 리스프에서는 SINGLE-FLOAT, C, C++, C# 및 자바에서는 float, 하스켈 및 스위프트에서는 Float, 그리고 오브젝트 파스칼 (델파이), 비주얼 베이직 및 매트랩에서는 Single이라고 부른다. 그러나 파이썬, 루비, PHP, OCaml의 float 및 옥타브 3.2 이전 버전의 single은 배정밀도 숫자를 나타낸다. 대부분의 포스트스크립트 구현과 일부 임베디드 시스템에서는 단정밀도만 지원된다.
IEEE 754 표준: binary32.
IEEE 754 표준은 binary32가 다음을 갖도록 지정한다.
이는 6에서 9 유효 십진수 정밀도를 제공한다. 최대 6개의 유효 숫자를 가진 십진수 문자열이 IEEE 754 단정밀도 형식으로 변환되어 정규화된 수를 생성한 다음, 동일한 자릿수의 십진수 문자열로 다시 변환되면 최종 결과는 원래 문자열과 일치해야 한다. IEEE 754 단정밀도 숫자가 최소 9개의 유효 숫자를 가진 십진수 문자열로 변환된 다음, 단정밀도 표현으로 다시 변환되면 최종 결과는 원래 숫자와 일치해야 한다.
부호 비트는 숫자의 부호를 결정하며, 이는 가수의 부호이기도 하다. "1"은 음수를 나타낸다. 지수 필드는 0부터 255까지의 8비트 부호 없는 정수이며, 편향 형식이다. 즉, 127의 값은 실제 지수 0을 나타낸다. 지수 필드의 값 0(모두 0)과 255(모두 1)는 특수 숫자(비정규 값수, 부호 있는 0, 무한, NaN 등)를 위해 예약되어 있으므로, 지수 범위는 -126에서 +127까지이다(지수 필드에서는 1에서 254까지).
정규화된 숫자의 실제 가수는 이진점 오른쪽에 23개의 분수 비트와 값 1을 가진 숨겨진 선행 비트 (이진점의 왼쪽에)를 포함한다. 비정규화된 숫자와 0 (가장 작은 양의 정규화된 숫자보다 절댓값이 작은 부동소수점 숫자)은 편향된 지수 값 0으로 표현되며, 숨겨진 선행 비트의 값은 0이 된다. 따라서 가수의 23개의 분수 비트만 메모리 형식에 나타나지만, 총 정밀도는 정규화된 값의 경우 24비트(log10(224) ≈ 7.225 십진수 자릿수와 동일)이며, 비정규화된 값은 가장 작은 비영(non-zero) 값의 경우 1비트까지 점진적으로 정밀도가 저하된다.
비트 배치는 다음과 같다:
주어진 부호, 편향된 지수 E (8비트 부호 없는 정수), 23비트 분수를 가진 32비트 binary32 데이터가 나타내는 실제 값은 다음과 같다.
이는 다음을 산출한다:
이 예시에서:
단정밀도 이진 부동소수점 지수는 오프셋 이진 표현을 사용하여 인코딩되며, 0 오프셋은 127이다. 이는 IEEE 754 표준에서 지수 바이어스라고도 알려져 있다.
따라서 오프셋 이진 표현에 따라 정의된 실제 지수를 얻으려면 저장된 지수에서 127의 오프셋을 빼야 한다.
저장된 지수 00H와 FFH는 특별하게 해석된다.
최소 양의 정규 값은 formula_13이고, 최소 양의 (비정규) 값은 formula_14이다.
십진수를 binary32로 변환.
일반적으로 실수에서 동등한 binary32 형식으로의 엄격한 변환 (반올림 동작 포함)에 대해서는 IEEE 754 표준 자체를 참조할 것.
여기에서는 다음 개요를 사용하여 10진수 실수를 IEEE 754 binary32 형식으로 변환하는 방법을 보여줄 수 있다.
분수 부분의 변환:
12.375의 분수 부분인 0.375를 고려한다. 이를 이진 분수로 변환하려면, 분수에 2를 곱하고, 정수 부분을 취한 다음, 분수가 0이 되거나 IEEE 754 binary32 형식의 정밀도 한계인 23개 분수 자릿수에 도달할 때까지 새 분수에 2를 곱하는 과정을 반복한다.
formula_18는 이진수로 formula_19로 정확하게 표현될 수 있음을 알 수 있다. 모든 십진수 분수가 유한 자릿수 이진 분수로 표현될 수 있는 것은 아니다. 예를 들어, 십진수 0.1은 이진수로 정확하게 표현될 수 없으며, 근사치로만 표현될 수 있다. 따라서:
IEEE 754 binary32 형식은 실제 값을 formula_21 형식으로 표현해야 하므로 (정규화된 수, 비정규 값 참조), 1100.011은 formula_22이 되도록 3자리 오른쪽으로 이동한다.
결론적으로 다음을 알 수 있다: formula_23
이를 통해 다음을 추론할 수 있다:
이것들로부터 12.375의 결과적인 32비트 IEEE 754 binary32 형식 표현을 구성할 수 있다:
참고: 68.123을 IEEE 754 binary32 형식으로 변환하는 것을 고려한다: 위의 절차를 사용하면 마지막 4비트가 1001인 formula_26을 얻을 것으로 예상된다. 그러나 IEEE 754 형식의 기본 반올림 동작으로 인해 얻는 값은 마지막 4비트가 1010인 formula_27이다.
예시 1:
십진수 1을 고려한다. 다음을 알 수 있다: formula_28
이것들로부터 실수 1의 결과적인 32비트 IEEE 754 binary32 형식 표현을 구성할 수 있다:
예시 2:
값 0.25를 고려한다. 다음을 알 수 있다: formula_32
이것들로부터 실수 0.25의 결과적인 32비트 IEEE 754 binary32 형식 표현을 구성할 수 있다:
예시 3:
0.375의 값을 고려한다. formula_35임을 보았다.
따라서 0.375를 formula_36로 표현한 후, 위와 같이 진행할 수 있다:
이것들로부터 실수 0.375의 결과적인 32비트 IEEE 754 binary32 형식 표현을 구성할 수 있다:
binary32를 십진수로 변환.
이 예시에서, binary32 값인 이 16진수일 경우, 먼저 2진수로 변환한다:
그 다음, 이를 세 부분으로 나눈다: 부호 비트, 지수, 가수.
그런 다음 가수에 숨겨진 24번째 비트를 추가한다:
그리고 127을 빼서 지수 값을 디코딩한다:
가수의 24비트(숨겨진 24번째 비트 포함), 비트 23부터 비트 0까지는 각각 1부터 시작하여 각 비트마다 절반이 되는 값을 나타내며, 다음과 같다:
비트 23 = 1
비트 22 = 0.5
비트 21 = 0.25
비트 20 = 0.125
비트 19 = 0.0625
비트 18 = 0.03125
비트 17 = 0.015625
비트 6 = 0.00000762939453125
비트 5 = 0.000003814697265625
비트 4 = 0.0000019073486328125
비트 3 = 0.00000095367431640625
비트 2 = 0.000000476837158203125
비트 1 = 0.0000002384185791015625
비트 0 = 0.00000011920928955078125
이 예시의 가수는 세 비트가 설정되어 있다: 비트 23, 비트 22, 비트 19. 이제 이 비트들이 나타내는 값을 더하여 가수를 디코딩할 수 있다.
그런 다음, 최종 결과를 얻기 위해 지수의 거듭제곱인 2를 밑으로 곱해야 한다:
여기서 는 부호 비트, 는 지수, 그리고 은 가수이다.
주목할 만한 단정밀도 사례.
이 예시들은 부동소수점 값의 16진수와 2진수 비트 표현으로 주어진다. 여기에는 부호, (편향된) 지수 및 가수가 포함된다.
0 00000000 000000000000000000000012 = 0000 000116 = 2−126 × 2−23 = 2−149 ≈ 1.4012984643 × 10−45
(가장 작은 양의 비정규화된 숫자)
0 00000000 111111111111111111111112 = 007f ffff16 = 2−126 × (1 − 2−23) ≈ 1.1754942107 ×10−38
(가장 큰 비정규화된 숫자)
0 00000001 000000000000000000000002 = 0080 000016 = 2−126 ≈ 1.1754943508 × 10−38
(가장 작은 양의 정규화된 숫자)
0 11111110 111111111111111111111112 = 7f7f ffff16 = 2127 × (2 − 2−23) ≈ 3.4028234664 × 1038
(가장 큰 정규화된 숫자)
0 01111110 111111111111111111111112 = 3f7f ffff16 = 1 − 2−24 ≈ 0.999999940395355225
(1보다 작은 가장 큰 숫자)
0 01111111 000000000000000000000002 = 3f80 000016 = 1 (하나)
0 01111111 000000000000000000000012 = 3f80 000116 = 1 + 2−23 ≈ 1.00000011920928955
(1보다 큰 가장 작은 숫자)
1 10000000 000000000000000000000002 = c000 000016 = −2
0 00000000 000000000000000000000002 = 0000 000016 = 0
1 00000000 000000000000000000000002 = 8000 000016 = −0
0 11111111 000000000000000000000002 = 7f80 000016 = 무한대
1 11111111 000000000000000000000002 = ff80 000016 = −무한대
0 10000000 100100100001111110110112 = 4049 0fdb16 ≈ 3.14159274101257324 ≈ π (파이)
0 01111101 010101010101010101010112 = 3eaa aaab16 ≈ 0.333333343267440796 ≈ 1/3
x 11111111 100000000000000000000012 = ffc0 000116 = qNaN (x86 및 ARM 프로세서에서)
x 11111111 000000000000000000000012 = ff80 000116 = sNaN (x86 및 ARM 프로세서에서)
기본적으로 1/3은 가수의 비트 수가 짝수이기 때문에 배정밀도처럼 내림 대신 올림한다. 반올림 지점 너머의 1/3 비트는 `1010...`으로 ULP의 1/2보다 크다.
qNaN 및 sNaN의 인코딩은 IEEE 754에 지정되어 있지 않으며, 프로세서마다 다르게 구현된다. X86 계열 및 ARM 계열 프로세서는 가수의 최상위 비트를 사용하여 콰이어트 NaN을 나타낸다. PA-RISC 프로세서는 이 비트를 사용하여 시그널링 NaN을 나타낸다.
부동소수점 형식의 설계는 원시 비트 패턴의 정수적인 관점에서 이진 로그 근사치를 쉽게 생성할 수 있게 하여 다양한 최적화를 가능하게 한다. 정수 산술 및 비트 시프팅은 컴퓨터 그래픽스에서 흔히 요구되는 고속 역 제곱근의 근사치를 제공할 수 있다.
XOR 연결 리스트 또는 XOR 링크드 리스트(XOR linked list)는 컴퓨터 프로그래밍에서 사용되는 자료 구조의 한 종류이다. 이는 이중 연결 리스트의 저장 공간 요구 사항을 줄이기 위해 비트 XOR 연산을 활용하여 두 주소의 구성을 하나의 필드에 저장한다. 구성된 주소는 그 자체로는 의미가 없지만, 순회 시 이전에 방문한 노드 주소에 대한 지식과 결합하여 다음 노드의 주소를 추론할 수 있다.
일반적인 이중 연결 리스트는 각 리스트 노드에 이전 및 다음 리스트 항목의 주소를 저장하므로 두 개의 주소 필드가 필요하다.
... A B C D E ...
–&gt; next –&gt; next –&gt; next –&gt;
&lt;– prev &lt;– prev &lt;– prev &lt;–
XOR 연결 리스트는 이전 주소와 다음 주소의 비트 XOR(여기서는 ⊕로 표시)을 하나의 필드에 저장하여 동일한 정보를 하나의 주소 필드로 압축한다.
⇌ A⊕C ⇌ B⊕D ⇌ C⊕E ⇌
더 공식적으로는:
link(B) = addr(A)⊕addr(C), link(C) = addr(B)⊕addr(D), ...
리스트를 왼쪽에서 오른쪽으로 순회할 때: 커서가 C에 있고 이전 항목이 B라고 가정하면, B는 링크 필드(B⊕D)의 값과 XOR될 수 있다. 그러면 D의 주소를 얻게 되고 리스트 순회를 재개할 수 있다. 동일한 패턴이 다른 방향에도 적용된다.
link(C) = addr(B)⊕addr(D)
addr(D) = addr(B)⊕addr(D) ⊕ addr(B)
addr(D) = addr(B)⊕addr(B) ⊕ addr(D)
왜냐하면
X⊕X = 0
=&gt; addr(D) = 0 ⊕ addr(D)
X⊕0 = X
=&gt; addr(D) = addr(D)
XOR 연산은 식에 두 번 나타나는 를 상쇄하고 남는 것은 뿐이다.
어떤 지점부터 리스트를 양방향으로 순회하려면 연속된 두 항목의 주소가 필요하다. 연속된 두 항목의 주소가 역전되면 리스트 순회는 반대 방향으로 발생한다.
핵심은 첫 번째 연산과 XOR의 속성이다.
R2 레지스터는 항상 현재 항목 C의 주소와 선행 항목 P의 주소의 XOR 값인 C⊕P를 포함한다. 레코드의 링크 필드에는 왼쪽 및 오른쪽 후속 주소의 XOR 값, 예를 들어 L⊕R이 포함된다. R2(C⊕P)와 현재 링크 필드(L⊕R)의 XOR 연산은 C⊕P⊕L⊕R을 생성한다.
각 경우에 결과는 현재 주소와 다음 주소의 XOR 값이다. 이 값을 R1의 현재 주소와 XOR하면 다음 주소가 남는다. R2에는 (이제) 현재 주소와 선행 주소의 필수 XOR 쌍이 남는다.
X R2,Link R2 &lt;- C⊕D ⊕ B⊕D (즉, B⊕C, "Link"는 현재 레코드의
링크 필드이며 B⊕D를 포함한다)
XR R1,R2 R1 &lt;- C ⊕ B⊕C (즉, B, 바로 다음 레코드)
컴퓨터 시스템은 점점 더 저렴하고 풍부한 메모리를 가지므로, 임베디드 시스템과 같은 특수 분야를 제외하고는 저장 공간 오버헤드가 일반적으로 최우선 문제는 아니다. 연결 리스트의 오버헤드를 줄이는 것이 여전히 바람직한 경우, 풀림은 더 실용적인 접근 방식을 제공한다(캐시 성능 향상 및 임의 접근 속도 향상과 같은 다른 이점도 있음).
XOR 연결 리스트의 기본 원리는 모든 가역 이진 연산에 적용할 수 있다. XOR를 덧셈이나 뺄셈으로 바꾸면 약간 다르지만 대체로 동일한 형태가 된다.
덧셈 연결 리스트.
⇌ A+C ⇌ B+D ⇌ C+E ⇌
이러한 종류의 리스트는 XOR 연결 리스트와 정확히 동일한 속성을 가지며, 0 링크 필드가 "거울"이 아니라는 점만 다르다. 리스트의 다음 노드 주소는 이전 노드의 주소를 현재 노드의 링크 필드에서 빼서 얻는다.
뺄셈 연결 리스트.
⇌ C-A ⇌ D-B ⇌ E-C ⇌
이러한 종류의 리스트는 표준 "전통적인" XOR 연결 리스트와 달리 리스트를 앞으로 순회하는 데 필요한 명령 시퀀스가 리스트를 역방향으로 순회하는 데 필요한 시퀀스와 다르다. 앞으로 나아갈 때 다음 노드의 주소는 링크 필드를 이전 노드의 주소에 더하여 얻는다. 이전 노드의 주소는 링크 필드를 다음 노드의 주소에서 빼서 얻는다.
뺄셈 연결 리스트는 리스트의 각 주소에 일정한 오프셋을 더해도 링크 필드에 저장된 값을 변경할 필요가 없으므로, 포인터 값의 패치 없이 전체 리스트를 메모리에서 재배치할 수 있다는 점에서도 특별하다. (직렬화 참조.) 이는 XOR 연결 리스트와 전통적인 연결 리스트 모두에 비해 장점이다.
이진 탐색 트리.
XOR 연결 리스트 개념은 XOR 이진 탐색 트리로 일반화될 수 있다.
컴퓨터 과학에서 이중 연결 리스트, 이중 링크드 리스트 또는 더블리 링크드 리스트(Doubly linked list)는 순차적으로 연결된 레코드들의 집합으로 구성된 연결 자료 구조이며, 이 레코드는 노드라고 불린다. 각 노드는 세 가지 필드를 포함한다: 두 개의 링크 필드 (참조하는 이전 노드와 다음 노드에 대한 참조)와 하나의 데이터 필드. 시작 노드와 끝 노드의 이전 및 다음 링크는 각각 어떤 종류의 종결자(일반적으로 센티널 노드 또는 널)를 가리켜 리스트 탐색을 용이하게 한다. 센티널 노드가 하나뿐인 경우 리스트는 센티널 노드를 통해 원형으로 연결된다. 이는 동일한 데이터 항목으로 구성되었지만 순서가 반대인 두 개의 단일 연결 리스트로 개념화될 수 있다.
두 노드 링크를 통해 리스트를 양방향으로 탐색할 수 있다. 이중 연결 리스트에서 노드를 추가하거나 제거하는 것은 단일 연결 리스트에서 동일한 작업을 수행하는 것보다 더 많은 링크를 변경해야 하지만, 작업은 더 간단하고 (첫 번째 노드를 제외한 노드의 경우) 잠재적으로 더 효율적이다. 탐색 중에 이전 노드를 추적할 필요가 없거나 이전 노드를 찾기 위해 리스트를 탐색할 필요가 없어 링크를 수정할 수 있기 때문이다.
명명법 및 구현.
실질적인 모든 응용 프로그램에서 이중 연결 리스트의 첫 번째 및 마지막 노드는 즉시 접근 가능하며 (즉, 탐색 없이 접근 가능하며 일반적으로 헤드 및 테일이라고 불림) 따라서 리스트의 시작 또는 끝에서 각각 리스트를 탐색할 수 있다. 예를 들어, 특정 데이터 값을 가진 노드를 찾기 위해 리스트를 처음부터 끝까지 또는 끝에서 처음까지 탐색할 수 있다. 일단 얻은 이중 연결 리스트의 어떤 노드도 주어진 노드에서 양방향(시작 또는 끝 방향)으로 리스트의 새로운 탐색을 시작하는 데 사용될 수 있다.
이중 연결 리스트 노드의 링크 필드는 종종 다음 및 이전 또는 앞 및 뒤라고 불린다. 링크 필드에 저장된 참조는 일반적으로 포인터로 구현되지만 (모든 연결된 데이터 구조에서와 같이) 노드가 존재하는 배열의 주소 오프셋 또는 인덱스일 수도 있다.
아래 Ada로 작성된 기본 알고리즘을 살펴보자:
개방형 이중 연결 리스트.
record DoublyLinkedNode {
next // 다음 노드에 대한 참조
prev // 이전 노드에 대한 참조
data // 데이터 또는 데이터에 대한 참조
record DoublyLinkedList {
DoublyLinkedNode firstNode // 리스트의 첫 번째 노드를 가리킴
DoublyLinkedNode lastNode // 리스트의 마지막 노드를 가리킴
리스트 탐색.
이중 연결 리스트의 탐색은 양방향으로 가능하다. 사실, 원하는 경우 탐색 방향을 여러 번 변경할 수 있다. 탐색은 종종 반복이라고 불리지만, 그 용어 선택은 불행하다. 왜냐하면 반복은 (예를 들어 수학에서) 탐색과 유사하지 않은 잘 정의된 의미론을 가지고 있기 때문이다.
앞으로
node := list.firstNode
&lt;node.data로 뭔가 함&gt;
node := node.next
뒤로
node := list.lastNode
node := node.prev
노드 삽입.
다음 대칭 함수는 주어진 노드 뒤 또는 앞에 노드를 삽입한다:
function insertAfter(List list, Node node, Node newNode)
newNode.prev := node
if node.next == null
newNode.next := null -- (항상 필요한 것은 아님)
list.lastNode := newNode
newNode.next := node.next
node.next.prev := newNode
node.next := newNode
function insertBefore(List list, Node node, Node newNode)
newNode.next := node
if node.prev == null
newNode.prev := null -- (항상 필요한 것은 아님)
list.firstNode := newNode
newNode.prev := node.prev
node.prev.next := newNode
node.prev := newNode
또한 비어 있을 수 있는 리스트의 시작 부분에 노드를 삽입하는 함수가 필요하다:
function insertBeginning(List list, Node newNode)
if list.firstNode == null
newNode.prev := null
newNode.next := null
insertBefore(list, list.firstNode, newNode)
대칭 함수는 끝에 삽입한다:
function insertEnd(List list, Node newNode)
if list.lastNode == null
insertBeginning(list, newNode)
insertAfter(list, list.lastNode, newNode)
노드 제거.
노드 제거는 삽입보다 쉽지만, 제거할 노드가 firstNode 또는 lastNode인 경우 특별한 처리가 필요하다:
function remove(List list, Node node)
list.firstNode := node.next
node.prev.next := node.next
list.lastNode := node.prev
node.next.prev := node.prev
위 절차의 미묘한 결과 중 하나는 리스트의 마지막 노드를 삭제하면 firstNode와 lastNode가 모두 null로 설정되므로, 한 요소 리스트에서 마지막 노드를 제거하는 것을 올바르게 처리한다는 것이다. 또한 "removeBefore" 또는 "removeAfter" 메서드가 별도로 필요하지 않다는 점에 유의하라. 이중 연결 리스트에서는 "remove(node.prev)" 또는 "remove(node.next)"를 사용할 수 있기 때문이다. 이는 또한 제거되는 노드가 존재한다고 가정한다. 노드가 이 리스트에 존재하지 않으면 오류 처리가 필요할 것이다.
원형 이중 연결 리스트.
someNode가 비어 있지 않은 리스트의 노드라고 가정하면, 이 코드는 someNode(어떤 노드든 상관없음)에서 시작하여 해당 리스트를 탐색한다:
node := someNode
node.value로 뭔가 함
while node ≠ someNode
테스트가 루프 끝으로 연기된다는 점에 유의하라. 이는 리스트가 단일 노드 someNode만 포함하는 경우에 중요하다.
이 간단한 함수는 주어진 요소 뒤에 노드를 이중 연결 원형 연결 리스트에 삽입한다: