Leet Code - 190. Reverse Bits(C++)

예제: Reverse Bits

문제
Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

• Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

풀이

주어진 숫자의 bit를 반전시켜 출력하는 예제이다.

음.. 필자의 로직을 설명하자면, 한마디로 말하면 주어진 숫자의 i번째 bit를 비교해가며 (31 - i)번째 bit에 넣어줘 출력한 것이다.

CASE1번과 CASE2번의 로직은 완전히 같은데, CASE1은 i가 넘어갈 때마다 일일이 비교해야 하지만, CASE2번은 변수 하나에 저장해두고 2를 곱해주어 바로바로 비교할 수 있다는 차이가 있다. 물론 속도도 차이가 있다.

전체적인 소스코드는 아래와 같다.

소스 코드

/* CASE1 */
class Solution {
public:
	uint32_t reverseBits(uint32_t n) {
		uint32_t res = 0;

		for (int i = 0; i <= 31; i++) {
			uint32_t num = (n & (1 << i));

			int shift = 31 - 2 * i;
			if (shift >= 0) {
				num = (num << shift);
			}
			else {
				num = (num >> -shift);
			}

			res += num;
		}

		return res;
	}
};

/* CASE2 */
class Solution {
public:
	uint32_t reverseBits(uint32_t n) {
		uint32_t res = 0;
		uint32_t mul = 1;

		for (int i = 0; i <= 15; i++) {
			res += ((n & mul) << (31 - 2 * i));
			mul *= 2;
		}

		for (int i = 16; i <= 31; i++) {
			res += ((n & mul) >> (2 * i - 31));
			mul *= 2;
		}

		return res;
	}
};

풀이 후기

비트연산은 잘만 쓰면 정말 빠른 것 같다.
다만 1과 0뿐이다 보니 문득문득 논리연산처럼 true/false로 생각할 때가 있다. 주의하자.