题目分析

位运算的题目难度都不大，但是有一些技巧和陷阱需要小伙伴们在做题中发现，做完这个题目，希望小伙伴们可以去Leetcode官网做面试题05.06进行知识点巩固。

位运算

**负数右移，符号位不变，这是需要小伙伴们注意的，如果我们想让负数右移符号位补0，可以让结果异或0x8000000(1 << 31)，或者让结果与(0x7fffffff)**。

本题中，我们从低位到高位统计连续的1出现的次数，如果某一位是0，则right统计右边1出现的个数，left统计左边1出现的个数。left + right + 1就是将该位改为1时连续的1出现的次数。然后再统计下一位，此时right = 0，left = right。

我写的版本是先找到最先出现的第一个0，统计右边1的个数记为right作为初始条件，然后开始统计left的个数。代码有些冗余，因此在下面提供一个其他人写的版本。

算法的**时间复杂度为$O(1)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<algorithm>

class Solution {
public:
    int reverseBits(int num) {
        int left = 0, right = 0, maxLens = 0;
        while (num && num % 2) {
            right++;
            num >>= 1;
            num = num >= 0 ? num : num ^ (1 << 31);
        }
        num >>= 1;
        num = num >= 0 ? num : num ^ (1 << 31);
        while (num) {
            if (num % 2) {
                left++;
            }
            else {
                maxLens = max(maxLens, left + right + 1);
                right = left;
                left = 0;
            }
            num = num >> 1;
        }
        return min(max(maxLens, left + right + 1), 32);
    }
};

优化位运算

其实并没有优化时间复杂度和空间复杂度，但是美观了我们的代码，让我们的代码可读性大大提高了。

思想是：不管移位以后最高位补的是0还是1，我们只关心int的32位数据，因此使用for循环进行遍历，而且不需要找到第一个0产生的位置，统计右边1的个数赋值给right，将初始值right设0即可。

算法的**时间复杂度为$O(1)$，空间复杂度为$O(1)$**。

#include<iostream>
#include<algorithm>

class Solution {
public:
    int reverseBits(int num) {
        if (~num == 0) return 32;
    
        int previous = 0;
        int current = 0;
        int length = 0;
        for (int i = 0; i < 32; i++) {
            if (num & 1) {
                current++;
            } else {
                previous = current;
                current = 0;
            }
            length = max(length, previous + current + 1);
            num >>= 1;
        }
        return length;
    }
};

刷题总结

位运算是小伙伴们必须掌握的技能，这是我们软件程序员的基本知识，从计算机为什么要用二进制表示，到数值的二进制保存方法，这都是需要我们熟记的。