Chapter 2 Representing and Manipulating Information

2.1 Information Storage

우리는 숫자의 가장 중요한 세 개의 표현들을 고려한다. Unsigned encodings은 전통적인 binary notation을 기반으로 하는데, 0 이상의 숫자들을 나타낸다. Two’s-complement encodings은 signed integers를 나타내는 가장 흔한 방법이다. 즉, positive하거나 negative할지도 모르는 숫자들이다. Floating-point encodings은 real numbers(실수)를 나타내기 위한 과학적 표기의 base-two version이다. 컴퓨터들은 덧셈과 곱셈같은 수학 연산을 구현하는데, 이러한 다른 표기들로 한다. 이것은 integers와 real numbers에 대해 대응되는 연산들은 유사하다.

컴퓨터 표현은 숫자를 인코딩하기 위해 제한된 수의 비트들을 사용하고, 그러므로 어떤 연산들은 그 결과가 표현하기에 너무 클 때 overflow 될 수 있다.

반며에, 정수 컴퓨터 연산은 실제 정수 연산의 많은 친숙한 부분들을 만족시킨다. 예를들어, 곱셈은 결합법칙과 교환법칙이 가능하다.

Floating-point 연산은 전적으로 다른 수학적 특성들을 가진다. 양의 숫자들의 한 집합의 곱은 항상 양수일 것이다. 비록 overflow가 특별한 값인 $+ \infty$ 를 만들어낼지라도. Floating-point 연산은 결합법칙이 안되는데, 이것은 표기의 유한한 정밀도에 의한 것이다. 예를들어, C expression의 (3.14 + 1e20) - 1e20은 대부분의 기계들에서 0.0으로 구해질 것인데, 반면에 3.14 + (1e20 -1e20)은 3.14로 구해질 것이다. integer vs floating-point 연산의 다른 수학적 특성들은 그것들이 그들의 표기에 있어서 유한성을 어떻게 다루는지의 차이에서 비롯한다 - 정수 표기들은 비교적 작은 범위의 값들을 인코딩할 수 있지만, 그렇제 정확하게 한다. 반면에 floating-point 표기들은 더 넓은 범위의 값들을 인코딩하라 수 있지만, 오직 대략적이다.

실제 숫자 표기를 공부함으로써, 우리는 나타내어질 수 있는 값들의 범위를 이해할 수 있고, 다른 수학 연산들의 특성들을 이해할 수 있다. 이 이해는 numeric values의 전체 범위에 대해 정확하게 작동하는 프로그램들을 작성하는데 있어서 매우 중요하고, 다른 machine, operating system, 그리고 compiler의 조합에 걸쳐서 portable한 프로그램에 중요하다. 우리가 설명하게 되듯이, 많은 컴퓨터 보안의 취약성은 컴퓨터 연산의 미묘함에 의해 발생한다. …

컴퓨터들은 numeric values를 인코딩하기 위해 몇 가지 다른 binary representations을 사용한다. 너는 Chapter 3에서 machine-level programming에 대해 진행함에 따라 이러한 표현들에 친숙해질 필요가 있을 것이다. 우리는 이러한 인코딩들을 이 챕터에서 설명하고, 숫자 표기에 대해 어떻게 사고하는지를 보여준다.

우리는 숫자들의 bit-level 표기를 직접 조작하여, 수학 연산들을 수행하는 몇 가지 방법들을 도출한다. 이러한 기법들을 이해하는 것은 arithmetic expression evaluation의 성능을 최적화하려는 컴파일러의 시도에서 그것들에 의해 생성되는 machine-level code를 이해하는데 있어서 중요하다.

이 주제에 대한 우리의 논의는 수학적 원리들의 핵심 집합을 기반으로 한다. 우리는 인코딩들의 기본 정의로 시작하고, 그러고나서 표기가능한 숫자들의 범위, 그것들의 bit-level representations, 그리고 수학연산들의 특성같은 특성들을 도출해낸다. 우리는 이 추상적인 관점으로부터 그 주제를 너가 조사하는 것이 중요하다고 믿는다. 왜냐하면 프로그래머들은 컴퓨터 연산이 정수와 실수 연산에 좀 더 친숙하게 어떻게 연관되어 있는지에 대해 확고한 이해를 가질 필요가 있기 때문이다.

2.1 Information Storage

메모리에서 개별 bits들을 접근하기 보다, 대부분의 컴퓨터들은 8개의 비트의 blocks, 즉 bytes를 메모리의 가장 작은 접근가능한 단위로서 사용한다. machine-level program은 메모리를 bytes의 매우 큰 배열로서 보고, 그 배열은 virtual memory로 지칭된다. memory의 모든 byte는 unique number로 인식되는데, 그것의 address로서 알려져있고, 모든 가능한 주소들의 집합은 virtual address space로서 알려져 있다. 그것의 이름이 가리키듯이, virtual address space는 machine-level program에게 제공되는 conceptual image이다. 그 실제 구현 (Chapter 9에서 나타나는)은 프로그램에게 monolithic byte array것처럼 보이는 것을 제공하기 위해 random-access memory (RAM), disk storage, 특별한 하드웨어, 그리고 운영체제 소프트웨어의 조합을 사용한다.

이후의 챕터들에서, 우리는 컴파일러와 run-time system이 이 메모리 공간을 좀 더 관리가능한 단위들로 어떻게 나누는지를 다룰 것이다. 이것은 다른 program objects들, 즉 program data, instructions, and control information을 저장하기 위해서이다. 다양한 메커니즘이 프로그램의 다른 부분들을 위한 storage를 할당하고 관리하기 위해 사용된다. 이 관리는 모두 virtual address space내에서 수행된다. …

그 C 컴파일러는 또한 type information을 각 포인터와 연관시키는데, 이것은 다른 machine-level code를 생성할 수 있는데, 그 값의 type에 따라 pointer에 지정되는 그 위치에 저장된 값을 접근하기 위해서이다.

2.1.1 Hexadecimal Notation

