(LeetCode) 190. Reverse Bits

190. Reverse Bits

• Explore : Interview > Top Interveiw Questions > Easy Collection
• 분류 : Others
• 난이도 : Easy

Problem

Reverse bits of a given 32 bits unsigned integer.

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 a signed integer type. They should not affect your implementation, as the integer’s internal binary representation 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.

Follow up:

If this function is called many times, how would you optimize it?

Example 1

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

Example 2

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

Constraints

• 0 <= x, y <= 2^31 - 1

Solution 1

Exapnder

class Solution {
    // you need treat n as an unsigned value
    fun reverseBits(n:Int):Int {
        var result = 0
        var number = n
        for (index in 0 until Int.SIZE_BITS) {
            result = result shl 1
            if ((number and 1) == 1) {
                result++
            }
            number = number shr 1
        }
        return result
    }
}

Solution 2

Exapnder

class Solution {
    // you need treat n as an unsigned value
    fun reverseBits(n:Int):Int = Integer.reverse(n)
}

Point of Thinking

• 주어진 n이 Int이므로 32만큼 순회하면서, 비트연산을 반복한다.
• 결과값은 좌측으로 시프트, 주어진 n은 우측으로 시프트하면서 n의 비트가 1이면 결과값에 1씩 더하면서 뒤집어 주면 Accepted.
• Integer.reverse()라는 필살기도 있다.

// Integer#reverse()
public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}