• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

leetcode190-颠倒二进制位

互联网 diligentman 41分钟前 4次浏览

问题描述:

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

示例 1:

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

示例 2:

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

提示:

请注意,在某些语言(如 Java)中,没有无符号整数类型。在这种情况下,输入和输出都将被指定为有符号整数类型,并且不应影响您的实现,因为无论整数是有符号的还是无符号的,其内部的二进制表示形式都是相同的。
在 Java 中,编译器使用二进制补码记法来表示有符号整数。因此,在上面的 示例 2 中,输入表示有符号整数 -3,输出表示有符号整数 -1073741825。

解题思路:

1、对二进制数进行翻转,类似于整数翻转,需要先获得二进制数的末位。可以通过与运算实现(n & 1)。
&运算满足两个同为1,结果才为1,否则为0,这里和1作与运算,最后得到的结果与n的末位相同。

2、获取末位值后,需要获得倒数第二位数值,这里通过移位即可实现:n>>1,使倒数第二位移至末位。我们只需位移 32 次,就能获得 n 的所有二进制位值。

3.使用 res对各个二进制位进行保存。

实现代码

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res=0;      //用res保存n的各个二进制位
        for(int i=0;i<32;i++){
            //这里让res先左移的原因是因为从最后一个位开始,每个位左移32-i位,则第1位左移31次,所以res左移放在最前面
            res=res<<1;      
            //如果当前n的末位是1,那么res++,保证左移完后,res的该位也为1
            if((n & 1)==1){
                res++;
            }
            //n右移,得到n的倒数第i位
            n=n>>1;
        }
        return res;
    }
}

注意点:

Java中没有无符号数,只有有符号数,有符号数的移位是算术移位
算术移位的对象是有符号数,在移位过程中符号位保持不变。
对于正数,移位后出现的空位均以0填充。
对于负数,负数的原码数值部分与真值相同,移位时符号位不变,空位添0
负数的反码各位除符号位外与负数的原码正好相反,故移位后所添的代码应该与原码相反,全部添1
所以,Java中负数右移得到的结果仍然是负数。
这里如果颠倒二进制位从高位向低位填充时,可能会出现错误。
如题主一开始写的代码


喜欢 (0)