…

C에서, 0x 또는 0X로 시작하는 numeric constants는 hexadecimal로서 해석된다. 'A’에서 'F’까지의 문자들은 대문자 또는 소문자로 쓰일지도 모른다.

machine-level programs과 작업하는데 있어서 흔한 작업은 직접 bit patterns의 decimal, binary, and hexadecimal 표기들 사이에서 변환하는 것이다.

…

그러나, 만약 bits의 총 개수가 4의 배수가 아니라면, 너는 4bits보다 더 적은 것이 leftmost group이 되도록 해야 하고, 효과적으로 그 숫자에 leading zeros를 패딩한다.

한 값 x가 2의 지수승 일 때, 즉 $x = 2^n$ 일 때, 어떤 음이 아닌 정수 n에 대해, 우리는 쉽게 hexadecimal form으로 그 x를 다시 쓸 수 있는데, x의 binary representation이 n개의 0이 1다음에 나오게 한다. 그래서 $i + 4j$ 의 형태로 쓰여진 n에 대해, $0 \leq i \leq 3$ 인 곳에서, 우리는 1 ( $i = 0$ ), 2 ( $i = 1$ ), 4 ( $i = 2$ ), or 8 ( $i = 3$ )의 한 개의 leading hex digit이 있는 $x$ 를 쓸 수 있고, 그 이후에 $j$ 개의 hexadecimal 0들이 나온다. 예를들어, $x = 2048 = 2^{11}$ 에 대해, 우리는 $n = 11 = 3 + 4 \cdot 2$ 를 갖게 되고, 이것은 hexadecimal representation 0x800를 준다.

decimal과 hexadecimal representations사이에 변환하는 것은 그 일반 케이스를 다루기 위해 곱셈 또는 나눗셈을 사용하는 것을 요구한다. decimal number x를 hexadecimal로 변환하기 위해, 우리는 반복적으로 x를 16으로 나눈다. 그리고 이것은 몫 q와 나머지 r를 주고, $x = q \cdot 16 + r$ 이 되게 한다. 우리는 그러고나서 r를 least significant digit으로서 나타내는 hexadecimal digit를 사용하고, q에 대한 처리를 반복하여 나머지 digits을 생성한다. 예를들어, decimal 314156를 변환하는 것을 고려해라:
$314156 = 19634 \cdot 16 + 12 \;\; (C) \\ 19634 = 1227 \cdot 16 + 2 \;\; (2) \\ 1227 = 76 \cdot 16 + 11 \;\; (B) \\ 76 = 4 \cdot 16 + 12 \;\; (C) \\ 4 = 0 \cdot 16 +4 \;\; (4)$
이것으로 부터, 우리는 hexadecimal representation을 0x4CB2C로 읽을 수 있다.

역으로, hexadecimal number를 decimal로 바꾸기 위해, 우리는 16의 적절한 지수승으로 hexadecimal digits의 각각을곱할 수 있다. 예를들어, 숫자 0x7AF에 대해, 우리는 그것의 decimal를 다음으로 계산한다 $7 \cdot 16^2 + 10 \cdot 16 + 15 = 7 \cdot 256 + 10 \cdot 16 + 15 = 1792 + 160 + 15 = 1967.$

2.1.2 Words

모든 컴퓨터는 word size를 갖는데, 이것은 integer와 pointer data의 명목상 size를 가리킨다. virtual address는 그러한 word에 의해 인코딩되기 때문에, 그 word size에 의해 결정되는 가장 중요한 system parameter는 virtual address space의 maximum size이다. 즉, w-bit word size를 가지는 한 machine에 대해, 그 virtual address는 0에서 $2^w - 1$ 의 범위를 가질 수 있고, 이것은 최대로 $2^w$ bytes에 대한 접근을 프로그램에게 준다.

대부분의 개인 컴퓨터들은 오늘날 32-bit word size를 가진다. 이것은 virtual address space를 4 gigabytes (4GB로 쓰여지는), 즉 $4 \times 10^9$ bytes로 제한한다. 비록 이것이 대부분의 어플리케이션들에 대해 충분한 공간일지라도, 우리는 많은 큰 스케일의 과학적 그리고 data base applications이 더 큰 storage의 양을 요구하는 지점에 도달해왔다. 결과적으로, 64-bit word sizes를 가진 high-end machines이 storage costs가 낮아짐에따라 점점 흔해지고 있다. 하드웨어 비용은 시간에 따라 떨어지기 때문에, 심지어 데스크탑과 laptop machines은 64-bit word sizes로 바뀔 것이고,그래서 우리는 w-bit word size의 일반 경우를 고려할 것이고, 뿐만아니라 $w = 32$ , $w = 64$ 의 특별한 경우들을 고려할 것이다.

2.1.3 Data Sizes

…

그 C data type int는 또한 qualifiers인 short long, 그리고 최근에는 long long으로 prefixed되어질 수 있다. 이것은 다양한 크기의 integer representations을 제공한다.

프로그래머들은 그들의 프로그램들이 다른 machines과 compilers에 걸쳐서 portable하도록 만들려고 노력해야 한다. portability의 한 측면은 그 프로그램이 다른 data types의 정확한 크기에 대해 많은 주의를 기울이게 만드는 것이다. C 표준의 다른 data types의 numeric ranges에 대해 하한을 설정한다, 이것은 나중에 다뤄질 것이진다. 그러나 어떠한 상한은 없다. 32-bit machines은 1980년대 이후로 표준이였기 때문에, 많은 프로그램들은 그림 2.3에서 이 word size를 위해 열거된 할당들을 가정하여 작성되어 왔다. 64-bit machines의 증가하는 이용가능성에 따라, 많은 숨겨진 word size dependencies는 이러한 프로그램들을 새로운 machines으로 이동시키는데 있어서 버그로서 나타날 것이다. 예를들어, 많은 프로그래머들은 type int로 선언된 program object가 한 포인터를 저장하도록 사용될 수 있다고 가정한다. 이것은 대부분의 32-bit machines에서는 잘 작동하지만, 64-bit machine에서 문제를 만든다.

