营销型网站建站公司,网络工程师是青春饭吗,wordpress允许作者上传媒体,ui设计软件官网文章目录
须知 #x1f4ac; 欢迎讨论#xff1a;如果你在学习过程中有任何问题或想法#xff0c;欢迎在评论区留言#xff0c;我们一起交流学习。你的支持是我继续创作的动力#xff01; #x1f44d; 点赞、收藏与分享#xff1a;觉得这篇文章对你有帮助吗#xff1…文章目录
须知 欢迎讨论如果你在学习过程中有任何问题或想法欢迎在评论区留言我们一起交流学习。你的支持是我继续创作的动力 点赞、收藏与分享觉得这篇文章对你有帮助吗别忘了点赞、收藏并分享给更多的小伙伴哦你们的支持是我不断进步的动力 分享给更多人如果你觉得这篇文章对你有帮助欢迎分享给更多对C算法感兴趣的朋友让我们一起进步 1. C 位运算算法 详解
1.1 位运算的重要性
位运算Bitwise Operation是计算机底层操作的核心。它的重要性体现在以下几个方面
高效性位运算直接操作二进制位速度极快是最高效的运算方式之一。底层控制用于硬件控制、网络协议、图像处理等领域帮助开发者操作底层数据。空间优化在数据压缩、哈希算法等场景中通过位操作极大节省存储空间。算法核心许多高效算法依赖位运算实现比如快速幂、判断奇偶、位图等。 1.2 位运算的定义
位运算是对整数在二进制位层面进行操作的运算主要包括以下基本操作 按位与 规则两个二进制位都为 1 时结果为 1否则为 0。应用常用于掩码操作保留某些位的信息。 示例1101 1011 1001 按位或| 规则只要有一个二进制位为 1结果为 1否则为 0。应用设置某些位为 1。 示例1101 | 1011 1111 按位异或^ 规则二进制位相同为 0不同为 1。应用交换值、检测位差。 示例1101 ^ 1011 0110 按位取反~ 规则将每个位取反即 1 变 00 变 1。应用构造补码。 示例~1101 0010假设为4位操作 左移 规则将所有位向左移动指定位置右边补 0。应用高效计算乘以 2^n。 示例1101 2 110100 右移 规则将所有位向右移动指定位置。 算术右移高位用符号位填充保留符号。逻辑右移高位用 0 填充。应用高效计算除以 2^n。 示例1101 2 0011 1.3 位运算的核心思想
二进制数据的直接操作将复杂的逻辑转换为简单的二进制运算。高效替代算术操作使用移位、与或操作完成加减乘除或逻辑控制。灵活的位级处理针对数据的某些特定位进行精确控制和修改。组合运用通过多种位运算的结合构造高效的算法。 1.4 经典应用 快速判断奇偶数 思路通过按位与操作 n 1 判断奇偶。 示例5 1 1奇数4 1 0偶数 交换两个数不使用额外变量 a a ^ b b a ^ b a a ^ b 示例a 5, b 7 - a 7, b 5 清零最低位的 1 公式n (n - 1)作用用于统计 1 的个数。 示例12 (1100) - n (n - 1) 8 (1000) 判断二进制中是否为 2 的幂 公式n 0 and (n (n - 1)) 0 示例8 (1000) 是 2 的幂10 (1010) 不是。 位图Bitmap算法 应用于海量数据处理用位表示某个值是否存在大幅节省空间。 示例检测某个数字是否出现。 位掩码Bitmask操作 用于权限管理如读写执行权限每个位表示一个权限状态。 示例111 表示 rwx 权限101 表示 rw-。 图像处理中的像素操作 按位与、或操作对图像的颜色、透明度等位级数据进行精细控制。 加法的位运算实现 利用异或操作模拟加法a ^ b不进位加法和 a b进位。 哈希函数优化 通过位运算快速计算哈希值或减少冲突。 网络编程中的子网掩码
使用按位与确定 IP 地址和子网的关系。 位运算的基础简单但应用广泛掌握它不仅能提升代码效率还能帮助开发者深入理解计算机的工作原理。 2. 题目1位1的个数
题目链接191. 位1的个数 - 力扣LeetCode
题目描述 2.1 算法思路 算法核心思想 逐位检查 利用右移操作将 n 的最低位逐步移出然后与 1 按位与操作来检查这一位是否为 1。如果结果是 1说明当前位是 1计数器 count 增加 1。 循环 32 次 因为输入是一个 32 位整数int需要从最低位到最高位依次检查所有 32 位。 返回计数器 每次遇到 1 时计数器增加最终返回这个计数值。 2.2 代码详解
class Solution
{
public:int hammingWeight(int n) {int count 0; // 初始化计数器统计 1 的个数for (int i 0; i 32; i) // 遍历 32 位{if (((n i) 1) 1) // 右移 i 位后与 1 按位与判断最低位是否为 1count; // 如果是 1增加计数}return count; // 返回汉明重量}
};2.2.1 示例分析
输入n 11
二进制表示00000000000000000000000000001011 逐步过程如下
i 0: (n 0) 1 000...0011 1 1 - count 1i 1: (n 1) 1 000...001 1 1 - count 2i 2: (n 2) 1 000...000 1 0 - count 2i 3: (n 3) 1 000...000 1 1 - count 3 最终结果count 3 2.3 时间复杂度与空间复杂度 时间复杂度 循环固定执行 32 次因为是 32 位整数。每次循环中执行常数操作右移和按位与。总时间复杂度为 O(1)与输入值大小无关。 空间复杂度 只使用了一个额外变量 count因此是 O(1)。 2.4 改进优化
虽然代码的时间复杂度已经是 O(1)但在某些场景下可以进一步优化位操作的效率例如使用 n (n - 1) 清零最低位的 1。 优化后的代码
class Solution
{
public:int hammingWeight(int n) {int count 0;while (n ! 0) // 当 n 不为 0 时逐位清零最低位的 1{n (n - 1); // 清零最低位的 1count;}return count;}
};2.4.1 优化思路
每次操作将当前数字的最低位 1 清零使得循环次数仅等于 1 的个数。时间复杂度O(k)其中 k 是 1 的个数适用于输入值中 1 的个数远小于 32 的情况。 2.5 总结
原始方法适合简单直接的逐位统计适合入门和通用情况。优化方法更高效尤其在实际应用中适用于稀疏数据1 的个数较少的场景。
3. 题目2:比特位计数
题目链接338. 比特位计数 - 力扣LeetCode
题目描述 3.1 算法思路 辅助函数 hammingWeight 的功能 作用输入一个整数 n计算其二进制中 1 的个数。思路通过循环逐位检查 n 的每一位是否为 1如果是则计数器增加。实现细节 使用右移运算符 将数字逐位右移。与 1 进行按位与运算检查最低位是否为 1。循环 32 次针对 32 位整数。 主函数 countBits 的功能 作用从 0 到 n依次调用 hammingWeight 计算每个数字中 1 的个数并将结果存入数组 arr。思路 遍历所有数字 i范围是 [0, n]。对每个数字 i 调用 hammingWeight获取其二进制中 1 的个数。使用 arr.push_back(count) 将结果依次存入数组。 整体流程 初始化数组 arr 用于存储结果。循环从 0 到 n计算每个数字的 1 个数。返回结果数组 arr。 3.2 示例代码
// 定义一个辅助函数用于计算一个整数的二进制中 1 的个数
int hammingWeight(int n)
{int count 0; // 初始化计数器用于统计二进制中 1 的数量for (int i 0; i 32; i) // 遍历整数的 32 位假设输入是 32 位整数{// 右移 i 位并用按位与操作提取最低位检查是否为 1if (((n i) 1) 1) count; // 如果当前位是 1计数器加 1}return count; // 返回 1 的总个数
}// 定义一个类包含主函数用于生成从 0 到 n 每个数字的二进制中 1 的个数
class Solution
{
public:// 主函数生成结果数组vectorint countBits(int n) {vectorint arr; // 定义一个向量用于存储结果每个元素代表对应数字的二进制中 1 的个数int count1 0; // 临时变量用于存储每个数字的 1 个数// 遍历从 0 到 n 的每个数字for (int i 0; i n; i) {count1 hammingWeight(i); // 调用辅助函数计算当前数字的 1 个数arr.push_back(count1); // 将结果添加到结果数组中}return arr; // 返回结果数组}
};3.2.1 代码详解
辅助函数 hammingWeight
int hammingWeight(int n)
{int count 0;for (int i 0; i 32; i) // 遍历整数的 32 位{if (((n i) 1) 1) // 检查当前位是否为 1count; // 如果是增加计数}return count; // 返回 1 的个数
}主函数 countBits
class Solution
{
public:vectorint countBits(int n) {vectorint arr; // 用于存储每个数字的汉明重量int count1 0;for (int i 0; i n; i) // 遍历从 0 到 n 的每个数字{count1 hammingWeight(i); // 计算当前数字的二进制中 1 的个数arr.push_back(count1); // 将结果加入数组}return arr; // 返回结果数组}
};示例分析 示例输入n 5
目标生成从 0 到 5 的二进制中 1 的个数即
0 - 0000 → 1 的个数 01 - 0001 → 1 的个数 12 - 0010 → 1 的个数 13 - 0011 → 1 的个数 24 - 0100 → 1 的个数 15 - 0101 → 1 的个数 2
输出[0, 1, 1, 2, 1, 2]
逐步过程
i 0 → 调用 hammingWeight(0) → 结果 0 → arr [0]i 1 → 调用 hammingWeight(1) → 结果 1 → arr [0, 1]i 2 → 调用 hammingWeight(2) → 结果 1 → arr [0, 1, 1]i 3 → 调用 hammingWeight(3) → 结果 2 → arr [0, 1, 1, 2]i 4 → 调用 hammingWeight(4) → 结果 1 → arr [0, 1, 1, 2, 1]i 5 → 调用 hammingWeight(5) → 结果 2 → arr [0, 1, 1, 2, 1, 2]
最终返回 arr [0, 1, 1, 2, 1, 2]。 3.3 时间复杂度与空间复杂度
时间复杂度
主函数从 0 到 n 遍历了 n 1 个数字。辅助函数每次调用 hammingWeight 执行了 32 次操作检查 32 位。总体复杂度O(n * 32)即 O(32n)等价于 O(n)。
空间复杂度
存储结果数组 arr大小为 n 1。总空间复杂度为 O(n)。 3.4 优化思路
当前实现中每次计算每个数字的汉明重量时完全独立地逐位检查。可以通过 动态规划 优化利用前一个数字的结果推导当前数字的汉明重量。优化方法为
观察规律 如果 i 是偶数则 countBits(i) countBits(i / 2)右移一位相当于去掉最低位。如果 i 是奇数则 countBits(i) countBits(i / 2) 1最低位为 1。动态规划实现
class Solution
{
public:vectorint countBits(int n) {vectorint dp(n 1, 0); // 初始化结果数组dp[i] 表示数字 i 的汉明重量for (int i 1; i n; i) {dp[i] dp[i 1] (i 1); // 动态转移方程}return dp;}
};优化复杂度时间复杂度降为 O(n)空间复杂度仍为 O(n)。 3.5 总结
初始实现通过逐位计算每个数字的汉明重量简单直观时间复杂度为 O(n * 32)。动态规划优化利用子问题结果减少重复计算时间复杂度降为 O(n)。
4. 题目3汉明距离
题目链接461. 汉明距离 - 力扣LeetCode
题目描述 4.1 算法思路
算法分为两部分 辅助函数 hammingWeight 计算一个整数的二进制表示中 1 的个数即汉明重量Hamming Weight。通过逐位右移和按位与操作统计 1 的个数。 主函数 hammingDistance 计算两个整数 x 和 y 的汉明距离。使用按位异或^操作找出 x 和 y 的二进制表示中不同的位结果是一个新整数 s。调用 hammingWeight 函数统计 s 中的 1 的个数即为汉明距离。 4.2 示例代码
// 辅助函数计算整数 n 的二进制表示中 1 的个数
int hammingWeight(int n)
{int count 0; // 初始化计数器用于统计二进制中 1 的数量for (int i 0; i 32; i) // 遍历 32 位假设输入为 32 位整数{// 右移 i 位并与 1 进行按位与操作检查最低位是否为 1if (((n i) 1) 1) count; // 如果最低位为 1则计数器加 1}return count; // 返回二进制中 1 的总数
}// 主类用于计算两个整数的汉明距离
class Solution
{
public:// 主函数计算 x 和 y 的汉明距离int hammingDistance(int x, int y) {// 按位异或操作得到二进制中 x 和 y 不同的位// 异或规则相同位结果为 0不同位结果为 1int s x ^ y;// 调用辅助函数 hammingWeight统计异或结果中 1 的个数// 这些 1 的数量即为 x 和 y 的汉明距离return hammingWeight(s);}
};4.2.1 代码逻辑详细解析 辅助函数 hammingWeight 功能统计整数 n 的二进制表示中 1 的个数。方法通过逐位右移操作依次提取最低位并判断是否为 1。 n i将整数 n 右移 i 位。(n i) 1提取右移后结果的最低位并判断是否为 1。时间复杂度固定遍历 32 位时间复杂度为 O(32)即 O(1)。 主函数 hammingDistance 功能计算两个整数 x 和 y 的汉明距离。方法 通过按位异或x ^ y操作生成一个新的整数 s其二进制表示中 1 的位置对应 x 和 y 不同的位。 异或规则 1 ^ 1 0 0 ^ 0 0 1 ^ 0 1 0 ^ 1 1 因此s 的二进制中所有的 1 表示 x 和 y 不同的位。调用 hammingWeight 函数统计 s 中 1 的个数作为 x 和 y 的汉明距离。时间复杂度 异或操作时间复杂度为 O(1)。调用 hammingWeight 时间复杂度为 O(32)即 O(1)。 示例运行过程
示例输入 x 1, y 4 计算过程 x 的二进制表示0001y 的二进制表示0100 按位异或 x ^ y 0001 ^ 0100 0101 异或结果为0101。 调用 hammingWeight(5) 5 的二进制表示为0101。遍历每一位 第 0 位1 → count 1第 1 位0 → count 1第 2 位1 → count 2第 3 位0 → count 2返回 count 2。 最终返回汉明距离2
输出 2 4.3 时间复杂度和空间复杂度
时间复杂度
异或操作按位异或操作的时间复杂度为 O(1)。辅助函数 hammingWeight遍历 32 位时间复杂度为 O(1)。总时间复杂度O(1)。
空间复杂度
使用常量级的变量如 count 和 s不需要额外空间O(1)。 4.4 代码特点 优点 简单直观通过辅助函数分离逻辑代码结构清晰。时间复杂度和空间复杂度均为常量级性能优良。 可优化方向 优化 hammingWeight 函数利用 n (n - 1) 方法快速清除最低位的 1减少迭代次数
优化后的辅助函数
int hammingWeight(int n)
{int count 0;while (n ! 0) // 当 n 不为 0 时{n (n - 1); // 清除最低位的 1count; // 每次清除后计数加 1}return count; // 返回二进制中 1 的总数
}优势循环次数等于 1 的个数适用于二进制中 1 较少的情况进一步提升性能。 完整优化代码
int hammingWeight(int n)
{int count 0;while (n ! 0) {n (n - 1);count;}return count;
}class Solution
{
public:int hammingDistance(int x, int y) {int s x ^ y; // 按位异或找出 x 和 y 不同的位return hammingWeight(s); // 统计不同位的数量即 1 的个数}
};5. 题目4只出现1的次数
题目链接136. 只出现一次的数字 - 力扣LeetCode
题目描述 5.1 算法思路 异或运算的特性 异或^运算的规则 a ^ a 0任何数与自己异或结果为 0a ^ 0 a任何数与 0 异或结果不变异或满足交换律和结合律a ^ b ^ c a ^ c ^ b。因此如果一个数出现两次它们会相互抵消为 0。只出现一次的数与 0 异或后仍是其本身。 核心逻辑 遍历数组中的每个元素对每个元素执行 异或操作。最终所有出现两次的数字会抵消为 0只剩下那个出现一次的数字。
5.2 示例代码
class Solution
{
public:int singleNumber(vectorint nums) {int ret 0; // 初始化结果为 0for (auto s : nums) // 遍历数组中的每个元素{ret ^ s; // 异或操作逐个元素与结果异或}return ret; // 返回出现一次的数字}
};5.2.1 执行过程示例
输入示例
nums [4, 1, 2, 1, 2]
执行过程 最终结果4
5.3 时间复杂度与空间复杂度 时间复杂度 遍历整个数组一次每个元素进行一次异或操作。时间复杂度为 O(n)其中 n 是数组的长度。 空间复杂度 使用了一个整数 ret 进行累加异或不需要额外的数据结构。空间复杂度为 O(1)。 5.4 多种解法
5.4.1 解法二哈希表法
思路
使用 哈希表 记录每个元素出现的次数。遍历哈希表找到次数为1的元素。 代码实现 class Solution {
public:int singleNumber(vectorint nums) {unordered_mapint, int countMap;for (int num : nums) {countMap[num]; // 记录每个元素出现的次数}for (auto pair : countMap) {if (pair.second 1) { // 找到只出现一次的元素return pair.first;}}return -1; // 兜底返回}
};时间复杂度O(n) — 遍历数组和哈希表
空间复杂度O(n) — 额外使用哈希表存储元素及其频次 5.4.2 解法三排序法
思路
对数组进行排序相同的元素会相邻。遍历排序后的数组如果某个元素与前一个和后一个元素不同它就是只出现一次的数。 代码实现 class Solution {
public:int singleNumber(vectorint nums) {sort(nums.begin(), nums.end()); // 排序数组for (int i 0; i nums.size(); i 2) { // 每次跳两个位置if (i nums.size() - 1 || nums[i] ! nums[i 1]) { return nums[i]; // 如果元素和下一个元素不同返回该元素}}return -1; // 兜底返回}
};时间复杂度O(n log n) — 排序的时间复杂度
空间复杂度O(1) — 如果排序算法为原地排序 5.4.3 解法四数学法2∗sum - sum
思路
利用集合Set去重后计算数组中元素的和。原始数组中所有元素之和减去去重后的和的两倍结果就是只出现一次的数。 代码实现 class Solution {
public:int singleNumber(vectorint nums) {unordered_setint numSet;int sumOfNums 0, sumOfSet 0;for (int num : nums) {sumOfNums num; // 数组中所有元素的和if (numSet.find(num) numSet.end()) { // 如果元素不在集合中numSet.insert(num);sumOfSet num; // 记录集合中元素的和}}return 2 * sumOfSet - sumOfNums; // 根据公式计算结果}
};时间复杂度O(n) — 遍历数组
空间复杂度O(n) — 额外使用集合 5.4.4 解法对比总结 5.5 总结
关键点利用异或的特性重复出现的数字会被抵消a ^ a 0最终只剩下不重复的那个数。优势 时间复杂度为 O(n)一次遍历解决问题。空间复杂度为 O(1)无需额外存储空间。适用场景数组中有且只有一个数字出现一次其余数字均出现两次 6. 题目5只出现一次的数字 |||
题目链接260. 只出现一次的数字 III - 力扣LeetCode
题目描述 6.1 算法思路 思路解析 步骤1使用异或找出两个数字的异或结果
将数组中所有数字进行异或最终结果 xorsum 是这两个不同数字的异或结果。 原因 相同的数字异或为 0a ^ a 0。0 与任何数异或不改变数值a ^ 0 a。因此数组中成对的数字会相互抵消只剩下两个不同的数字的异或结果。xorsum 的特点 它是两个只出现一次的数字的 异或值即 xorsum num1 ^ num2其中 num1 和 num2 是结果。
步骤2找到异或结果中最低的不同位区分两组数字 异或结果 xorsum 中的 最低位的1表示在这一位上两个不同数字的二进制表示不同一个是 1另一个是 0。 通过 xorsum (-xorsum) 找出最低的1位 (-xorsum) 是 xorsum 的 补码补码中保留最低位的1并将其他位取反。xorsum (-xorsum) 可以快速找到最低位的1。 这位 lsblowest significant bit可以将数组中的所有数字分为两组 第一组在该位上为 1 的数字。第二组在该位上为 0 的数字。
步骤3分别异或两组数字得到两个结果
将数组中的所有数字根据最低位的1进行分组。对每一组的数字分别进行异或 在第一组中所有成对的数字出现两次的数字会互相抵消最终结果是 num1。在第二组中所有成对的数字也会互相抵消最终结果是 num2。 6.2 代码解析
class Solution {
public:vectorint singleNumber(vectorint nums) {int xorsum 0; // 用于存储所有数字的异或结果for (int num: nums) {xorsum ^ num; // 所有数字异或最终结果是两个不同数字的异或值}// 找出 xorsum 中最低位的 1用于区分两个数字// 如果 xorsum 是 INT_MIN最小负数它本身只有最高位为 1不会溢出int lsb (xorsum INT_MIN ? xorsum : xorsum (-xorsum));int type1 0, type2 0; // 用于存储两个只出现一次的数字for (int num: nums) {if (num lsb) { // 根据最低位的1分组该位为1type1 ^ num; // 第一组异或得到 num1}else { // 该位为0type2 ^ num; // 第二组异或得到 num2}}return {type1, type2}; // 返回结果}
};6.2.1 示例执行过程
输入
nums [1, 2, 1, 3, 2, 5]
步骤1计算所有元素的异或结果
1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 3 ^ 5 6二进制 01106 是 3 和 5 的异或结果。
步骤2找到最低位的1
xorsum 6 → 二进制 0110xorsum (-xorsum) 2最低位的1在第2位。
步骤3根据最低位的1分组
分组1第2位为1的数字2, 2, 3分组2第2位为0的数字1, 1, 5
步骤4分别异或两组
第一组2 ^ 2 ^ 3 3第二组1 ^ 1 ^ 5 5
输出
[3, 5]结果顺序不唯一。 6.3 复杂度分析
时间复杂度分析 第一次遍历计算所有数字的异或时间复杂度为 O(n)。 第二次遍历根据最低位的1分组并分别异或时间复杂度为 O(n)。 总体时间复杂度O(n)。
空间复杂度分析
使用了常数额外空间空间复杂度为 O(1)。 6.4 多种解法思路
6.4.1 解法二哈希表法
思路
使用哈希表记录每个元素的出现次数。遍历哈希表找到出现次数为1的两个元素。 代码实现 class Solution {
public:vectorint singleNumber(vectorint nums) {unordered_mapint, int freq; // 统计元素出现的频率for (int num : nums) {freq[num];}vectorint result;for (auto pair : freq) {if (pair.second 1) { // 出现次数为1的元素result.push_back(pair.first);}}return result;}
};复杂度分析
时间复杂度O(n)一次遍历数组和哈希表。空间复杂度O(n)额外的哈希表空间。 6.4.2 解法三排序法
思路
对数组进行排序相同的元素会相邻。遍历排序后的数组如果某个元素与前后元素都不相同则它是目标元素之一。
代码实现
class Solution {
public:vectorint singleNumber(vectorint nums) {sort(nums.begin(), nums.end()); // 排序数组vectorint result;for (int i 0; i nums.size(); i) {if ((i 0 || nums[i] ! nums[i - 1]) (i nums.size() - 1 || nums[i] ! nums[i 1])) {result.push_back(nums[i]);}}return result;}
};复杂度分析
时间复杂度O(n log n)排序的时间复杂度。空间复杂度O(1)原地排序如果排序算法是原地的 6.4.3 解法对比总结 6.5 总结
异或法是解决此类问题的核心思想利用异或的性质实现高效解法。通过 最低位的1 将两个不同的数字区分开来巧妙地将问题分解为两组。该解法时间复杂度为 O(n)空间复杂度为 O(1)性能最优。 7. 总结要点
异或运算 是位运算解决重复出现问题的核心思想 相同为00与任何数异或等于数本身。位统计 取模通过逐位统计 1 的个数可以解决 K次出现问题。低位的1通过提取最低位的1可以将数字分组解决两个目标数字的问题。
8. 最后 通过上面几个例题「Single Number」的异或运算解法、「Single Number III」的异或分组方法以及**「Single Number II」的位统计与取模优化**我们总结出位运算在数组问题中的高效应用。 位运算 通过将复杂的数字出现次数、分组、去重等问题转化为简单的位级操作如异或、位统计、取模等极大地提升了问题求解的效率。 在处理 元素重复出现问题、分组求解问题 以及 高效数值处理 等场景时位运算展现出显著的性能优势尤其适用于 大规模数据 和 时间复杂度敏感 的应用场景。 路虽远行则将至事虽难做则必成 亲爱的读者们下一篇文章再会
