Viiisit [LeetCode] - 190. Reverse Bits

keep learning, keep coding!

Problem - Reverse Bits

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.

翻譯蒟蒻

將給定整數的二進制表示中的位元順序完全反轉。

---

• 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.

---

Solution - JavaScript

Solution 1 (wrong):

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    // 將 ans 左移一位，然後加上 n 的最低位元
    ans = (ans << 1) + (n & 1); 
    // 將 n 右移一位，丟棄已經處理過的最低位元
    n = n >> 1; 
  }

  return ans; 
};

在 JavaScript 中的位元運算符對於無符號整數和有符號整數的處理方式不同。在 JavaScript 中，所有的整數都是以 64 位雙精度浮點數（double-precision floating-point）的形式存儲的。當使用位元運算符時，JavaScript 會將整數隱式轉換為 32 位有符號整數進行操作，在對無符號整數進行位元反轉時，可能會產生負數的情況。而在 JavaScript 中，對於右移運算符（>>）來說，如果操作的是一個負數，則會在左邊填充 1，這會導致結果不正確。

修正如下：

Solution 1 (correct):

var reverseBits = function(n) {
  let ans = 0;
  for (let i = 0; i < 32; i++) {
    ans = (ans << 1) + (n & 1);
    n = n >>> 1; // 使用無符號右移運算符
  }
  return ans >>> 0; // 返回無符號整數
};

Solution 2:

/**
 * @param {number} n - a positive integer
 * @return {number} - a positive integer
 */
var reverseBits = function(n) {
  let binary = n.toString(2);
  while (binary.length < 32) {
    binary = '0' + binary;
  }
  let reversed = binary.split('').reverse().join('');
  return parseInt(reversed, 2);
};

Solution - Ruby

def reverse_bits(n)
  n.to_s(2).rjust(32, '0').reverse.to_i(2)
end

Ruby 方法筆記

• rjust 函數用於將當前字符串右對齊並返回一個新的字符串（是 String 類別的一個方法）；如果新字符串的長度大於原字符串的長度，則會在左側填充指定的字符（默認為空格）。

  函數的基本語法如下：

  str.rjust(integer, padstr=' ')

"hello".rjust(10)         # => "     hello"
"hello".rjust(10, '123')  # => "12312hello"

Solution - PHP

function reverseBits($n) {
  $ans = 0;
  for ($i = 0; $i < 32; $i++) {
    $ans = ($ans << 1) | ($n & 1);
    $n >>= 1;
  }
  return $ans;
}

在 PHP 中，位元運算符（>> 和 <<）會自動地處理無符號整數。表示即使操作的是無符號整數，也不會在左邊填充 1。因此，不需要像在 JavaScript 中一樣使用無符號右移運算符（>>>）。

LeetCode 傳送門 - Reverse Bits