2.1.4 Addressing and Byte Ordering

여러 bytes로 확장되는 program objects들에 대해, 우리는 두 가지 conventions을 구축해야 한다: 그 오브젝트의 주소가 무엇이 될 지를, 그리고 그 bytes가 메모리에서 그 bytes를 어떻게 순서지을지를. 가상적으로 모든 machines에서, multi-byte object는 계속되는 bytes의 연속으로서 저장되는데, 그 오브젝트의 주소는 사용된 bytes의 가장 작은 주소가 주어진다. 예를들어, int type의 변수 x가 0x100의 주소를 가진다고 가정하자. 즉, address expression &x의 값이 0x100이다. 그러고나서 x의 4 bytes는 메모리 위치들 0x100, 0x101, 0x102, 그리고 0x103에 저장되어질 것이다.

한 오브젝트를 나타내는 bytes를 순서짓는 것에 대해, 두 가지 흔한 conventions이 있다. w-bit integer가 한 bit representation $[x_{w-1}, x_{w-2}. \dots, x_1, x_0]$ 를 갖는다고 고려하자. 여기에서 $x_{w-1}$ 은 most significant bit이고 $x_0$ 이 least이다. $w$ 가 8의 배수라는 것을가정하여, 이러한 bits는 bytes로 묶여질 수 있고, most significant byte는 $[x_{w-1}, x_{w-2}, \dots, x_{w-8}]$ 를 가지고, 그 least significant byte는 $[x_7, x_6, \dots, x_0]$ bits를 가지고, 다른 bytes들은 중간의 bits들을가진다. 어떤 machines은 메모리에 있는 오브젝트가 least significant byte에서 most로 순서가 되도록 저장하는 것을 선택하는 반면에, 다른 machines들은 most to least로 그것들을 저장한다. 전자의 convention - least significant byte가 처음에 오는 - 것은 little endian이라고 지칭된다. 이 컨벤션은 대부분의 Intel과 호환되는 머신들에 의해 따라진다. 후자의 컨벤션 - most significant byte가 먼저 오는 -은 big endian이라고 지칭된다. 이 컨벤션은 IBM과 Sun Microsystems의 대부분의 머신들에 의해 따라진다. 우리가 "most"라고 말했다는 것에 주목해라. 그 conventions은 회사의 영역에 따라 정화하게 분리되지 않는다. 예를들어, IBM과 Sun은 Intel과 호환가능한 프로세서들을 사용하고 그러므로 little endian인 machines들을 제조한다. 많은 최근의 microprocessors들은 bi-endian인데, 이것은 그것들이 little- or big-endian machines 둘 중 하나로서 작동하도록 설정될 수 있다는 것을 의미한다.

우리의 이전 예제들을 계속하여, int type의 변수 x를 가정하고, 주소 0x100에서 0x01234567의 값을 갖는다고 가정하자. address range 0x100에서 0x103까지의 bytes의 ordering은 machine의 type에 의존한다:

* Big Endian
0x100	0x101	0x102	0x103
 01		 23		 45		 67

* Little endian
0x100	0x101	0x102	0x103
 67		 45		 23		 01

0x01234567 단어에서, high-order byte가 hexadecimal value 0x01를 갖지만, low-order byte가 value 0x67를 갖는다는 것에 주목해라.

…

egg 문제처럼, 다른것에 대해 한 byte ordering convention을 선택할 어떠한 기술적 이유가 없고, 그러므로 그 논쟁은 사회 정치적인 문제로 다투는 것으로 퇴화된다. 그 컨벤션들 중 하나가 선택되고 일관되게 고수되는 한, 그 선택은 임의적이다.

대부분의 application programmers에 대해, 그들의 machines에 의해 사용되는 byte orderings은 전적으로 보이지 않는다; machine의 어떤 클래스든지에 대해 컴파일되는 프로그램은 동일한 결과를 준다. 그러나, 때때로, byte ordering은 문제가 된다. 그 첫 번째는 binary data가 다른 machines사이에서 network를 걸쳐 통신될 때 이다. 한 흔한 문제는 little-endian machine에서 생성된 데이터가 big-endian machine으로 보내지는 것이다. 또는 역으로이다. 이것은 받는 프로그램에 대해 반대 순서로된 words내의 bytes를 이끌게 된다. 그러한 문제를 피하기 위해, networking applications를 위해 작성되는 코드는 보내는 machine이 그것의 내부 representation이 network 표준으로 바꾸도록 하는 byte ordering을 위한 구축된 컨벤션을 따라야 한다. 반면에, receiving machine은 그 network standard를 그것의 내부 표기로 바꾼다. 우리는 이 변환의 예제를 Chapter 11에서 볼 것이다.

byte ordering이 중요한 두 번째 경우는, integer data를 나타내는 byte sequences를 볼 때이다. 이것은 종종 machine-level programs를 조사할 때 발생한다. 예로서, 다음의 line은 Intel IA32 processor를 위해 machine-level code의 text representation를 주는 파일에서 발생한다

80483bd:	01 05 64 94 04 08	add	%eax, 0x8049464

이 line은 disassembler에 의해 생성되었는데, 이것은 executable program file에 의해 나타내어지는 instruction sequence를 결정하는 도구이다. 우리는 disassemblers에 대해 더 배울 것이고, Chapter 3에서 이것과 같은 lines을 어떻게 해석하는지를 배울 것이다. 지금은, 우리는 간단히 이 line이 hexadecimal byte sequence 01 05 64 94 04 08를 instruction의 byte-level representation이라는 것을 말하는 것에 주목한다. 이 명령어는 0x8049464 주소에 저장되어 있는 값에 data의 word를 추가하는 것이다. 만약 우리가 그 sequence의 마지막 4 bytes를 취한다면, 64 94 04 08, 그리고 그것들을 역순으로 쓴다면, 우리는 08 04 94 64를 가진다. leading 0을 없애고, 우리는 0x8049464인 오른쪽에 쓰여진 숫자 값을 가지게 된다. bytes가 역순으로 나타나게 하는 것은, 흔히 발생하는데, 이것과 같은 little-endiand를 위해 생성된 machine-level program representations을 읽을 때이다. byte sequence를 작성하는 자연스러운 방법은 lowest-numbered byte를 왼쪽에, 오른쪽에는 highest를 갖는 것이지만, 이것은 most significant digit을 left에 least를 right에 쓰는 것 일반적인 방법과 대조적이다.

