Leetcode-190-颠倒的二进制位

Leetcode-190-颠倒二进制位

题目描述

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

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

示例 2：

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

思路：逐位颠倒

• 在面试的时候逐位颠倒作为最直接的解决方案。

• 对于十进制而言(反转)
  • 十进制：ans = ans * 10 + n % 10; n = n / 10;
  • 二进制：ans = ans * 2 + n % 2; n = n / 2;

但是：

• 这种写法会有整型溢出，Java的整数溢出后的二进制数会变成负数（补码的形式），Java中负数除以2会向0取整，参考：https://www.cnblogs.com/zhangziqiu/archive/2011/03/30/ComputerCode.html
• 所以综上所述，要使用位运算来避免溢出问题，同时循环32次。

/**
 * 对于十进制而言
 *  ans = ans * 10 + n % 10 ; n = n /10;
 * 对于二进制而言
 *  ans = ans * 2 + n % 2 ; n = n /2;
 */
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;

        //  * 对于二进制而言
        // *  ans = ans * 2 + n % 2 ; n = n /2;
        for (int i = 0; i < 32; i++) {
            ans = (ans << 1) + (n & 1);
            n >>= 1;
        }

        return ans;
    }
}

时间复杂度：O(logn) 这里32位所以是O(1)

空间复杂度： O(1)

打赏