二进制相关

algorithm

翻转二进制位

• 翻转二进制位
• 题目大意：给定一个数，其二进制表示为32位，需要按照中心，进行旋转。举例说明，n=11111111111111111111111111111101，翻转后的结果为:n=10111111111111111111111111111111
• 简单的方法把二进制形式求解出来，放在数组里，翻转数组，再依据数组构建出翻转后的数。我们也可以在求解二进制每一位的时候，把翻转后的数字构建出来。
• 结题思路类似于，求解整数十进制的每一个位，然后反过来构建整数。这里获取十进制每一位数字的方式是n%10,n/10这种方式。

 uint32_t reverseBits(uint32_t n) {
        if (n == 0)
            return n;
        const int N  = 32;
        uint32_t r = 0,i,j=0;
        while(n) {
            i = n&1; // 获取最后一位数字，0，1 类似n%2
            r <<= 1; // 左移扩大
            r |= i;// 类似十进制的 r += i
            j++;
            n>>=1;// 右移，除以2，倒数第二位变成倒数第一位
        }
        return r << (N-j);// 剩下的位数左移
}

优化方法

• redis里有个位数计算的数据结构，使用的是全移位来实现交换翻转二进制位数

 uint32_t reverseBits(uint32_t n) {
        n = (n >> 16) | (n << 16); // 交换低16位和高16位
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8);// 交换低8位和高8位
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4);// 交换低4位和高4位
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2);// 交换低2位和高2位
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1);// 交换低1位和高1位
        return n;
    }

备注

• 十进制获取每一位的方法

int reverse(int n){
    while(n) {
        x = n %10;
        n/=10;
    }
}

翻转十进制位数

• 翻转十进制位数
• 题目大意：给定一个整数，范围在$[-2^{31},2^{31}-1]$，翻转其十进制表示。如果出现溢出，返回0。举例，n=120,返回，r=21，n=-2147483648,r=0,n=-2147483612,r=0
• 需要注意的地方在溢出判断，

int reverse(int x) {
        if(x == INT_MIN) // 最小值特殊case
            return 0;
        int a = abs(x);
        int z = 0;
        while(a) {
            if(overflow(z)) // 溢出判断
                return 0;
            z *=10;
            z += a%10;
            a /=10;
        }
        return x >0 ? z:-z;
}
// 溢出判断
int overflow(int z) {
    return z > INT_MAX/10 ||(z == INT_MAX/10 && a%10 > INT_MAX%10) // 溢出判断

• 溢出判断中，z需要乘以10，并且要加上a%10，所以，如果z > INT_MAX/10，必然会溢出。
• 如果z == INT_MAX/10 &&那么乘以10不会溢出，但是还需要判断加上后面的数是否会溢出也就是 加的数是否会大于最大值的最后一位。a%10 > INT_MAX%10)