1. 进制转换基础与实战技巧
1.1 二进制与十进制的相互转换
二进制转十进制是计算机科学中最基础的技能之一。让我们从一个实际案例开始:假设我们有一个二进制数1101,如何快速计算出它的十进制值?
计算过程详解:
- 从右到左,每一位的权重依次是2^0, 2^1, 2^2, 2^3...
- 具体计算:
- 最右边第0位:1 × 2^0 = 1
- 第1位:0 × 2^1 = 0
- 第2位:1 × 2^2 = 4
- 第3位:1 × 2^3 = 8
- 总和:8 + 4 + 0 + 1 = 13
十进制转二进制的实用方法:
对于十进制数1206,我们可以使用"除2取余法":
- 1206 ÷ 2 = 603 余 0
- 603 ÷ 2 = 301 余 1
- 301 ÷ 2 = 150 余 1
- 150 ÷ 2 = 75 余 0
- 75 ÷ 2 = 37 余 1
- 37 ÷ 2 = 18 余 1
- 18 ÷ 2 = 9 余 0
- 9 ÷ 2 = 4 余 1
- 4 ÷ 2 = 2 余 0
- 2 ÷ 2 = 1 余 0
- 1 ÷ 2 = 0 余 1
将余数从下往上排列:10010110110
提示:对于大数转换,可以分段计算。比如先转换高8位,再转换低8位,最后合并结果。
1.2 八进制与十六进制的转换技巧
二进制转八进制的黄金法则:
- 从右向左,每3位二进制为一组
- 不足3位时在左边补0
- 将每组转换为对应的八进制数字
示例:二进制10110111
- 分组:010 110 111(最左边补一个0)
- 转换:2 6 7
- 结果:八进制267
十六进制转换的特别注意事项:
- A-F分别对应10-15
- 前缀0x表示十六进制数
- 每4位二进制对应1位十六进制
示例:二进制110101101
- 分组:0001 1010 1101(左边补三个0)
- 转换:1 A D
- 结果:十六进制0x1AD
实用技巧:
- 记忆常用十六进制与二进制的对应关系:
- 0x0: 0000
- 0xF: 1111
- 0xA: 1010
- 0x5: 0101
1.3 原码、反码和补码的深入理解
三种编码的关系对比:
| 编码类型 | 正数表示 | 负数表示 | 特点 |
|---|---|---|---|
| 原码 | 符号位+绝对值 | 符号位+绝对值 | 最直观,但加减运算复杂 |
| 反码 | 与原码相同 | 符号位不变,其他位取反 | 解决了加减问题,但有±0 |
| 补码 | 与原码相同 | 反码+1 | 解决了±0问题,统一加减运算 |
补码的实际意义:
- 计算机中使用补码存储整数
- 补码使得加法和减法可以使用同一套电路实现
- 补码表示的范围比原码多一个负数(-128在8位补码中可表示)
示例:-10的编码转换
- 原码:10000000 00000000 00000000 00001010
- 反码:11111111 11111111 11111111 11110101
- 补码:11111111 11111111 11111111 11110110
重要提示:进行位运算时,操作的都是补码形式。计算结果也需要从补码转换回原码才能得到真实值。
2. 位运算操作符的全面解析
2.1 移位操作符的底层原理
左移操作符(<<)的详细分析:
- 语法:num << n
- 效果:将num的二进制表示向左移动n位,右边补0
- 数学意义:相当于乘以2^n
- 边界情况:移动位数超过类型宽度时行为未定义
右移操作符(>>)的两种实现:
- 逻辑右移:左边补0,右边丢弃
- 算术右移:左边补符号位,右边丢弃
- 大多数编译器使用算术右移
- 正数右移相当于除以2^n并向下取整
实际案例对比:
cpp复制int a = -10;
// 原码: 100...1010
// 补码: 111...0110
int b = a >> 1; // 算术右移结果: 111...1011 (即-5)
int c = a << 1; // 左移结果: 111...1100 (即-20)
警告:不要移动负数位,这是未定义行为。例如num >> -1会导致不可预测的结果。
2.2 按位操作符的实战应用
按位与(&)的典型用途:
- 清零特定位:x & ~(1 << n)
- 判断奇偶:x & 1
- 取指定位:x & mask
按位或(|)的常见场景:
- 设置特定位:x | (1 << n)
- 合并标志位:flags | new_flags
按位异或(^)的巧妙用法:
- 交换变量:a ^= b; b ^= a; a ^= b;
- 加密解密:data ^ key
- 找不同:在一组相同数字中找出唯一的那个
按位取反(~)的注意事项:
- 结果是所有位取反
- 对于有符号整数,相当于-(x+1)
- 常用于创建掩码
综合示例:
cpp复制unsigned char flags = 0x00; // 00000000
flags |= 0x01; // 设置第0位: 00000001
flags |= 0x80; // 设置第7位: 10000001
flags &= ~0x01; // 清除第0位: 10000000
flags ^= 0x80; // 切换第7位: 00000000
2.3 位运算的性能优势
与算术运算的对比:
| 操作 | 算术运算 | 位运算 | 性能提升 |
|---|---|---|---|
| 乘以2 | x * 2 | x << 1 | 2-5倍 |
| 除以2 | x / 2 | x >> 1 | 3-10倍 |
| 取模2 | x % 2 | x & 1 | 5-20倍 |
实际应用场景:
- 嵌入式系统开发
- 图形处理
- 加密算法
- 网络协议处理
- 内存管理
经验分享:在现代CPU上,简单的位运算通常只需要1个时钟周期,而对应的算术运算可能需要多个周期。但在实际开发中,应先保证代码可读性,只在性能关键路径使用位运算优化。
3. 位运算的高级应用技巧
3.1 高效算法实现
统计二进制中1的个数:
cpp复制int countBits(int x) {
int count = 0;
while (x) {
x &= x - 1; // 清除最低位的1
count++;
}
return count;
}
判断是否是2的幂:
cpp复制bool isPowerOfTwo(int x) {
return x > 0 && (x & (x - 1)) == 0;
}
获取最低位的1:
cpp复制int lowestBit(int x) {
return x & -x;
}
3.2 位掩码的高级用法
多标志位管理:
cpp复制#define FLAG_A 0x01
#define FLAG_B 0x02
#define FLAG_C 0x04
unsigned char flags = 0;
// 设置标志位
flags |= FLAG_A | FLAG_C;
// 检查标志位
if (flags & FLAG_B) {
// FLAG_B被设置
}
// 清除标志位
flags &= ~FLAG_A;
紧凑数据存储:
cpp复制// 将4个4位数打包成一个16位整数
unsigned short pack(unsigned char a, unsigned char b, unsigned char c, unsigned char d) {
return (a << 12) | (b << 8) | (c << 4) | d;
}
// 解包
void unpack(unsigned short packed, unsigned char &a, unsigned char &b, unsigned char &c, unsigned char &d) {
a = (packed >> 12) & 0xF;
b = (packed >> 8) & 0xF;
c = (packed >> 4) & 0xF;
d = packed & 0xF;
}
3.3 位运算在算法题中的应用
只出现一次的数字(LeetCode 136):
cpp复制int singleNumber(vector<int>& nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
丢失的数字(LeetCode 268):
cpp复制int missingNumber(vector<int>& nums) {
int result = nums.size();
for (int i = 0; i < nums.size(); ++i) {
result ^= i ^ nums[i];
}
return result;
}
颠倒二进制位(LeetCode 190):
cpp复制uint32_t reverseBits(uint32_t n) {
uint32_t result = 0;
for (int i = 0; i < 32; ++i) {
result = (result << 1) | (n & 1);
n >>= 1;
}
return result;
}
4. 实战经验与常见问题
4.1 位运算的常见陷阱
符号扩展问题:
cpp复制int x = 0x80000000; // 最小负数
unsigned int y = x >> 1; // 算术右移,结果0xC0000000
unsigned int z = (unsigned int)x >> 1; // 逻辑右移,结果0x40000000
移位溢出问题:
cpp复制uint32_t x = 1 << 31; // 正确
uint32_t y = 1 << 32; // 未定义行为!
类型提升问题:
cpp复制uint8_t a = 0xFF;
uint8_t b = 0x01;
uint8_t c = a + b; // 可能溢出
uint8_t d = a & b; // 安全
4.2 性能优化建议
- 缓存局部性:频繁访问的位域应该放在同一个字节或字中
- 指令级并行:无依赖的位操作可以并行执行
- 避免分支:用位运算替代条件判断
- 利用硬件特性:某些CPU有专门的位操作指令
4.3 调试技巧
- 打印二进制:
cpp复制void printBinary(int x) {
for (int i = 31; i >= 0; --i) {
cout << ((x >> i) & 1);
if (i % 4 == 0) cout << " ";
}
cout << endl;
}
- 单元测试:为关键位操作函数编写全面的测试用例
- 静态分析:使用工具检查潜在的位操作问题
4.4 跨平台注意事项
- 移位操作的行为可能因编译器而异
- 位字段的内存布局与字节序相关
- 不同平台的基本类型大小可能不同
- 嵌入式系统可能对未对齐的位访问有限制
在实际开发中,我经常使用位运算来优化性能关键代码。例如,在一个图像处理项目中,通过使用位运算替代算术运算,我们将关键算法的速度提升了近3倍。但也要注意,过度使用位运算会降低代码可读性,应该在注释中充分说明位操作的目的和原理。