byte ordering이 보이는 세 번째 경우는 normal type system을 우회하는 programs이 작성되었을 때 이다. C language에서, 이것은 한 object가 그것이 생성되었던 것과 다른 data type을 따라서 참조되도록 하도록 하기 위해 cast를 사용하여 처리된다. 그러한 coding tricks은 강하게 추천되지 않지만, 그것들은 system-level programming에서 꽤 유용하고 심지어 필수적이다.

…

floating-point와 integer data 둘 다가 numeric value 12,345를 인코딩할 지라도, 그것들은 매우 다른 byte patterns을 가진다는 것을 관찰해라: integer에 대해 0x00003039, floating point에 대해 0x4640E400. 일반적으로 이러한 두 포맷들은 다른 encoding schemes를 사용한다. 만약 우리가 이러한 hexadecimal patterns을 binary form으로 확장하고, 그것들을 적절히 shift하면, 우리는 13개의 매칭되는 비트들의 sequence를 찾고, asterisks의 sequence로 다음과 같이 표기한다:

   0   0   0   0   3   0   3   9 
00000000000000000011000000111001 
                   *************
             4   6   4   0   E   4   0   0
          01000110010000001110010000000000

이것은 우연이 아니다. 우리는 우리가 floating-point formats을 공부할 때 이 예제로 돌아올 것이다.

…

2.1.5 Representing Strings

…

2.1.6 Representing Code

다음의 C 함수를 고려해라:

int sum(int x, int y) {
	return x + y;
}

우리의 sample machines에서 컴파일 될 때, 우리는 다음의 byte 표기를 갖는 machine code를 생성한다:

Linux 32: 	55 89 e5 8b 45 0c 03 45 08 c9 c3 
Windows: 	55 89 e5 8b 45 0c 03 45 08 5d c3 
Sun: 		81 c3 e0 08 90 02 00 09 
Linux 64: 	55 48 89 e5 89 7d fc 89 75 f8 03 45 fc c9 c3

여기에서 우리는 instruction codings이 다르다는 것을 발견한다. 다른 machine types은 다르고 호환되지 않는 instructions과 encodings을 사용한다. 심지어 다른 운영체제를 작동시키는 동일한 프로세서들은 그들의 코딩 컨벤션에서 차이를 가지고 있고, 그러므로 binary compatible하지 않다. Binary code는 machine과 operating system의 다른 조합에 걸쳐서 결코 portable 하지 않다.

computer systems의 기본 개념은, machine의 관점으로부터, 한 프로그램이 bytes의 한 sequence인 것이다. 그 machine은 original source program에 대한 어떠한 정보를 가지고 있지 않다. 아마도 debugging을 도움을 주기 위해 유지되는 보호 테이블을 제외하고. 우리는 이것을 Chapter 3에서 machine-level programming을 공부할 때 좀 더 명백하게 보게 될 것이다.

2.1.7 Introduction to Boolean Algebra

binary values가 computers가 정보를 encode, store, 그리고 manipulate하는 방법의 핵심에 있기 때문에, 풍부한 수학적 지식이 0과 1의 값에 대한 연구에 대해 진화해왔다. 이것은 George Boole (1815-1864)의 작업으로 시작했었고, 따라서, Boolean algebra로 알려져있다. Boole는 logic values를 TRUE와 FALSE를 1과 0으로 encoding하여, logical reasoning의 기본 원칙을 포착하는 대수를 공식화 할 수 있엇다.

가장 간단한 Boolean algebra는 2개의 원소 집합인 {0, 1}에 대해 정의된다. 그림 2.7은 이 대수에 대해 몇 가지 연산들을 정의한다.

이러한 연산들을 나타내기 위한 우리의 symbols은 나중에 이야기 될 C bit-level operations에 의해 사용되느 ㄴ것과 부합되는 걸 선택되었다. 그 Boolean operation ~는 location operation NOT에 대응되고, symbol $\lnot$ 에 의해 표기된다. 즉, P가 true가 아닐 때, ¬P는 true라고 말한다. 역으로도 그렇다. 대응되어, p가 0일 떄, ~p는 1과 같다. Boolean operation &는 logical operation AND와 대응되고, symbol KaTeX parse error: Undefined control sequence: \and at position 1: \̲a̲n̲d̲에 의해 표기된다. 우리는 KaTeX parse error: Undefined control sequence: \and at position 3: P \̲a̲n̲d̲ ̲Q가 both P가 true이고 Q가 true 일 때 유효하다고 말한다. 대응하여, $p \; \& \; q$ 는 $p = 1$ 이고 $q = 1$ 일 때에만 1과 같다. Boolean operation $|$ 는 logical operation OR와 대응되고, symbol KaTeX parse error: Undefined control sequence: \or at position 1: \̲o̲r̲로 표기된다. 우리는 P가 true이거나 Q가 true일 때, KaTeX parse error: Undefined control sequence: \or at position 3: P \̲o̲r̲ ̲Q가 유효하다고 말한다. 대응하여, $p \; | \; q$ 는 $p = 1$ 이거나 $q = 1$ 일 때, 1과 같다. Boolean operation ^는 logical operation EXCLUSIVE-OR와 대응되고, symbol $\oplus$ 로 표기된다. 우리는 P가 true이거나 Q가 true 둘 중 하나이지만, 둘 다는 아닐 때, $P \oplus Q$ 가 유효핟고 말한다. 그에 따라, p ^ q는 p = 1이고 q = 0이거나 p = 0이고 q = 1일 때 1이다.

