位运算-LeetCode 191、190、7、338、461

位运算：LeetCode #191 190 7 338 461

1

编程题

【LeetCode #191】位 1 的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

示例 1： 输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        int tmp = 32;
        while(tmp){
            if(n & (1 << (tmp-1)))
                res++;
            tmp--;
        }
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-of-1-bits

【LeetCode #190】颠倒二进制位

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

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

解题思路：

首先需要通过位与运算循环遍历32个位数字，获得1所在的位数，然后通过与1 << （32-bits）进行位或运算，得到最后的结果即可！

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        int bits = 32;
        int res = 0;
        while(bits){
            if(n & (1 << (bits-1))){
                res |= (1 << (32-bits));
            }
            bits--;
        }
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-bits

【LeetCode #7】整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出: -321

解题思路：

利用求商与取余的方法，可以不用管整数的符号对数字进行反转，但需要注意本题如果数据溢出后，结果为零！

class Solution {
public:
    int reverse(int x) {
        long res = 0;
        int MAX = 0x7fffffff, MIN = 0x80000000;
        while(x != 0){
            res = res * 10 + (x % 10);
            x /= 10;
        }
        res = (res > MAX || res < MIN) ? 0 : (int)res;
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-integer

【LeetCode #338】比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1: 输入: 2 输出: [0,1,1]

解题思路：

i & (i-1)表示某一个数 i 将最后一个为 1 的位数变成 0，也就是011 ---> 010, 即3 ---> 2. 因此本题中，0的个数为0，得到一个递推式： res[i] = res[i & (i-1)] + 1;

class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> res(num+1, 0);
        for(int i = 1; i <= num; i++){
            res[i] = res[i & (i-1)] + 1;
        }
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/counting-bits

【LeetCode #461】汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。 给出两个整数 x 和 y，计算它们之间的汉明距离。

注意： 0 ≤ x, y < 231. 输入: x = 1, y = 4 输出: 2

解释: 1 (0 0 0 1) 4 (0 1 0 0)

上面的箭头指出了对应二进制位不同的位置。

解题思路：

对于汉明距离，统计的是两个数的二进制相应位置的不同数字的个数，如011和101的汉明距离为2。 因此，首先计算a和b的异或，然后统计1出现的个数。

class Solution {
public:
    int hammingDistance(int x, int y) {
        int z = x ^ y;
        int res = 0;
        while(z){
            res += z & 1;
            z = z >> 1;
        }
        return res;
    }
};

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/hamming-distance