C/C++位操作实战：从基础到高级技巧

1. 位操作基础与实战技巧

在C/C++底层编程中，位操作是最基础也是最重要的技能之一。通过直接操作数据的二进制表示，我们可以实现高效的计算和精巧的逻辑控制。下面我将结合多年开发经验，深入解析几个经典的位操作问题。

1.1 异或运算的位级实现

异或运算（XOR）是位操作中最常用的运算之一，标准运算符是^。但如果我们被限制只能使用&和~，该如何实现呢？

c复制int bitXor(int x, int y) {
  return ~(~(x & ~y) & ~(~x & y));
}

这个实现基于布尔代数中的德摩根定律：

1. 首先计算x & ~y（x为1且y为0的位）
2. 然后计算~x & y（x为0且y为1的位）
3. 将这两个结果取反后相与，再整体取反

提示：理解这个实现的关键在于记住德摩根定律：A | B = ~(~A & ~B)。通过这一定律，我们可以将OR操作转换为AND和NOT的组合。

1.2 最小整数的位表示

在32位补码表示中，最小整数是0x80000000。这个值的获取可以通过简单的位移操作实现：

c复制int tmin(void) {
  return 1 << 31;
}

这里有几个关键点需要注意：

• 位移操作在不同语言中的行为可能不同
• C/C++中，对有符号整数的右移是算术右移（保留符号位）
• 在Java等语言中，>>是算术右移，>>>是逻辑右移

1.3 判断最大整数的技巧

判断一个数是否是最大整数（0x7FFFFFFF）需要一些技巧：

c复制int isTmax(int x) {
  int plus_one = x + 1;
  int sum = x + plus_one;
  int is_neg_one = !(~sum);
  int not_neg_one = !!plus_one;
  return is_neg_one & not_neg_one;
}

这个实现的精妙之处在于：

1. 如果x是Tmax，那么x+1就是Tmin（0x80000000）
2. x + (x+1) 应该等于-1（所有位都是1）
3. 同时需要排除x=-1的情况，因为-1 + 0 = -1

2. 位掩码的高级应用

2.1 检查奇数位是否全为1

这个问题的核心是构造一个合适的掩码：

c复制int allOddBits(int x) {
  int mask = 0xAA;
  mask = mask | (mask << 8);
  mask = mask | (mask << 16);
  return !((x & mask) ^ mask);
}

这里有几个值得注意的技巧：

1. 由于不能直接使用大常数，需要逐步构造0xAAAAAAAA
2. 先构造0xAA，然后扩展到0xAAAA，再到0xAAAAAAAA
3. 最后通过异或运算检查x的奇数位是否全为1

2.2 取反操作的位级实现

在补码系统中，取反操作可以通过位运算实现：

c复制int negate(int x) {
  return ~x + 1;
}

这个实现基于补码的定义：

• 一个数的补码是其反码加1
• 因此，-x = ~x + 1
• 这也是计算机中表示负数的方式

经验分享：这个简单的操作在实际开发中非常有用，特别是在需要频繁进行符号转换的场景，比如图像处理中的像素值反转。

3. 条件判断与逻辑运算

3.1 ASCII数字判断

判断一个数是否在ASCII数字范围内（'0'-'9'）需要一些技巧：

c复制int isAsciiDigit(int x) {
  int lower_bound = x + (~0x30 + 1);
  int is_ge_lower = !(lower_bound >> 31);
  int upper_bound = 0x39 + (~x + 1);
  int is_le_upper = !(upper_bound >> 31);
  return is_ge_lower & is_le_upper;
}

这个实现的关键点：

1. 计算x - 0x30并检查是否为非负
2. 计算0x39 - x并检查是否为非负
3. 通过符号位来判断比较结果

3.2 条件选择运算

实现类似三元运算符的功能：

c复制int conditional(int x, int y, int z) {
  int mask = !!x;
  mask = ~mask + 1;
  return (mask & y) | (~mask & z);
}

这个实现展示了位运算的强大之处：

1. 首先将x转换为布尔值（0或1）
2. 然后通过~mask + 1将其扩展为全0或全1的掩码
3. 最后根据掩码选择y或z

4. 比较运算与逻辑否定

4.1 小于等于判断

