53 - 颠倒二进制位

题目

颠倒给定的 32 位无符号整数的二进制位。

示例 1：

输入: 00000010100101000001111010011100 输出: 00111001011110000010100101000000 解释: 输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：11111111111111111111111111111101 输出：10111111111111111111111111111111 解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，因此返回 3221225471 其二进制表示形式为 10101111110010110010011101101001。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。

• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

进阶: 如果多次调用这个函数，你将如何优化你的算法？

解答

输入一串数字，就是要反转一下再还回去

按位

就从末位，一个个拿出来，从头到尾放到另一个数字里面

作者：archieCode

链接：https://leetcode-cn.com/problems/two-sum/solution/goshi-xian-by-archiecode/

func reverseBits(num uint32) uint32 {
    var ans uint32 = 0
    t := 32
    for t > 0 {
        ans <<= 1
        ans |= num & 1
        num >>= 1
        t--
    }
    return ans
}

Runtime: 4 ms, faster than 18.22% of Go online submissions for Reverse Bits.

Memory Usage: 2.3 MB, less than 75.00% of Go online submissions forReverse Bits.

这个大佬的解法有些难以理解。。

运算符

• <<，左移n位就是乘以2的n次方。就是把其左边的运算数的 二进制位全部左移若干位，由<<右边的数指定移动的位数。移动后高位丢弃，低位补0。 第五行的意思是，把ans全体左移一位，ans = ans << 1，给即将来的数留位置。

• 第六行，相当于ans = ans | (num & 1)。 |是让参与运算的两数 各自对应的二进位 相或。只有当两位都是1，才出0。

  &则是相与，& 的目的就是把值为0的位给清除掉，因为只有当两个位都是1的时候才会出1，其他都是0 据他说，这段的意思是取出num的最后一位，并放到ans的开头。其实不太理解为什么能做到。
• >>是右移，相当于num = num >> 1。

作者：sh1tge

链接：https://leetcode-cn.com/problems/two-sum/solution/javajie-fa-by-sh1tge/

根据这个大佬的说法：

• &1是为了取有效位

• |=是为了将结果和运算结合

看了位1的个数和mdn，大概能理解了

• ans<<=1，是让ans左移一位，最左的抛弃，最右新增的为0

• ans |= num &1，这分两步

  • num & 1是把num的最右边的一位取出来。因为&的操作，是两边都为1则返回1，不然返回0。而1在32位无符号二进制，是在最后/最右一位是1，其他是0。也就是说，num &1是在取num最末位。

  • |=的操作，是把取出来的数，放到ans 的最右边那位上面。因为|是两边只要一个为1，就返回1，不然返回0。而经过左移，ans最右已经是0，只要num &1返回1，就是1。也就是把最后一位贴上去。

• num>>=1，是把num右移一位，因为最右一位已经移动到ans的最右了，就直接抛弃了。

理解了之后，这个go的代码也能再优化一下：

func reverseBits(num uint32) uint32 {
    var ans uint32 = 0
    for i := 0; i < 32; i++ {
        ans <<= 1
        ans |= num & 1
        num >>= 1
        runtime.Gosched()
    }
    return ans
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forReverse Bits.

Memory Usage: 2.3 MB, less than 75.00% of Go online submissions forReverse Bits.

本来是想，t 的计数自在循环里面用，不应该定义在外面。。似乎对内存的占用并不大，没啥变化。

速度倒是快了很多，怕是go对for循环有特殊的优化吧。

js不知道为啥就是不行。。对数字处理的精度堪忧啊。。

image-20190817133051904

转字符串再转回来

作者：mrandmrsbenben 链接：https://leetcode-cn.com/problems/two-sum/solution/go-shi-xian-by-mrandmrsbenben/

func reverseBits(num uint32) uint32 {
    str := strconv.FormatUint(uint64(num), 2)
    rev := ""
    for i := len(str) - 1; i >= 0; i-- {
        rev = rev + str[i:i+1]
    }
    if len(rev) < 32 {
        rev = rev + strings.Repeat("0", 32-len(rev))
    }
    n, _ := strconv.ParseUint(rev, 2, 64)
    return uint32(n)
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forReverse Bits.

Memory Usage: 2.6 MB, less than 25.00% of Go online submissions forReverse Bits.

这速度，怎么感觉leetcode检验代码崩掉了。。

• strconv.FormatUint()把int64的数字转换成了字符串。转不了int32，因此还得先转一下int64

• 然后一个个元素拿出来贴一下。其实这个写法可以写成这样：

  ...
  for _, elem := range str {
    rev = string(elem) + rev
    runtime.Gosched()
  }
  ...

  这是从前往后贴，就避免了str[i:i+1]的麻烦，直接就用elem给取字母了。

  Runtime: 4 ms, faster than 18.22% of Go online submissions for Reverse Bits.

  Memory Usage: 2.6 MB, less than 25.00% of Go online submissions forReverse Bits.

• strings.Repeat()是用来填充字符串的，在rev后面填充32-len(rev) 个0，来补位

• 最后strconv.ParseUint()把string转成int64，再转回来int32

https://leetcode.com/problems/reverse-bits/discuss/131774/JS-submissions-which-beats-98

var reverseBits = function (n) {
  var origin = [];
  var tip = 0;
  sum = 0
  while (n !== 0) {
    origin.push(n % 2);
    n = parseInt(n / 2);
  }
  var diff = 32 - origin.length;
  if (diff > 0) {
    for (var m = 0; m < diff; m++) {
      origin.push(0);
    }
  }
  for (var i = origin.length - 1; i >= 0; i--) {
    sum += origin[i] * Math.pow(2, tip);
    tip++;
  }
  return sum;
};

Runtime: 64 ms, faster than 87.30% of JavaScript online submissions for Reverse Bits.

Memory Usage: 36.7 MB, less than 16.67% of JavaScript online submissions for Reverse Bits.

• 第7行的parseInt()相当于Math.floor()，感觉学到了一手，能少打不少字。。

• 一开始是一个个放进origin的数组里面，然后再用0补全，再用算法加回来

  不知道js里面有没有go类似的方法，可以直接调函数