풀이에 들어가기에 앞서, data lab에 관련된 설명을 먼저 드리겠습니다.

Data lab은 주어진 문제(c코드로 제시된 문제)를 제한된 연산자와 개수로 올바른 답을 도출해내는 과제입니다.

여기서, 연산자는 주로 비트 연산자, 논리연산자로 주어지며 특별한 경우를 제외하고는

for, while, if와 같은 제어문을 사용할 수 없습니다.

저 또한 학습 중에 있으니, 풀이가 최선은 아님을 먼저 말씀드리고 시작하겠습니다.

#1. bitNor

/*
 * bitNor - ~(x|y) using only ~ and &
 *   Example: bitNor(0x6, 0x5) = 0xFFFFFFF8
 *   Legal ops: ~ &
 *   Max ops: 8
 *   Rating: 1
 */
int bitNor(int x, int y) {
  return 2;
}

코드는 위와 같습니다. ~(x|y)를 not 연산자와 and 연산자만을 이용해 표현해야 합니다.

최대 사용 가능한 연산자의 개수는 8개입니다.

여기서, not과 and을 보고 드모르간 법칙을 생각할 수 있습니다.

드모르간 법칙

~(x and y) = ~x or ~y
~(x or y) = ~x and ~y

따라서, 정답 코드는 아래와 같이 작성할 수 있겠네요.

// 1번 풀이

int bitNor(int x, int y) {
  return (~x) & (~y);
}

#2. allEvenBits

/*
 * allEvenBits - return 1 if all even-numbered bits in word set to 1
 *   Examples allEvenBits(0xFFFFFFFE) = 0, allEvenBits(0x55555555) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allEvenBits(int x) {
  return 2;
}

코드는 위와 같습니다. 모든 짝수 자리에 위치한 비트가 1이면 1을 반환합니다.

주어진 연산자는 논리부정(!), not(~), and(&), xor(^), or(|), add(+), shift left(<<), shift right(>>)입니다.

사용가능한 최대 연산자의 개수는 12개네요.

주어지는 숫자는 총 32비트입니다. 만약, 모든 짝수 비트를 일일이 검사한다고 생각하면 16개의 비트를 검사해야하는데,

사용가능한 최대 연산자 개수를 초과할 것입니다.

제가 생각해 낸 방법은 숫자를 반으로 접어 겹쳐놓는 방법입니다.

주어진 숫자 x는 총 32비트의 숫자이고, x와 x>>16을 겹쳐놓는다면

x의 하위 16비트와 상위 16비트를 겹치는 효과를 기대해 볼 수 있습니다.

이를 계속 반복한다면, 겹쳐진 홀수 비트 + 짝수 비트가 남을 것입니다.

겹쳐지는 숫자가 1인지 아닌지만 검사하면 됩니다.

여기서 and연산을 취한다고 하면, 적어도 하나의 짝수 비트에 0이 있는 경우 연산의 최종 결과로 나오는 수의 짝수비트는 0일 것입니다.

이를 이용해서 정답 코드를 작성해보겠습니다.

// 2번 풀이


int allEvenBits(int x) {
  x = x & (x >> 16);
  x = x & (x >> 8);
  x = x & (x >> 4);
  x = x & (x >> 2);
  return x & 0x01;
}
// 연산 과정에서 상위 비트들은 여전히 존재할 것이므로
// 이를 걷어내기 위해 0x01과 and연산을 취합니다.