나중에 information theory의 분야를 만든 Claude Shannon (1916-2001)은 처음에 Boolean algebra와 digital logic사이의 연결을 만들었다. 그의 1937 석사 논문에서, 그는 Boolean algebra가 electromechanical relays의 networks의 설계와 분석에 적용될 수 있다는 것을 보여주었다. 비록 컴퓨터 기술이 그 때 이후로 상당히 진보했을지라도, Boolean algebra는 여전히 digital systems의 설계와 분석에 있어서 중요한 역할을 한다.

우리는 4개의 Boolean operations이 또한 bit vectors에 작동하도록 확장시킬 수 있다. 그것은 어떤 고정된 길이 $w$ 의 0과 1의 strings이다. 우리는 arguments의 매칭되는 원소들에 대한 적용에 따라 bit vectors의 연산들을 정의한다. $a$ 와 $b$ 가 bit vectors $[a_{w-1}, a_{w-2}, \dots, a_0]$ 과 $[b_{w-1}, b_{w-2}, \dots, b_0]$ 로 표기된다고 하자. 우리는 $a \; \& \; b$ 가 또한 길이 w의 bit vector가 된다고 정의하고, 거기에서 i번째 원소는 $0 \leq i \leq w$ 에 대해 $a_i \; \& \; b_i$ 와 같다. 그 operations |, ^, 과 ~는 같은 방식으로 bit vectors에 확장된다.

Web Aside Data : Bool More on Boolean algebra and Boolean rings

w의 길이를 가진 bit vectors에 연산되는 Boolean operations |, &, 그리고 ~ 는 Boolean algebra를 형성한다. 어떤 정수 w > 0에 대해. 가장 간단한 것은, w = 1인 경우이고, 두 개의 elements가 있다. 그러나 조 ㅁ더 일반적인 경우에, 길이가 w인 $2^w$ bit vectors가 있다. Boolean algebra는 정수에 대해 대수에서 많은 같은 특성을 가진다. 예를들어, 곱셈이 덧셈에 대해 분배되듯이, $a \cdot (b + c) = (a \cdot b) + (a \cdot c)$ 라고 쓰여지고, Boolean operation &은 |에 대해 분배되고, $a ; & ; (b ; | ; c) = (a ; & ; b) ; | ; (a ; & ; c) $로 쓰여진다. 게다가, 그러나, Boolean operation |은 $\&$ 에 대해 분배된다. 그래서 우리는 $a ; | ; (b ; & ; c) = (a ; | ; b) ; & ; (a ; | ; c) $라고 쓸 수 있다. 반면에, 우리는 모든 정수에 대해 그렇게 쓸 수 없다.

우리가 w의 길이를 가진 bit vectors에 작용하는 ^, &, ~ 연산들을 고려할 때, 우리는 Boolean ring이라고 알려진 다른 수학적 형태를 얻는다. Boolean rings은 정수 대수 많은 공통 특성을 가진다. 예를들어, 정수 대수의 한 특성은 모든 x가 역원 -x를 가지고, x + -x = 0이 되게 한다. 비슷한 특성이 Boolean rings에 대해 유효하다. 거기에서 ^는 “addition” operation이지만, 이 경우에, 각 element는 그것 자신의 additive inverse이다. 즉, 어떤 값 a에 대해, a ^ a = 0이다.거기에서, 우리는 모든 zeros의 bit vector를 나타내기 위해 0을 사용한다. 우리는 단일 bits들에 대해 이것이 유효하다는 것을 알 수 있다. 왜냐하면 0 ^ 0 = 1 ^ 1 = 0이고, 이것은 bit vectors에게도 확장이 되어진다. 이 특성은 심지어 우리가 항들을 재배치하고, 그것들을 다른 순서로 합할 때에도 유효하다. 그래서 (a ^ b) ^ a = b이다. 이 특성은 흥미로운 결과와 똑똑한 트릭을 이끈다. 우리가 Problem 2.10에서 조사하게 되듯이.

bit vectors의 한 가지 유용한 적용은 유한한 집합을 나타내는 것이다. 우리는 bit vector $[a_{w-1}, a_{w-2}, \dots, a_1, a_0]$ 로 $A \subseteq \{0, 1, \dots, w - 1 \}$ 를 encode할 수 있다. 거기에서 $i \in A$ 인 경우에만 $a_i = 1$ 이다. 예를들어, 우리가 $a_{w-1}$ 를 왼쪽에, $a_0$ 을 오른쪽에 쓴다는 것을 회상하면, bit vector $a \doteq [01101001]$ 은 집합 $A = \{0, 3, 5, 6\}$ 을 encodes한다. 반면에 bit vector $b \doteq [01010101]$ 은 집합 $B = \{0, 2,4, 6\}$ 를 인코딩한다. 집합을 이 방식으로 인코딩하여, Boolean operations |과 &는 각각 union과 intersection를 설정하는 것으로 대응되고, ~는 complement를 설정하는 것으로 대응된다. 우리의 이전 예제를 계속하여, $a \; \& \; b$ 는 bit vector $[01000001]$ 를 만들어낸다. $A \cap B = \{0, 6\}$ 이면서.

우리는 많은 실제적인 적용에서 bit vectors로 집합의 encoding을 볼 것이다. 예를들어, Chapter 8에서, 우리는 한 프로그램의 실행을 interrupt할 수 있는 많은 다른 signals이 있다는 것을 볼 것이다. 우리는 bit-vector mask를 명시하여 다른 signals를 선택적으로 활성화하거나 비활성화 할 수 있다. 여기에서 bit position i에 있는 1은 signal i가 활성화 되어있다는 것을 가리키고, 0은 그것이 비활성화 되어 있다는 것을 가리킨다. 따라서, 그 mask는 활성화된 signals의 집합을 나타낸다.

2.1.8 Bit-Level Operations in C

