跳到主要内容

9.2 位运算基础问题

461. Hamming Distance​

题目描述​

给定两个十进制数字，求它们二进制表示的汉明距离（Hamming distance，即不同位的个数）。

输入输出样例​

输入是两个十进制整数，输出是一个十进制整数，表示两个输入数字的汉明距离。

Input: x = 1, y = 4
Output: 2

在这个样例中，1 的二进制是 0001，4 的二进制是 0100，一共有两位不同。

题解​

对两个数进行按位异或操作，统计有多少个 1 即可。

int hammingDistance(int x, int y) {
    int diff = x ^ y, dist = 0;
    while (diff != 0) {
        dist += diff & 1;
        diff >>= 1;
    }
    return dist;
}

190. Reverse Bits​

题目描述​

给定一个十进制正整数，输出它在二进制下的翻转结果。

输入输出样例​

输入和输出都是十进制正整数。

Input: 43261596 (00000010100101000001111010011100)
Output: 964176192 (00111001011110000010100101000000)

使用算术左移和右移，可以很轻易地实现二进制的翻转。

题解​

uint32_t reverseBits(uint32_t n) {
    uint32_t m = 0;
    for (int i = 0; i < 32; ++i) {
        m <<= 1;
        m += n & 1;
        n >>= 1;
    }
    return m;
}

136. Single Number​

题目描述​

给定一个整数数组，这个数组里只有一个数次出现了一次，其余数字出现了两次，求这个只出现一次的数字。

输入输出样例​

输入是一个一维整数数组，输出是该数组内的一个整数。

Input: [4,1,2,1,2]
Output: 4

题解​

我们可以利用 x ∧ x = 0 和 x ∧ 0 = x 的特点，将数组内所有的数字进行按位异或。出现两次的所有数字按位异或的结果是 0，0 与出现一次的数字异或可以得到这个数字本身。

int singleNumber(vector<int>& nums) {
    int single = 0;
    for (int num : nums) {
        single ^= num;
    }
    return single;
}

这里我们也可以直接使用 reduce 函数：

int singleNumber(vector<int>& nums) {
    return reduce(nums.begin(), nums.end(), 0,
                  [](int x, int y) { return x ^ y; });
}