C++ 位运算从入门到精通（全知识点+面试题+实战应用）

C 位运算从入门到精通全知识点面试题实战应用一、位运算基础概念位运算是直接对二进制位bit进行操作的运算是计算机底层最基础、最高效的运算方式。在嵌入式开发、高性能算法、网络协议、加密解密、面试高频考点中都有极其广泛的应用。C 提供了 6 种基础位运算符所有运算均以二进制补码形式进行不涉及浮点数运算仅针对整数类型char、short、int、long、long long 等生效。1.1 二进制与补码基础计算机中所有整数均以补码形式存储和运算这是因为补码能统一正数和负数的运算规则避免出现“正零”和“负零”的歧义同时简化减法运算减法可转化为加法。核心规则正数原码 反码 补码。例如int 类型的 532位原码、反码、补码均为 00000000 00000000 00000000 00000101。负数反码 原码符号位不变其余各位按位取反补码 反码 1。例如int 类型的 -5原码为 10000000 00000000 00000000 00000101反码为 11111111 11111111 11111111 11111010补码为 11111111 11111111 11111111 11111011。符号位二进制最高位为符号位0 表示正数1 表示负数32位 int 类型的取值范围是 -2³¹ ~ 2³¹ - 1其中 -2³¹ 是唯一无法用原码和反码表示的数只能用补码表示。位运算的核心优势的是效率极高——CPU 执行位运算指令无需复杂的算术运算如乘除、取模直接操作内存中的二进制位速度比普通算术运算快 10~100 倍尤其适合对性能要求极高的场景。1.2 六种基础位运算符重点C 提供 6 种基础位运算符优先级从高到低依次为~按位取反 、移位 按位与 ^按位异或 |按位或。所有运算符均针对二进制补码进行操作具体规则如下| 运算符 | 名称 | 作用 | 运算规则 | 示例x50101y30011 ||--------|------|------|----------|----------------------------||| 按位与 | 对两个数的二进制位逐位进行“与”操作 | 两位均为 1结果为 1否则为 0 | x y 00011 |||| 按位或 | 对两个数的二进制位逐位进行“或”操作 | 任意一位为 1结果为 1否则为 0 | x | y 01117 ||^| 按位异或 | 对两个数的二进制位逐位进行“异或”操作 | 两位相同为 0不同为 1 | x ^ y 01106 ||~| 按位取反 | 对一个数的二进制位逐位取反包括符号位 | 0 变 11 变 0 | ~x 1010补码对应-6 ||| 左移 | 将二进制位整体向左移动 n 位 | 高位丢弃低位补 0 | x 1 101010 ||| 右移 | 将二进制位整体向右移动 n 位 | 正数高位补 0负数高位补 1算术右移 | x 1 00102 |注意事项移位运算中移位的位数不能为负数也不能超出当前数据类型的宽度如 32 位 int 类型移位位数不能 ≥32否则行为未定义不同编译器表现不同。按位取反~是单目运算符对正数取反后结果为负数对负数取反后结果为正数公式~x -x - 1。位运算仅针对整数类型若对浮点数使用位运算编译器会报错需强制转换为整数后再操作。二、六种基础位运算符详解附实战代码2.1 按位与最常用核心性质任何数 0 0清零任何数 自身 自身保留原值按位与具有“掩码”作用可用于提取某几位、判断某一位是否为 1。高频应用场景判断一个整数的奇偶性最经典用法原理整数的二进制最低位为 1 时是奇数为 0 时是偶数。用x 1可快速判断——结果为 1 则是奇数为 0 则是偶数。代码示例#includeiostreamusingnamespacestd;// 判断奇偶性boolisOdd(intx){returnx1;// 等价于 x % 2 1但效率更高}intmain(){coutisOdd(5)endl;// 1奇数coutisOdd(6)endl;// 0偶数return0;}清零二进制中最低位的 1原理x (x - 1)会将 x 二进制中最低位的 1 变为 0其余位保持不变。这是位运算中最核心的技巧之一广泛用于统计 1 的个数、判断 2 的幂等场景。代码示例#includeiostreamusingnamespacestd;// 清零最低位的 1intclearLowestOne(intx){returnx(x-1);}intmain(){intx6;// 二进制 0110coutclearLowestOne(x)endl;// 40100最低位1被清零x5;// 0101coutclearLowestOne(x)endl;// 40100return0;}提取二进制中的特定位原理用一个“掩码”mask与目标数进行按位与掩码中需要保留的位设为 1其余位设为 0即可提取出目标位。示例提取 int 类型 x 的第 3 位从 0 开始计数最低位为第 0 位。代码示例#includeiostreamusingnamespacestd;// 提取第 k 位0-basedintgetKthBit(intx,intk){return(x(1k))!0;// 1k 生成掩码只有第k位为1}intmain(){intx10;// 二进制 1010coutgetKthBit(x,1)endl;// 1第1位是1coutgetKthBit(x,2)endl;// 0第2位是0return0;}2.2 按位或|核心性质任何数 | 0 自身任何数 | 自身 自身按位或可用于“置位”即将某一位强制设为 1其余位保持不变。高频应用场景将二进制中某一位设为 1原理用1 k生成掩码第 k 位为 1与目标数进行按位或即可将第 k 位设为 1其余位不变。代码示例#includeiostreamusingnamespacestd;// 将第 k 位设为 10-basedintsetKthBit(intx,intk){returnx|(1k);}intmain(){intx5;// 0101coutsetKthBit(x,2)endl;// 91001第2位设为1coutsetKthBit(x,3)endl;// 131101第3位设为1return0;}合并多个标志位在实际开发中常用位来表示多个独立的状态标志位用按位或合并多个标志位实现多状态共存。代码示例权限控制#includeiostreamusingnamespacestd;// 定义权限标志位每一位代表一种权限constintREAD10;// 第0位读权限1constintWRITE11;// 第1位写权限2constintEXEC12;// 第2位执行权限4// 合并权限intaddPerm(intperm,intp){returnperm|p;}intmain(){intperm0;// 初始无权限permaddPerm(perm,READ);// 增加读权限001permaddPerm(perm,WRITE);// 增加写权限0113coutpermendl;// 3return0;}2.3 按位异或^最灵活按位异或是位运算中最灵活的运算符核心特性是“相同为 0不同为 1”且满足交换律、结合律具有可逆性。核心性质x ^ x 0任何数与自身异或结果为 0x ^ 0 x任何数与 0 异或结果为自身交换律a ^ b b ^ a结合律(a ^ b) ^ c a ^ (b ^ c)可逆性若 a ^ b c则 a c ^ bb c ^ a。高频应用场景交换两个整数无需临时变量原理利用异或的可逆性无需额外临时变量即可交换两个数的值效率极高是面试中常见的写法。代码示例#includeiostreamusingnamespacestd;// 异或交换两个整数无临时变量voidswap(inta,intb){if(ab)return;// 避免 a b 时异或后变为 0a^b;// a a ^ bb^a;// b b ^ (a ^ b) aa^b;// a (a ^ b) ^ a b}intmain(){inta5,b10;swap(a,b);couta a,b bendl;// a10, b5return0;}注意当 a 和 b 指向同一块内存如 swap(x, x)时会导致 x 变为 0因此需添加 a b 的判断。2. 翻转二进制中的某一位原理用1 k生成掩码与目标数异或——若第 k 位为 0则变为 1若为 1则变为 0实现翻转。代码示例#includeiostreamusingnamespacestd;// 翻转第 k 位0-basedintflipKthBit(intx,intk){returnx^(1k);}intmain(){intx5;// 0101coutflipKthBit(x,0)endl;// 40100第0位翻转coutflipKthBit(x,1)endl;// 70111第1位翻转return0;}找出数组中唯一出现一次的数字题目数组中只有一个数字出现一次其余数字均出现两次找出这个唯一的数字面试高频题。原理利用 x ^ x 0 和 x ^ 0 x 的性质将数组中所有元素异或出现两次的数字会相互抵消结果为 0最终结果就是唯一出现一次的数字。代码示例#includeiostream#includevectorusingnamespacestd;intsingleNumber(vectorintnums){intres0;for(intx:nums){res^x;// 所有元素异或抵消出现两次的数字}returnres;}intmain(){vectorintnums{2,3,2,4,4};coutsingleNumber(nums)endl;// 3唯一出现一次的数字return0;}2.4 按位取反~按位取反是单目运算符对二进制的每一位包括符号位进行取反0 变 11 变 0。由于计算机存储的是补码因此取反后的结果需要结合补码规则解读。核心规律对于整数 x~x -x - 1无论 x 是正数还是负数均成立。示例x 5补码 00000101~x 11111010补码对应十进制 -6满足 -5 -1 -6x -5补码 11111011~x 00000100补码对应十进制 4满足 -(-5) -1 4。应用场景生成全 1 的掩码例如生成 32 位全 1 的掩码用于提取所有位可使用~00 的补码是全 0取反后是全 1。代码示例#includeiostreamusingnamespacestd;intmain(){intmask~0;// 32位全1对应十进制 -1coutmaskendl;// -1// 生成低 k 位全 1 的掩码如 k3掩码为 00000111intk3;intlowMask(1k)-1;// 等价于 ~(~0 k)coutlowMaskendl;// 700000111return0;}快速计算负数的绝对值辅助作用结合取反和加法可快速计算负数的绝对值公式abs(x) ~x 1仅对负数有效。代码示例#includeiostreamusingnamespacestd;intabsNeg(intx){if(x0){return~x1;// 负数取反加1得到绝对值}returnx;}intmain(){coutabsNeg(-5)endl;// 5coutabsNeg(5)endl;// 5return0;}2.5 左移左移运算将二进制位整体向左移动 n 位高位丢弃低位补 0。左移 n 位等价于乘以 2ⁿ前提是不发生溢出效率远高于乘法运算。核心规律x n x * 2ⁿx 为正数且不溢出。示例5 1 105 * 2¹5 2 205 * 2²5 3 405 * 2³。注意事项溢出风险左移可能导致数值超出当前数据类型的取值范围溢出后行为未定义。例如32 位 int 类型的最大值是 21474836470x7FFFFFFF左移 1 位后变为 0xFFFFFFFE对应十进制 -2发生溢出。左移位数不能为负数也不能超出数据类型宽度如 32 位 int 不能左移 ≥32 位。应用场景快速乘法乘以 2 的幂在高性能算法中常用左移替代乘以 2 的幂提升运算速度。代码示例#includeiostreamusingnamespacestd;// 快速乘以 2^nintfastMultiply(intx,intn){returnxn;}intmain(){coutfastMultiply(5,1)endl;// 105*2coutfastMultiply(5,3)endl;// 405*8return0;}生成掩码左移可快速生成“某一位为 1其余位为 0”的掩码用于置位、提取位等操作前面已多次用到。2.6 右移右移运算将二进制位整体向右移动 n 位分为两种类型算术右移主流编译器默认正数高位补 0负数高位补 1保持符号不变逻辑右移无论正数还是负数高位均补 0仅部分编译器支持如 GCC 需加-funsigned-bitfields选项。核心规律x n x / 2ⁿ向下取整适用于正数和负数。示例10 1 510 / 2 5向下取整9 1 49 / 2 4.5向下取整-10 1 -5-10 / 2 -5-9 1 -5-9 / 2 -4.5向下取整为 -5。应用场景快速除法除以 2 的幂与左移对应右移可快速实现除以 2 的幂效率高于除法运算。代码示例#includeiostreamusingnamespacestd;// 快速除以 2^n向下取整intfastDivide(intx,intn){returnxn;}intmain(){coutfastDivide(10,1)endl;// 5coutfastDivide(9,1)endl;// 4coutfastDivide(-9,1)endl;// -5return0;}二进制位遍历通过右移可逐位遍历二进制的每一位用于统计 1 的个数、判断某一位是否为 1 等操作。代码示例遍历二进制每一位#includeiostreamusingnamespacestd;// 遍历 x 的每一位32位voidprintBits(intx){for(inti31;i0;i--){// 右移 i 位提取第 i 位cout((xi)1);if(i%40)cout ;}coutendl;}intmain(){intx10;// 00000000 00000000 00000000 00001010printBits(x);return0;}三、位运算经典技巧面试必备位运算的核心价值在于“高效”和“简洁”以下是面试中高频出现的经典技巧涵盖判断、统计、计算等场景全部附带可直接运行的代码。3.1 判断一个数是否是 2 的幂核心原理2 的幂的二进制只有一个 1如 210、4100、81000因此满足x 0 且 x (x - 1) 0。注意x 必须大于 0因为 0 和负数不是 2 的幂。代码示例#includeiostreamusingnamespacestd;// 判断 x 是否是 2 的幂boolisPowerOfTwo(intx){returnx0(x(x-1))0;}intmain(){coutisPowerOfTwo(8)endl;// 1是coutisPowerOfTwo(6)endl;// 0不是coutisPowerOfTwo(0)endl;// 0不是coutisPowerOfTwo(-4)endl;// 0不是return0;}3.2 统计二进制中 1 的个数汉明重量方法一循环清零最低位 1最优解原理利用 x (x - 1) 清零最低位的 1每执行一次计数器加 1直到 x 变为 0计数器的值就是 1 的个数。代码示例#includeiostreamusingnamespacestd;// 统计 x 二进制中 1 的个数intcountOneBits(intx){intcnt0;while(x){xx-1;// 清零最低位的 1cnt;}returncnt;}intmain(){coutcountOneBits(5)endl;// 20101coutcountOneBits(7)endl;// 30111coutcountOneBits(-1)endl;// 3232位全1return0;}方法二逐位遍历兼容所有场景原理通过右移逐位判断每一位是否为 1适合对负数也需要统计所有位包括符号位的场景。代码示例#includeiostreamusingnamespacestd;intcountOneBits(intx){intcnt0;for(inti0;i32;i){if((xi)1){cnt;}}returncnt;}intmain(){coutcountOneBits(5)endl;// 2coutcountOneBits(-1)endl;// 32return0;}3.3 获取二进制中最低位的 1树状数组核心核心原理x -x利用补码特性可快速获取最低位的 1 所在的位置返回值是“只有最低位 1”的数。示例x 60110-x 11111010补码x -x 00102x 50101-x 11111011补码x -x 00011x 81000-x 11111000补码x -x 10008。代码示例#includeiostreamusingnamespacestd;// 获取最低位的 1intlowBit(intx){returnx-x;}intmain(){coutlowBit(6)endl;// 2coutlowBit(5)endl;// 1coutlowBit(8)endl;// 8return0;}应用场景lowBit 是树状数组Fenwick Tree的核心操作用于快速更新和查询前缀和在算法竞赛中广泛应用。3.4 反转二进制位面试高频题题目将一个 32 位无符号整数的二进制位反转例如输入 00000010100101000001111010011100输出 00111001011110000010100101000000。核心思路逐位提取原数的每一位依次放到结果的对应位置通过左移和或运算拼接结果。代码示例#includeiostreamusingnamespacestd;// 反转 32 位无符号整数的二进制位unsignedintreverseBits(unsignedintx){unsignedintres0;for(inti0;i32;i){res(res1)|(x1);// 提取x的最低位放到res的最低位x1;// x右移处理下一位}returnres;}intmain(){unsignedintx0b00000010100101000001111010011100;coutreverseBits(x)endl;// 输出 0b00111001011110000010100101000000 对应的十进制return0;}