– 이러한 것들 (Boolean operation)은 어떠한 “integral” data type에 적용되어질 수 있다. 즉, type char, int로 선언되는 것이고, short, long, long long, unsigned같은 qualifiers들이 있고 없는 것들. 여기에서 data type char에 대한 몇 가지 expression evaluation의 예가 있다:

C expression	Binary expression	Binary result	Hexadecimal result
~0x41	~[0100 0001]	[1011 1110]	0xBE
~0x00	~[0000 0000]	[1111 1111]	0xFF
0x69 & 0x55	[0100 1001] & [0101 0101]	[0100 0001]	0x41
0x69 \| 0x55	[0100 1001] & [0101 0101]	[0111 1101]	0x7D

Practice Problem 2.10

어떤 bit vector a에 대해 a ^ a = 0 의 특성 적용으로서 다음의 프로그램을 고려해라:

void inplace_swap(int *x, int *y)
{
    *y = *x ^ *y;	/* Step 1 */
    *x = *x ^ *y;	/* Step 2 */
    *y = *x ^ *y;	/* Step 3 */
}

이름이 암시하듯이, 우리는 이 절차의 결과가 pointer 변수 x와 y에 의해 표기되는 위치에 저장된 값을 바꾸는 것이라고 주장한다. 두 개의 값을 바꾸는 보통의 기법과 다르게, 우리는 우리가 다른 곳으로 옮기는 동안 한 값을 임시적으로 저장할 세 번째 위치가 필요하지 않다. 이 swapping의 방법에 대해 어떠한 성능 이점이 없다; 그것은 단지 지적인 즐거움이다.

x와 y에 의해 가리켜지는 위치에서 a와 b의 값으로 각각 시작하여, 다음의 테블을 채우고, 그 절차의 각 단계후의 두 위치에서 저장된 값을 주어라. 그 요구되는 결과가 성취되는 것을 보여주기위해 ^의 properties를 사용해라. 모든 element가 그것 자신의 additive inverse라는 것 (즉, a ^ a = 0)이라는 것을 기억해라.

Step	*x	* y
Initially	[0101 1110] == 0x5E	[0001 1001] == 0x19
Step 1	[0101 1110] == 0x5E	[0100 0111] == 0x47
Step 2	[0001 1001] == 0x19	[0100 0111] == 0x47
Step 3	[0001 1001] == 0x19	[0101 1110] == 0x5E

Practice Problem 2.11

Problem 2.10의 함수 inplace_swap으로 무장하여, 너는 array의 반대 끝에서 중간으로 가서 elements를 바꾸어서 한 배열의 원소를 바꿀 코드를 작성하기로 결정한다.

너는 다음의 함수에 도달한다:

void reverse_array(int a[], int cnt) {
    int first, last;
    for (first = 0, last = cnt - 1;
        first <= last;
        first++, last--)
        inplace_swap(&a[first], &a[last]);
}

너가 1,2,3,4의 원소를 가진 배열에 함수를 적용할 때, 너는 예상되듯이 그 배열이 이제 원소 4, 3, 2, 1를 갖는다는 것을 알게된다. 너가 그것을 1,2,3,4,5의 원소를 가진 배열에 시도할 때, 그러나, 너는 그 배열이 이제 5, 4, 0, 2, 1를 가지게 되어서 놀라게 된다. 사실, 너는 그 코드가 짝수 길이의 배열에만 항상 작동하지만, 그것이 배열이 홀수 일 때 중간 원소가 0으로 설정된다는 것을 발견하게 된다.

A. 홀수 길이의 cnt = 2k + 1의 배열에 대해, 함수 reverse_array의 마지막 iteration에서 first와 last의 변수의 값은 무엇인가?

first == last == cnt / 2 + 1

B. 왜 xor_swap 함수에 대한 호출은 그 배열 원소를 0으로 만드는가?

같은 원소에 즉, 같은 값에 대한 xor은 항상 0이다.

C. reverse_array의 코드에 대해 무슨 간단한 수정이 이 문제를 제거할 것 인가?

for문의 조건문을 first < last로 바꾼다.

Practice Problem 2.12

다음의 값들에 대해 변수 x의 관점에서 C 문장을 써라. 너의 코드는 $w \geq 8$ 인 어떤 word size에 대해 작동해야 한다. 참조를 위해, $w = 32$ 인 $0x87654321$ 에 대한 문장의 결과를 보여주어라.

A. 모든 다른 비트를 0으로 설정한 x의 least significant byte [0x00000021].

int result = 0xFF & x;

B. least significant byte는 안바뀐채 나머지 byte가 보수되는 것. [0x789ABC21].

int result = x ^ ~0xFF

이것에 대한 것은 다음의 성질을 알고 있으면 좋다.

0x00000000(32 bit)과 어떤 값 x에 대한 xor연산은 항상 x이다. 왜냐하면 x에 1로 되어있는 것은 그 해당 자리가 1로 될 것이고, 0으로 된 것은 0으로 될 것이기 때문이다. 0x0과 어떤 값 x에 대한 xor연산은 0x00000000 | x의 연산으로 보아도 된다.

0x11111111(32 bit)과 어떤 값 x에 대한 xor연산은 항상 ~x이다. 왜냐하면, x에 1로 되어있는 것은 그 해당자리가 0으로 될 것이고, 0으로 된 것은 항상 1로 될 것이기 때문이다. 이것은 ~(0x11111111 & x)로 봐도 된다.

C. least significant byte가 항상 1로 설정되고, 모든 다른 bytes는 바뀌지 않는다. [0ㅌ876543FF].

int result = 0xFF | x;

Practice Problem 2.13

