[CSAPP] 1. Data lab (Bit Manipulation)

미국에 악명 높은 시스템 프로그래밍 관련 실험이 있다. CS:APP(Computer Science:A Programmer's Perspective)라고, 미국 카네기 멜론 대학(CMU) 랩(과제) 시리즈라고 한다. 각 과제마다 매우 성격이 다르지만, 나중에 프로그래밍으로 밥 벌어먹고살아야 하는 사람이라면 한 번은 거치고 가야 한다는 말이 있을 정도로 전 세계적으로 인기가 많고, 또 그만큼 유명세도 높은 랩이다.

 

나의 전공수업 '마이크로프로세서'(라 하고 시스템프로그래밍 가르치는 수업)에서 이 시리즈의 과제를 진행하는데, 과제 제출 이후 CSAPP 시리즈를 연재하면서 이에 대한 복기 차원에서 포스팅을 진행할 예정이다.

 

첫 번째 CSAPP의 과제는 Data lab으로, 제한된 횟수의 제한된 비트 연산을 통해 함수를 구현하는 것이다. 무슨 말인지 감이 안 온다면, 밑의 문제들을 먼저 본다면 무슨 말인지 단번에 이해할 수 있을 것이다.

---

문제

이번 과제는 총 15문제로 이루어져 있으며, 각 문제들에 대한 설명은 함수 위의 주석을 통해 알 수 있다. 각 문제의 설명에는 최대 연산 횟수, 가능한 연산자 등을 소개하고 있다.

 

Data lab의 특이한 점으로는, 모든 연산은 거의 c의 비트 연산으로만 처리를 해야 한다는 것이다. 그리고, 다음과 같은 규칙이 적용된다.

 

1. 정수는 0(0x00)부터 255(0xFF)까지만 사용할 수 없다. 이보다 큰 정수는 선언할 수 없다.
2. 전역 변수는 사용할 수 없다.
3. 제어문을 사용할 수 없다. (if, do, while, for, switch 등등 금지)
4. 매크로를 사용할 수 없다. (#define... 금지)
5. 다른 함수를 호출할 수 없다. (함수 사용 금지)
6. 주어진 연산자 이외의 연산자를 사용할 수 없다. (&&, ||, -, ? 등등 금지)
7. 어떠한 형태의 타입 변환도 할 수 없다. (int => unsigned int, int => double 금지)
8. int형 이외의 타입은 사용할 수 없다. (array, struct, union, pointer, float, double 등등 금지)
9. 모든 int형은 2의 보수 형태로 해석된다. (sign bit + 31bit)
10. right shift는 artithmetic shift이다. (right shift는 MSB가 복사되어 MSB를 채운다.)
11. negative shift 또는 32 이상의 shift는 undefined behavior이다.

다만, floating point관련 문제들은 정수의 크기에 제한이 없고 (0x0 ~ 0xFFFFFFFF), 제어문을 사용할 수 있다.

 

이러한 조건하에서, 더 적게 연산자를 사용하면 할수록 더 효율적으로 비트 연산을 한 것이니, 나의 해답보다 더 적은 횟수로 해결하였다면 댓글로 겐세이를 넣어도 좋다. (마음의 준비가 되어있다.)

 

이제, 하나씩 해결하여보자.

1. bitOr (4 / 8ops)

/* 
 * bitOr - x|y using only ~ and & 
 *   Example: bitOr(6, 5) = 7
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitOr(int x, int y) {
  // idea : ~& == |
  return ~((~x)&(~y));
}

 

• 허용 연산자 : ~ &
• 최대 연산 횟수 : 8

첫 문제는 ~(Bitwise NOT)과 &(AND)를 이용하여 OR를 구현하는 것이다. 중학교 때 배운 드모르간의 법칙을 활용한다면, 4번의 연산만으로 끝낼 수 있다.

 

2. oddBits (4 / 8ops)

/* 
 * oddBits - return word with all odd-numbered bits set to 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 2
 */
int oddBits(void) {
  // idea: pre-make 1010 1010 1010 1010 and copy
  int chunk;
  chunk = (0xAA << 8 | 0xAA);
  // chunk : 1010101010101010(16bits)
  return (chunk << 16) | chunk;
}

 

• 허용 연산자 : ! ~ & ^ | + << >>
• 최대 연산 횟수 : 8

두 번째 문제는 위 연산자들을 활용하여 1010 1010 ... 1010 1010 (0xAAAAAAAA)를 만드는 것이다. 0xAAAA(chunk)를 만들고, 이를 16번 shift한 것과 OR 연산을 하면 아주 쉽게 구할 수 있다.

 

3. rotateLeft (9 / 25ops)

/* 
 * rotateLeft - Rotate x to the left by n
 *   Can assume that 0 <= n <= 31
 *   Examples: rotateLeft(0x87654321,4) = 0x76543218
 *   Legal ops: ~ & ^ | + << >> !
 *   Max ops: 25
 *   Rating: 3 
 */
int rotateLeft(int x, int n) {
  // idea: shift left n | shift right (32-n), but fill 0 at front
  int rightShiftCount;
  int minusOne;
  int left, right;
  // 1. left part
  left = x << n;
  // 2. right part
  // get rightShiftCount = 32-n = 32+(-n) = 32+(~n+1) = 33+(~n);
  rightShiftCount = 33 + (~n);
  minusOne = ~0;
  /* -  ~0 << rightShiftCount = 1111 1111 ... 1110 (the number of 1s : n at left)
       doing & with this gets n length left data
       
     - ~(~0 << n) = 0000 ... 000 1111 (the number of 1s : n at right)
       doing & with this gets n length right data */
  right = (x >> rightShiftCount) & ~(minusOne  << n);
  
  return left | right; // accumulate the result
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 25

세 번째 문제는 rotateLeft로 위 연산자들을 활용하여 x를 왼쪽으로 n만큼 회전시켰을 때의 결과를 구하는 것이다.

 

가장 생각할 수 있는 간단한 방법은, 왼쪽으로 돌리는 것이므로 왼쪽의 n개의 비트와 오른쪽의 (32-n)개의 비트를 바꾸는 것이다. (x << n) 과 (x >> (32-n)) = (x >> (33 + ~n))를 합치면 간단한 문제인 줄 알았다.

 

문제는 right shift 연산이 logical shift가 아닌, arthimetic shift라는 것이다. 오른쪽으로 shift를 할 경우 sign bit이 1이면 1이 앞에 채워진다는 것이다. 이 경우 left part과 right part를 합칠 때, right part의 sign bit extension으로 인하여 left part의 정보를 살릴 수 없다는 것이다.

 

이를 해결하기 위해서는, 오른쪽으로 right shift한 다음, sign bit extended 된 부분을 제거해주는, 하나의 필터가 필요하다.

 

필요한 필터는 (0...01...1)의 꼴이고, 오른쪽에 1이 n개만큼 있어야 한다. 이를 위해서, left shift의 경우 오른쪽 끝에 0이 채워지므로 먼저 0xffffffff = ~0를 만들고, 이를 n개만큼 left shift하고, 이를 뒤집으면 n개의 1이 오른쪽에 있는 필터를 만들 수 있다.

 

right shift이후 필터와 & 연산을 취해 필요한 정보를 걸러낸 후, left part와 right part를 | 연산으로 합쳐주면 끝.

 

4. bitReverse (34 / 45ops)

/*
 * bitReverse - Reverse bits in a 32-bit word
 *   Examples: bitReverse(0x80000002) = 0x40000001
 *             bitReverse(0x89ABCDEF) = 0xF7D3D591
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 45
 *   Rating: 4
 */
int bitReverse(int x) {
  /*
    idea : shuffle in divide-and-conquer way, reducing in exponential size
    ex)Reversing 1-2-3-4-5-6-7-8
    1-2-3-4-5-6-7-8
    5-6-7-8-1-2-3-4
    7-8-5-6-3-4-1-2
    8-7-6-5-4-3-2-1
  */
  int filter;
  filter = (0xFF << 8) | 0xFF;
  // filter : 0000 0000 0000 0000 1111 1111 1111 1111 (0x0000FFFF)
  
  x = (((x >> 16) & filter) | (x << 16)); // shuffle each upper 16-bits & lower 16-bits
  filter = filter^(filter << 8);
  // filter: 0000 0000 1111 1111 0000 0000 1111 1111 (0x00FF00FF)
  x = (((x >> 8) & filter) | ((x & filter) << 8)); // shuffle each upper 8-bits & lower 8-bits
  filter = filter^(filter << 4);
  // filter: 0000 1111 0000 1111 0000 1111 0000 1111 (0x0F0F0F0F)
  x = (((x >> 4) & filter) | ((x & filter) << 4)); // shuffle each upper 4-bits & lower 4-bits
  filter = filter^(filter << 2);
  // filter: 0011 0011 0011 0011 0011 0011 0011 0011 (0x33333333)
  x = (((x >> 2) & filter) | ((x & filter) << 2)); // shuffle each upper 2-bits & lower 2-bits
  filter = filter^(filter << 1);
  // filter: 0101 0101 0101 0101 0101 0101 0101 0101 (0x55555555)
  x = (((x >> 1) & filter) | ((x & filter) << 1)); // shuffle each upper 1-bit & lower 1-bit
 
  return x;
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 45

네 번째 문제는 bitReverse로, 비트의 순서를 거꾸로 뒤집는 것이다. 쉽게 말해, 1-2-3-4로 비트가 있으면 이를 4-3-2-1로 뒤집는 것을 의미한다.

 

처음 보면 위의 코드가 어려울 수 있다. 하나하나씩 설명해보자. FFT(Fast Fourier Transform)알고리즘이나 이에 대한 아이디어를 아는 사람이면, 이 설명이 익숙할 것이지만 모른다고 해도 쉽게 이해한다면 충분히 이해할 수 있다.

 

이해를 쉽게 하기 위해서 1-2-3-4-5-6-7-8를 뒤집는다고 가정하자. 먼저, 상위 4개의 항목과 하위 4개의 항목을 뒤집자. 그럼, (5-6-7-8)-(1-2-3-4)가 된다. 이후 2개의 항목씩 짝지어서 뒤집자. 그럼, (7-8)-(5-6)-(3-4)-(1-2)가 된다. 이후 1개의 항목씩 짝지어서 뒤집자. 그럼, (8)-(7)-(6)-(5)-(4)-(3)-(2)-(1)가 된다. 따라서, 8-7-6-5-4-3-2-1이 된다. 이를 요약하면 다음과 같다.

 

1. 1-2-3-4-5-6-7-8
2. 5-6-7-8-1-2-3-4
3. 7-8-5-6-3-4-1-2
4. 8-7-6-5-4-3-2-1

 

이를 구현하여보자. 1-2-3-4-5-6-7-8을 뒤집는다고 하면, 5-6-7-8-1-2-3-4가 되어야 한다. 그러므로, 위의 3. rotateLeft와 같은 방법으로 구현하면 되지 않을까 생각하였다. 다만, 나중에는 2개씩 정보를 뽑아야 하므로 이 생각은 접었다.

 

이를 위해서 필터를 적용하는 방법을 떠올렸다. 상위 비트와 하위 비트 내용을 뽑아낸 다음, 이를 합치면 되지 않을까 생각을 하였다.

 

구체적으로 1-2-3-4-5-6-7-8을 예시로 들고, 상위 4비트와 하위 4비트를 뽑아내고 싶다면 다음과 같이 연산하면 된다. filter = 0x0F(0000 1111)로 하자.

 

a = (x >> 4) & filter = 0-0-0-0-1-2-3-4

b = (x & filter) >> 4 = 5-6-7-8-0-0-0-0

                       a | b = 5-6-7-8-1-2-3-4

 

이 과정을 여러 번 반복한다면, 비트를 뒤집을 수 있다.

 

그러면 filter는 어떻게 설계하면 되는가? 새로운 필터를 계속 만들 수 있지만, 기존의 filter에서 ^(XOR) 연산을 활용하면 새로운 filter를 만들 수 있다. 가령 0x00FF00FF = 0x0000FFFF ^ (0x0000FFFF << 8)이다.

 

이 방법보다 연산자 수를 더 줄일 수 있을까?

 

5. bang (5 / 12ops)

/* 
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int bang(int x) {
  // idea: just checking zero is enough!
  // if x == -x, then x = 0 else x != 0
  // -x = ~x+1
  // if x | (~x+1) == 0xFFFFFFFF <=> x != 0
  // else x | (~x+1) == 0x00000000 <=> x == 0;
  
  return ((x | (~x + 1)) >> 31) + 0x01;
}

 

• 허용 연산자 : ~ & ^ | + << >> 
• 최대 연산 횟수 : 12

다섯 번째 문제는 bang으로, !(Logical NOT)을 연산자 ! 없이 구현하는 것이다. 쉽게 말해, x가 0이면 1, 0이 아니면 0이 나오도록 해야한다.

 

해당 문제에 대한 아이디어는 2의 보수 체계에서의 0의 특성에 대하여 생각해보는 것이다. 0과 다른 수를 가르는 결정적인 기준은 뭘까? 0은 자기 자신에 마이너스를 취해도 똑같다. 다른 말로, x == -x인지 판별하면 된다.

 

x == -x를 비트로 어떻게 나타낼 수 있을까? x와 x의 2의 보수에 | 연산을 하면, 0 이외의 수는 0xFFFFFFFF가 나오고, 0은 0x00000000가 나온다. (2의 보수의 원리를 생각해보면 그렇다). 마지막으로, 0 이외의 수는 0이 나와야 하고, 0은 1이 나와야 하므로 일부러 0x01을 더해 오버플로우를 일으킨다면? 0 이외의 수는 0, 0은 0x01이 나온다!

 

6. tmax (2 / 4ops)

int tmax(void) {
  // idea : make 0111 1111 1111 1111 1111 1111 1111 1111
 
  return ~(1 << 31);
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 4

여섯 번째 문제는 tmax로, 2의 보수 체계에서 가장 큰 수를 만든 것이다. 2의 보수 체계에서 가장 큰 수는 0x7FFFFFFF로, MSB를 제외한 모든 수가 1이면 된다. 위의 return을 통해 단번에 이해할 수 있을 것이다. 쉬어가는 코너다.

 

7. negate (2 / 5ops)

int negate(int x) {
  // idea: 2's complement formula
 
  return ~x + 1;
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 5

일곱 번째 문제는 tmax로, 2의 보수 체계에서 음수를 만드는 것이다. 위의 문제들에서 은근히 -x 대신 ~x+1을 써왔는데, 2의 보수를 어떻게 하는지 구글링하고 보면 이게 2의 보수를 구현한 것이라는 것을 알 수 있다. 쉬어가는 코너2.

 

8. fitsBits (6 / 15ops)

int fitsBits(int x, int n) {
  // idea : if x > 0 : (n-1)th ~ 31st bits are 0s. else if x < 0 1s.
  // 31st ~ (n-1)bits are just filling space because of 32-bit extended signs representations.
  // so, check if (x >> n-1) is zero if x >= 0 else one.
  // in short, check (x >> (n-1)) == (x >> 31)
 
  return !((x >> (n + ~0)) ^ (x >> 31));
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 15

여덟 번째 문제는 fitsBits로, x를 n개의 비트로 표현할 수 있으면 1, 아니면 0을 반환하는 함수이다. 쉽게 말해, x = 5, n = 3이면 fitsBits(5, 3)은 0을 반환해야 한다. 왜냐면 5 = 0101이므로, 최소 4개의 비트가 필요하다. (sign bit의 존재를 잊으면 안된다.) 

 

2의 보수체계에서 생각해보자. 어디까지 유효한 정보이고, 어디까지가 필요없는 정보일까? 5의 경우 0101로 충분하지만, 이를 32비트에 꾸겨넣는 과정에서 0x00000101이 되버린다.  -4의 경우 100로 충분하지만 이를 32비트에 꾸겨넣는 과정에서 0xFFFFFFFC가 되어버린다. 결국 앞의 수들은 sign bit의 연장선이라 생각하면 된다.

 

이에 아이디어를 떠올려, MSB(31번째)부터 (n-1)번째 비트까지는 sign bit extension으로 인하여 채워진 자리이므로 실제 MSB와 비교하면 되겠다는 생각이 들었다. 결국, x >> 31과 x >> (n-1)이 같은지 확인하면 되는 문제이다.

 

만약 같다면, 둘 사이에 XOR 연산을 하였을 때 0 이 나올 것이고, 아니라면 XOR 연산을 하였을 때 0이 아닌 다른 것이 나올 것이다(실제 정보가 들어있는 자리까지 shift가 안된 것이다. 여기서 핵심은 x >> (n-1)이 실제 정보가 있는 자리까지 덮을 수 있어야 한다는 것이다. 그래야 모든 bit가 sign bit의 연장선이 되니까.) 여기에 ! 연산자를 취하면 원하는 결과를 얻을 수 있다.

 

9. dividePower2 (7 / 15ops)

/* 
 * dividePower2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: dividePower2(15,1) = 7, dividePower2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int dividePower2(int x, int n) {
    // idea: split into two cases, which x is neg or not neg.
    // if x >= 0, floor(x/2^n) = x >> n
    // if x < 0 : ceil(x/2^n) = floor((x+(2^n)-1)/2^n) = (x + ((1 << n) -1)) >> n
    
    int isNeg;
    int minusOne;
    isNeg = x >> 31; // get 0xFFFFFFFF if x < 0 else 0x0
    minusOne = ~0;
 
    return (x + (isNeg & ((1 << n) + minusOne))) >> n;
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 15

아홉 번째 문제는 dividePower2로, x를 2^n으로 나누었을 때의 값을 계산하는 것이다.

 

right shift( >> )가 2로 나눗셈이므로, n번만큼 right shift하면 될까 생각해봤지만 문제는 x가 음수일 때이다. 주석에서 round toward zero이므로, x가 음수일 때 n번만큼 right shift하면 bias가 1이 생기는 경우가 있는 것이다. (2의 거듭제곱의 2의 보수인 경우)

 

결국 x / 2^n은 x가 음수가 아닐 때 floor(x / 2^n)이고, x가 음수일 때 ceil(x / 2^n)이므로 이를 한 번에 구현해야 했다.

 

ceil(x / 2^n) = floor((x+2^n -1) / 2^n)이므로, x가 음수일 때는 x에 (2^n - 1)을 더해주어야 했다. 이를 구현하기 위해서 x가 음수일 때 sign bit이 1이므로 이를 31번 right shift하여 음수 필터(isNeg)를 만들어 주었다. 이외는 위의 테크닉들을 활용하여 만들어주면 끝.

 

6ops까지 줄이는 것을 보았는데, 어떻게 구현해야 하는지 아직 모르겠다.

 

10. conditional (7 / 16ops)

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  // idea: check if x == 0 and return y or z
 
  int filter;
  // filter : 0xFFFFFFFF if x == 0 else 0x00000000
  filter = ~(!x) + 0x01;
 
  // z should be returned if x == 0xFFFFFFFF
  return (filter & z) | (~filter & y);
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 16

열 번째 문제는 conditional로, return x ? y : z을 비트 연산으로 구현하면 된다.

 

제어문이 없기에 조금 까다로웠으나, 5.bang에서 일부러 오버플로우를 일으키는 방법과 9.dividePower2에서의 필터링 방법을 섞어서 x에 대한 bool을 구현할 수 있었다.

 

먼저, x가 0이면 y가 나와야 하고, x가 0이 아니면 z가 나와야 하므로 이를 먼저 구현하였다. x가 0이면 filter가 0xFFFFFFFF, x가 0이 아니면 filter가 0x0이 나오게 하여야 했다.

 

!x를 취할 경우 x가 0이면 1, 0이 아니면 0이 나오게 한 후, 이를 뒤집고, 5.bang처럼 1을 더하여 filter를 구현하였다. 이에 대한 구체적인 설명은 5.bang을 읽어보면 이해하기 쉬울 것이다.

 

6ops까지 줄이는 것을 보았다. 어떻게 한거지?

 

11. isGreater (10 / 24ops)

/* 
 * isGreater - if x > y  then return 1, else return 0 
 *   Example: isGreater(4,5) = 0, isGreater(5,4) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isGreater(int x, int y) {
  // idea: Check MSB to check if is greater of not.
  // using truth table makes this puzzle easy :)
 
  int alwaysGreater, sameSign;
  alwaysGreater = ~x & y; // if x >=0 and y < 0
  sameSign = ~((x^y) | (x + ~y)); // if x and y have same sign, do x-y-1
 
  return ((alwaysGreater | sameSign) >> 31) & 0x01;
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 24

열한 번째 문제는 isGreater로, return x > y를 비트 연산으로 구현하면 된다.

 

x, y의 조합으로 가능한 경우는 총 4가지이다. 결국 대소관계가 중요하기에, sign bit를 기준으로 경우를 나누자.

 

x >= 0, y >= 0	x-y을 해봐야 안다.	x >= 0, y < 0	항상 true다.
x < 0,  y >= 0	항상 false다.	x < 0, y < 0	x-y을 해봐야 안다.

 

결국, x >=0, y < 0인 경우를 살리고, 나머지 경우는 x-y를 하여서 적용하면 된다.

 

먼저, x>=0, y < 0인 경우 ~x & y 연산을 하면 sign bit이 1, 나머지의 경우 0이 된다. 따라서 이 경우를 살릴 수 있다.

 

이외의 경우는 같은 sign의 경우 x-y를 해봐야 한다. 일단, 같은 sign인 지 판단하기 위해 ~(x ^ y)를 만들었다. 같은 sign일 경우 sign bit이 1, 나머지의 경우 0이 된다. 이후 (x + ~y)를 하였는데, 현재 정수 연산을 하고 있으므로 (x > y)은 (x >= y+1)과 같은 말이다. 7. negate에서 y+1 == ~y이므로, x + ~y를 해서 더 크면 sign bit이 0, 같거나 더 작으면 sign bit이 1이 된다.

 

따라서 이를 합치면 ~(x ^ y) & ~(x + ~y)이 되고, 1.bitOr에서 사용하였던 드 모르간 법칙을 활용하여 연산자를 더 줄이면 ~((x ^ y) | (x + ~y))가 된다.

 

이제 결과를 합치고, sign bit만 뽑아내면 끝.

 

원래는 11ops로 하였는데, 포스팅을 쓰다가 드 모르간 법칙 아이디어가 떠올라 연산자를 하나 더 줄여서 10ops로 작성하였다.

 

12. intLog2 (24 / 90ops)

/*
 * intLog2 - return floor(log base 2 of x), where x > 0
 *   Example: intLog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
int intLog2(int x) {
 
  // Second Idea: Counting Leading Zeros & subtract from 31
  int cnt = 0;
 
  int isZero;
  isZero = !(x >> 16) << 4; // check if 16bit-upper-half is zero
  // isZero = 16 if 0x0000.... else isZero = 0
  cnt = isZero; // accumulate the result
  x = x << isZero; // shift to check is there are more zeros or not
 
  // repeat the process
 
  isZero = !(x >> 24) << 3; // check if 8bit-upper-half is zero
  cnt = cnt + isZero;
  x = x << isZero;
 
  isZero = !(x >> 28) << 2; // check if 4bit-upper-half is zero
  cnt = cnt + isZero;
  x = x << isZero;
 
  isZero = !(x >> 30) << 1; // check if 2bit-upper-half is zero
  cnt = cnt + isZero;
  x = x << isZero;
 
  return 32 + ~(cnt + !(x >> 31)); // 1bit is enough with one ! and subtract from 31
}

 

• 허용 연산자 : ~ & ^ | + << >> !
• 최대 연산 횟수 : 90

열두 번째 문제는 intLog2로, floor(log2(x))를 비트 연산으로 구현하는 것이다.

 

어려운 문제고, 실제로 많은 동기들과 선후배들이 못 푼 문제기도 하다. 일단 아이디어만 떠올릴 수 있으면, 최대 연산 횟수 자체는 넉넉하므로 구현에 초점을 맞추면 된다.

 

먼저 x는 양수이므로, 맨 앞의 sign bit은 0이다. 따라서, 양수가 아닌 수의 예외 처리는 구현하지 않아도 된다.

 

핵심은 x는 결국 이진법으로 이루어진 수라는 것이다. x = 0x7F000000이면, x = 2^31 + 2^30 ...이다. 여기에 log2(x)를 하면? log2(2^31) = 31과 같다. x = 0x00000022이면 x = 2^5 + 2^1이므로 log2(2^5) = 5와 같다. 다른 말로, 결국 가장 큰 지수만 뽑혀 나오는 것과 같다. 이를 비트로 해석하면, 가장 앞의 1의 위치를 찾으면 된다. 구글과 stackoverflow에 돌아다니는 풀이가 이 방법을 사용하는 것 같다.

 

이를 이분 탐색으로 구현하였더니 25ops까지 줄일 수 있었다. 그러나, 이 방법을 비틀어서 생각하였다.

 

가장 앞의 1의 위치를 찾는다는 것은, 그 앞은 모두 0이라는 것이다. 따라서 1의 위치 앞의 0의 개수를 찾는다는 것을 활용한다면, 1의 위치를 찾는것보다 더 줄일 수 있겠다는 생각이 들었다.

 

이를 이분 탐색으로 구현한 것이 위의 코드이다. 주석을 달아두었으니 따라가보면 어떤 논리인지 알 수 있을 것이다. 구현하였더니 24ops까지 줄일 수 있었다.

 

이거보다 최적화된 방법이 있다고는 봤지만(22ops), 어떻게 구현하는지는 알지 못하였다. 겐세이 넣어주세요.

 

13. floatAbsVal (2 / 10ops)

/* 
 * floatAbsVal - Return bit-level equivalent of absolute value of f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument..
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned floatAbsVal(unsigned uf) {
  // idea: just check if is not Nan
  // Nan = 0111 1111 1(0~1~0)(min : 0x7F800000), so |uf| bigger than Nan is Nan
 
  int absolute;
  absolute = uf & 0x7FFFFFFF; // |uf|
 
  if (absolute > 0x7F800000) { // if Nan
    return uf;
  } else { // if not Nan
    return absolute; 
  }
}

 

• 허용 연산자 : int, uint관련 모든 연산자 & 제어문
• 최대 연산 횟수 : 10

열세 번째 문제는 single-precision floating point argument uf의 절댓값을 반환하되, NaN의 경우 argument 그대로 반환하는 것이다.

 

간단하다. NaN이 아니면 sign bit을 0으로 만들어 버려 반환하면 되는 것이다. 문제는 어떻게 NaN을 판별하냐는 것이다.

 

floating point의 NaN의 경우 exponent가 모두 1이고 fraction이 0이 아니면 되니, 만약 uf가 0x7F800000(0 / 1111111 / 0000 .... 0000 = +INF)보다 큰 경우는 모두 NaN이라 생각하면 된다. 따라서 이를 비교하여 적절한 return 값을 만들어 주면 된다. 간단한 문제.

 

14. floatFloat2Int (13 / 30ops)

/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  // idea : parse float to int following the rule of 32-bit floating point representation
 
  int exponent, fraction;
  int compareExp;
  exponent = (uf & 0x7F800000) >> 23;
  fraction = (uf & 0x007FFFFF);
 
  if (exponent > 0x9D) { // if exponent > 157(0x9D) (out of range case), explicitly return 0x80000000;
    return 0x80000000;
  } else if (exponent < 0x7F) { // if exponent < 127(0x7F), return 0.
    return 0;
  } else {
    fraction = fraction | 0x00800000;  // add 1 << 23z
    compareExp = exponent-150;
 
    fraction = ((compareExp > 0) ? fraction << compareExp : fraction >> -compareExp);
 
    return uf < 0x80000000 ? fraction : -fraction; // return according to the sign.
  }
}

 

• 허용 연산자 : int, uint관련 모든 연산자 & 제어문
• 최대 연산 횟수 : 30

열네 번째 문제는 single-precision floating point argument uf을 int로 바꾸어 주는 함수를 만드는 것이다. 다만, INF 혹은 NaN의 경우 0x80000000u를 반환해야 한다.

 

이에 대한 구현은 floating point를 바꾸는 방법 그대로 따라가면 된다. sign, exponent, fraction 분리해서 생각하면 된다. 이에 대한 설명은 부동소수점 개념에서 찾으면 될거 같고, 위의 주석을 따라가면 이해하는데 무리가 없을 거라 생각한다.

 

9ops로 줄인 사람 봤는데, 댓글로 나타나주세요 제발!!

 

15. floatScale2 (6 / 30ops)

/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  // idea: move exponent case by case
  // Fraction part is redundant in this puzzle.
 
  int sign, exponent;
  sign = uf & 0x80000000;
  exponent = uf & 0x7F800000;
 
  if (exponent) { // if exp != 0
    if (exponent != 0x7F800000) { // not Nan case
      uf += 0x00800000; // 
    }
  } else { // denormalized case
    uf = sign | (uf << 1);
  }
 
  // if Nan return uf, else uf*2
  return uf;
}

 

• 허용 연산자 : int, uint관련 모든 연산자 & 제어문
• 최대 연산 횟수 : 30

열다섯 번째 문제는 2*f를 반환하는 것이다. 다만 f가 NaN이면 f 그대로 반환하는 것이다.

 

2를 곱하는 방법에는 두 가지 방법이 있다.

 

1. exponent에 1을 더해준다. (2^x+1 = 2^x * 2이므로)
2. fraction을 left shift 1번 해준다.

 

1번의 경우 denormalized number가 아닐 때 사용할 수 있고, 2번의 경우 denormalized number일 때 사용할 수 있다. 따라서 denormalized number인 경우와 아닌 경우로 나눌 수 있다.

 

denormalzied number의 경우 exponent가 0이므로, 0인 경우와 아닌 경우로 나눌 수 있다. 0이 아닌 경우, NaN을 판별하여줘야 하므로 exponent를 비교해준다. 아니라면 exponent에 1을 더해주면 된다.

---

직접 문제들을 풀고 싶은 독자들은 여기에 들어가서 Data lab을 다운로드 받고, manual 대로 하여 직접 코드를 짜고 채점기로 채점받으면 된다.