位运算与数学

位运算和数学题在面试中常考但相对简单，掌握常见的位运算技巧和数学规律即可轻松应对。本模块涵盖位1的个数、汉明距离、只出现一次的数字、多数元素等经典题目。理解异或、与、或、移位等基本操作是解题基础。

---

Q1: 位1的个数 「🟢 初级」

题目描述：编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为汉明重量）。

考察点：位运算、n & (n-1) 技巧、移位操作。

解题思路：

• 方法1：逐位检查，右移32次（时间O(1)固定32次，空间O(1)）
• 方法2：n & (n-1) 消除最低位的1，有多少个1就循环多少次（时间O(k)，k为1的个数）- 最优解

代码实现：

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1); // 消除最低位的1
        count++;
    }
    return count;
}

复杂度分析：时间复杂度 O(k)，k为二进制中1的个数，最多32次；空间复杂度 O(1)。

变体扩展：

• 变体1：汉明距离
• 变体2：比特位计数
• 变体3：颠倒二进制位
• 变体4：数字范围按位与

---

Q2: 汉明距离 「🟢 初级」

题目描述：两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

考察点：异或运算、位1的个数。

解题思路：

• 方法：先异或得到不同的位，再统计异或结果中1的个数（时间O(1)，空间O(1)）- 最优解

代码实现：

public int hammingDistance(int x, int y) {
    int xor = x ^ y;
    int count = 0;
    while (xor != 0) {
        xor = xor & (xor - 1);
        count++;
    }
    return count;
}

复杂度分析：时间复杂度 O(1)，最多32次循环；空间复杂度 O(1)。

变体扩展：

• 变体1：位1的个数
• 变体2：汉明距离总和
• 变体3：只出现一次的数字
• 变体4：交换两个数（异或技巧）

---

Q3: 颠倒二进制位 「🟢 初级」

题目描述：颠倒给定的 32 位无符号整数的二进制位。

考察点：位运算、移位操作、分治思想。

解题思路：

• 方法1：逐位反转，取最低位放到结果的高位（时间O(1)固定32次，空间O(1)）- 最优解
• 方法2：分治法，类似归并排序的思路，两两交换、四位交换...

代码实现：

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1); // 把n的最低位放到res的最低位，然后res左移
        n >>>= 1; // 无符号右移
    }
    return res;
}

复杂度分析：时间复杂度 O(1)，固定32次循环；空间复杂度 O(1)。

变体扩展：

• 变体1：位1的个数
• 变体2：整数反转
• 变体3：回文数
• 变体4：数字反转相关问题

---

Q4: 只出现一次的数字 「🟢 初级」

题目描述：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

考察点：异或运算的性质、位运算。

解题思路：

• 方法1：哈希表统计（时间O(n)，空间O(n)）
• 方法2：排序后查找（时间O(nlogn)，空间O(1)）
• 方法3：异或运算，a^a=0，a^0=a，所有数异或结果就是出现一次的数（时间O(n)，空间O(1)）- 最优解

代码实现：

public int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

复杂度分析：时间复杂度 O(n)，遍历一次数组；空间复杂度 O(1)，仅一个变量。

变体扩展：

• 变体1：只出现一次的数字II（其他出现三次）
• 变体2：只出现一次的数字III（两个数各出现一次）
• 变体3：丢失的数字
• 变体4：找不同

---

Q5: 多数元素 「🟢 初级」

题目描述：给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

考察点：摩尔投票法、哈希表、排序、分治。

解题思路：

• 方法1：哈希表统计（时间O(n)，空间O(n)）
• 方法2：排序后取中间元素（时间O(nlogn)，空间O(1)或O(n)）
• 方法3：摩尔投票法，抵消思想（时间O(n)，空间O(1)）- 最优解

代码实现：

public int majorityElement(int[] nums) {
    int candidate = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

复杂度分析：时间复杂度 O(n)，遍历一次数组；空间复杂度 O(1)，仅两个变量。

变体扩展：

• 变体1：求众数II（超过n/3的元素）
• 变体2：数组中出现次数超过一半的数字
• 变体3：主要元素
• 变体4：有序数组中的单一元素

---

Q6: 整数反转 「🟡 中级」

题目描述：给你一个 32 位的有符号整数 x，返回将 x 中的数字部分反转后的结果。如果反转后整数超过 32 位的有符号整数的范围 [−2³¹, 2³¹ − 1]，就返回 0。假设环境不允许存储 64 位整数（有符号或无符号）。

考察点：数学运算、溢出判断、边界处理。

解题思路：

• 方法：逐位取余反转，在溢出前判断（时间O(log|x|)，空间O(1)）- 最优解

代码实现：

public int reverse(int x) {
    int res = 0;
    while (x != 0) {
        int digit = x % 10;
        x /= 10;
        // 溢出判断
        if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && digit > 7)) {
            return 0;
        }
        if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && digit < -8)) {
            return 0;
        }
        res = res * 10 + digit;
    }
    return res;
}

复杂度分析：时间复杂度 O(log|x|)，循环次数为数字位数；空间复杂度 O(1)。

变体扩展：

• 变体1：回文数
• 变体2：字符串转换整数 (atoi)
• 变体3：颠倒二进制位
• 变体4：数字的各位相加