Digital Equipment VAX computer는 1970년대 후반부터 1980년대까지 매우 인기있는 머신이였다. Boolean operations에 대한 명령어 AND와 OR보다는, 그것은 bis (bit set)과 bic (bit clear) 명령어를 가졌다. 두 명령어는 한 data word x와 mask word m을 가진다. 그것들은 m의 비트들에 따라 수정된 x의 비트들로 구성된 결과 z를 생성한다. bis로, 그 수정은 m이 1인 각각의 비트 포지션에서 z를 1로 설정하는 것을 포함한다. bic로, m이 1인 각 bit position에서 z를 0으로 만드는 설정을 포함한다.

이 연산이 C bit-level 연산에서 어떻게 관련있는지를 보기위해, 우리는 그 bit set과 bit clear operations을 구현하는 bis와 bic 함수들을 가진다고 가정하고, bit-wise operations |와 ^를 어떠한 다른 C연산 없이 연산하는 함수를 구현하기 위해 이러한 것을 사용하길 원한다고 가정하자. 아래에서 빈 코드를 채워라. Hint : bis와 bic 연산을 위한 C expression을 작성해라.

/* Declarations of functinos implementing operations bis and bic */
int bis(int x, int m)
{
    return x | m;
}

int bic(int x, int m)
{
    return x & ~m;
}

/* Compute x|y using only calls to functions bis and bic */
int bool_or(int x, int y) {
    int result = bis(x, y);
    return result;
}

/* Compute x^y using only calls to functions bis and bic */
int bool_xor(int x, int y)
{
    int result = bis(bic(x,y), bic(y,x));
}

Chan : bool_xor은 모르겠어서 답을 보았다. 일단 bis의 1번 째 파라미터와, 2 번째 파라미터에 들어가는 것이 즉, x ^ y = (x & ~y) | (~x & y)의 각 항이 무엇을 가리키는지 알아보고자 한다. 먼저 왼쪽 항의 (x & ~y)에 대해 알아야 한다. ~y를 했을 때, y의 0은 1이되고 1은 0이된다. 그 상태에서, x와 AND 연산을 하게 된다. 케이스 별로 살피게 되면

x y result (x & ~ y)

1 1 0

1 0 1

0 1 0

0 0 0

즉 이것을 보면, x가 1이고, y가 0인 경우에만 1이 세팅되어진다.

이제 우측 항에 대해서도 알아보면

x y result (~x & y)

1 1 0

1 0 0

0 1 1

0 0 0

이 때는 x가 0이고 y가 1인 경우에만 1이 세팅되어진다.

따라서 왼쪽항에는 x의 1, y의 0으로 세팅 되어있는 애들만 1이 되어지고, 오른쪽 항에는 x의 0, y의 1로 세팅되어있는 애들만 1이 되어진다. 즉, 다른 것들만 1로 세팅되어서 그것들의 OR 연산을 하게 되면, XOR 연산이 되게 된다.

2.1.9 Logical Operations in C

C는 또한 logical operators ||, &&, !의 세트를 제공한다. 그리고 이것은 논리의 OR, AND, NOT 연산과 같다. 이러한 것들은 bit-level 연산과 쉽게 혼동되어질 수 있찌만, 그것들의 함수는 꽤 다르다. 그 논리 연산은 어떤 0이 아닌 argument를 TRUE로 나타내는 것으로 하고, argument 0을 FALSE로 나타내어 다룬다. 그것들은 1 또는 0 둘 중 하나를 반환하는데, 이것은 각각 TRUE 또는 FALSE 둘 중 하나의 결과를 가리킨다. 여기에 expression evaluation의 몇 가지 예제가 있다:

Expression	Result
!0x41	0x00
!0x00	0x01
!!0x41	0x01
0x69 && 0x55	0x01
0x69 \|\| 0x55	0x01

bit-wise 연산은 arguments가 0 또는 1로 제한되는 특별한 경우에만 그것의 논리 연산자의 대응물과 같은 행동을 가진다는 것을 관찰해라.

논리 연산자 &&, || 와 그것들의 bit-level 의 대응되는 것인 *, | 사이의 두 번째 중요한 구분은 논리 연산자는 expression의 결과가 첫 번째 argument를 evaluate하여 결정될 수 있따면, 그것들의 두 번째 argument를 evaluate하지 않는다는 것이다. 따라서, 예를들어, 그 expression a && 5/a는 결코 0으로 나누는 것을 발생시키지 않을 것이고, expression p && *p++는 결코 null pointer를 역참조하지 않게 할 것이다.

Practice Problem 2.14

x와 y가 byte values 0x66과 0x39를 각각 가졌다고 가정하자. 다른 C expressions의 byte values를 가리키는 다음의 태이블을 채워라.

0x66 == [0110 0110]

0x39 == [0011 1001]

Expression	Value	Expression	Value
x & y	0x20	x && y	0x01
x \| y	0x7E	x \|\| y	0x01
~x \| ~y	0xDF	!x \|\| !y	0x00
x & !y	0x00	x && ~y	0x01

Practice Problem 2.15

오직 bit-level과 logical operations만을 사용하여, x == y와 같은 C expression을 작성해라. 다시 말해서, x와 y가 동일하면 1를 반환하고, 아니면 0을 반환할 것이다.

int equal(int x, int y)
{
    return !(x ^ y);
}

2.1.10 Shift Operations in C

C는 또한 bit patterns을 왼쪽으로 그리고 오른쪽으로 옮기기 위한 shift operations의 한 집합을 제공한다. bit 표기 $[x_{n-1}, x_{n-2}, \dots, x_0]$ 을 가지는 operand x에 대해, C expression x << k는 bit representation $[x_{n-k-1}, x_{n-k-2}, \dots, 0, \dots, 0]$ 의 값을 만들어낸다. 즉, x는 왼쪽으로 k bits로 이동하고, k번째 most significant bits까지 버리고, 오른쪽 끝을 k개의 0으로 채운다. 그 shift 양은 0과 n-1 사이의 값이여야 한다. Shift operations은 왼쪽에서 오른쪽까지 associate한다. 그래서,x << j << k는 (x << j) << k와 같다.