实现x <= y的判断需要考虑符号位：

c复制int isLessOrEqual(int x, int y) {
  int x_sign = (x >> 31) & 1;
  int y_sign = (y >> 31) & 1;
  int same_sign = !(x_sign ^ y_sign);
  int diff = y + (~x + 1);
  int diff_sign = (diff >> 31) & 1;
  int ge_zero = !diff_sign;
  int diff_sign_result = x_sign & !y_sign;
  return (same_sign & ge_zero) | (!same_sign & diff_sign_result);
}

这个实现处理了多种情况：

1. 同号情况下，直接比较差值
2. 异号情况下，只需比较符号位
3. 特别注意整数溢出的情况

4.2 逻辑否定运算

实现!运算符的功能：

c复制int logicalNeg(int x) {
  int neg_x = ~x + 1;
  int combined = x | neg_x;
  int sign_bit = (combined >> 31) & 1;
  return sign_bit ^ 1;
}

这个实现利用了0的特殊性质：

• 只有0的相反数仍然是0
• 其他数的相反数与原数相或，符号位必定为1

5. 位计数与浮点数操作

5.1 计算需要的位数

计算表示一个数所需的最少位数：

c复制int howManyBits(int x) {
  int sign, n, bits, hi16, hi8, hi4, hi2, hi1;
  sign = x >> 31;
  n = (sign & ~x) | (~sign & x);
  bits = 0;
  hi16 = !!(n >> 16);
  bits = bits + (hi16 << 4);
  n = n >> (hi16 << 4);
  hi8 = !!(n >> 8);
  bits = bits + (hi8 << 3);
  n = n >> (hi8 << 3);
  hi4 = !!(n >> 4);
  bits = bits + (hi4 << 2);
  n = n >> (hi4 << 2);
  hi2 = !!(n >> 2);
  bits = bits + (hi2 << 1);
  n = n >> (hi2 << 1);
  hi1 = !!(n >> 1);
  bits = bits + hi1;
  n = n >> hi1;
  return bits + n + 1;
}

这个实现采用了二分查找的思想：

1. 首先处理符号位，负数需要找到最高位的0
2. 然后通过二分法逐步缩小范围
3. 最后加上符号位

5.2 浮点数乘以2

实现浮点数乘以2的操作：

c复制unsigned floatScale2(unsigned uf) {
  unsigned sign = uf & 0x80000000;
  unsigned exp = (uf >> 23) & 0xFF;
  unsigned frac = uf & 0x7FFFFF;
  if (exp == 0xFF) {
    return uf;
  }
  if (exp > 0) {
    exp = exp + 1;
    if (exp == 0xFF) {
      return sign | 0x7F800000;
    }
    return sign | (exp << 23) | frac;
  }
  frac = frac << 1;
  if (frac & 0x800000) {
    exp = 1;
    frac = frac & 0x7FFFFF;
  }
  return sign | (exp << 23) | frac;
}

这个实现需要考虑三种情况：

1. 特殊值（NaN或无穷大）保持不变
2. 规格化数通过增加指数实现
3. 非规格化数通过左移尾数实现

5.3 浮点数转整数

将浮点数转换为整数：

c复制int floatFloat2Int(unsigned uf) {
  int sign = (uf >> 31) & 1;
  int exp = (uf >> 23) & 0xFF;
  int frac = uf & 0x7FFFFF;
  int E = exp - 127;
  int mantissa;
  if (exp == 0xFF) {
    return 0x80000000;
  }
  if (exp == 0) {
    return 0;
  }
  mantissa = frac | 0x800000;
  if (E < 0) {
    return 0;
  }
  if (E > 30) {
    return 0x80000000;
  }
  if (E > 23) {
    mantissa = mantissa << (E - 23);
  } else {
    mantissa = mantissa >> (23 - E);
  }
  if (sign) {
    mantissa = -mantissa;
  }
  return mantissa;
}

这个实现的关键步骤：

1. 提取符号位、指数和尾数
2. 计算实际指数
3. 处理特殊情况
4. 调整尾数并考虑符号

在实际开发中，理解这些位操作对于性能优化和底层系统编程至关重要。特别是在嵌入式系统、加密算法和图形处理等领域，这些技巧可以显著提高代码效率。