대응되는 right shift operation x >> k가 있지만, 이것은 다소 미묘한 행동을 가진다. 일반적으로 machines은 right shift의 두 가지 형태를 지원한다 : logical과 arithmetic. logical right shift는 왼쪽 끝을 k개의 0으로 채우고, 다음의 결과를 준다 $[0, \dots, 0, x_{n-1}, x_{n-2}, \dots, x_k]$ . arithmetic right shift는 왼쪽 끝을 most significant bit의 k개의 반복으로 채운다. 그리고 다음의 결과를 준다 $[x_{n-1}, \dots, x_{n-1}, x_{n-1}, x_{n-2}, \dots, x_k]$ . 이 convention은 특이하것 처럼 보이지만, 우리가 보게 되듯이 이것은 signed integer data에 작동하는데 유용하다.

예를들어, 다음의 테이블은 어떤 샘플 8-bit data에 대하 다른 shift operations을 적용한 효과를 보여준다:

Operation	Values
Argument x	[01100011] [10010101]
x << 4	[00110000] [01010000]
x >> 4 (logical)	[00000110] [00001001]
x >> 4 (arithmetic)	[00000110] [11111001]

그 이탤릭 표기된 숫자들은 오른쪽 끝을 채우거나 (left shift) 왼쪽 끝을 (right shift) 채운 값들을 가리킨다. 한 entry를 제외하고 0으로 채워지는 것을 관찰해라. 그 예외는 [10010101]을 오른쪽으로 arithmetically shift하는 경우이다. 그것의 most significant bit이 1이기 때문에, 이것은 그 fill value로서 사용될 것이다.

C 표준은 정확하게 right shift의 어떤 type이 사용될 지를 정의하지 않는다. unsigned data에 대해 (즉, unsigned qualifier로 선언된 integral objects), right shifts는 logical이여야 한다. signed data (default)에 대해, arithmetic 또는 logical shifts가 사용될지도 모른다. 이것은 불행하게도, 한 형태 또는 다른 것을 가정하는 어떤 코드는 잠재적으로 이식 문제를 겪게 될 것을 의미한다. 그러나, 실제로, 거의 모든 compiler/machine의 조합은 signed data에 대해 arithmetic right shifts를, 그리고 많은 프로그래머들은 이것이 사실이라고 가정한다.

반면에, Java는 right shifts가 어떻게 수행될지에 대한 정확한 정의를 갖는다. 그 표현식 x >> k는 x를 arithmetically하게 k 위치만큼 옮기고, 반면에 x >>> k는 그것을 logically하게 shift한다.

Aside 큰 k 값에 대해, k만큼 shift 하기.

w bits로 구성된 data type에 대해, $k \geq w$ 인 값만큼 shift하는 것의 효과는 무엇이 되는가? 예를들어, 32-bit machine에서 다음의 식을 연산하는 것의 결과가 무엇인가:
int			lval = 0xFEDCBA98 << 32;
int			aval = 0xFEDCBA98 >> 36;
unsigned	uval = 0xFEDCB498u >> 40;
그 C 표준은 그러한 겨웅에 무엇이 되어야 하는지 명시하는 것을 세심하게 피한다. 많은 machines들에서, 그 shift instructions은 w-bit value를 옮길 때, shift 양의 lower $log_2w$ 만을 고려하고, 그래서 그 shift amount는 k mod w로서 효과적으로 연산된다. 예를들어, 이 컨벤션을 따르는 32-bit machine에서, 위의 세 shifts는 그것들이 각각 0, 4 그리고 8의 양인 것처럼 연산된다.
lval	0xFEDCBA98
aval`	0xFFEDCBA9
uval	0x00FEDCBA
그러나, 이 행동은 C programㄴ에 대해 보장되지 않고, 그래서 shift 양은 word size보다 더 작게 유지되어야 한다.

반면에, Java에서는 shift 양이 우리가 보여준 modular 방식으로 연산되어지는 것을 요구한다.

Aside shift operations과 관련된 연산자 우선순위 문제 (Operator precedence)

1 << 2 + 3 << 4의 식을 쓰는 것은 유혹적일지 모른다. 이것이 (1 << 2) + (3 << 4)를 의미하도록 의도하면서. 그러나, C에서 이전의 식은 1 << (2 + 3) << 4와 같다. 왜냐하면, 덧셈(그리고 뺄셈)은 shifts보다 더 높은 우선순위를 갖기 때문이다. left-to-right associativity rule은 이것이 (1 << (2 + 3)) << 4로 괄호쳐지게 하고, 의도된 52의 값보다는 512의 값을 준다.

C expressions에서 우선순위를 잘못하는 것은 흔한 프로그램의 에러이고, 종종 이러한 것은 조사해서 찾기에도 어렵다. 의심될 때, 괄호를 넣어라!

Practice Problem 2.16

단일 byte quantities에 대해 다른 shifts들의 효과를 보여주는 테이블을 채워라. shift operations에 대해 생각하는 가장 좋은 방법은 binary representations과 작업하는 것이다. 초기 값을 binary로 바꾸고, shifts를 수행하고, 그러고나서 hexadecimal로 다시 바꾸어라. 그 각각의 답들은 8 binary digits 또는 2 hexadecimal digits이 되어야 한다.

Operation	Hex	Binary
x	0xC3	1100 0011
x << 3	0x18	0001 1000
x >> 2 (Logical)	0x30	0011 0000
x >> 2 (Arithmetic)	0xF0	1111 0000

x	0x75	0111 0101
x << 3	0xA8	1010 1000
x >> 2 (Logical)	0x1D	0001 1101
x >> 2 (Arithmetic)	0x1D	0001 1101

x	0x87	1000 0111
x << 3	0x38	0011 1000
x >> 2 (Logical)	0x21	0010 0001
x >> 2 (Arithmetic)	0xE1	1110 0001

x	0x66	0110 0110
x << 3	0x30	0011 0000
x >> 2 (Logical)	0x19	0001 1001
x >> 2 (Arithmetic)	0x19	0001 1001

CS : APP Chapter 2-1

댓글