C/C++刁钻问题各个击破之位运算及其应用实例(1)
摘要
位运算是C/C++中的基本运算之一，即便是这样，它对大多数程序员来说是一个比较陌生的运算——大多数程序员很少使用位运算。本篇先简要介绍基本的位运算操作符及其用法(何时使用)，然后介绍位运算符的几个典型应用：
（1） 三种不用临时变量交换两个整数的实例，并分析每个实例的优缺点
（2） 进制转换，通过位运算实现将十进制数按二进制和十六进制输出，并得出一个通用的，用于将十进制按照2的n次方进制输出的程序。
（3） 给出利用位运算实现的计算整数的二进制表示中有多少个1的实例。
揭开位运算的面纱
所有数据在计算机底层都是按二进制存储的，一个数据可以看做是一个有序的位集合。每一位只有两种状态：0或1。位运算允许程序员操作数据的某一特定位，比如将某位设置为1(或0)，查询某位的状态(1，或0)。位运算由位运算操作符和操作数组成，不同的位运算操作符定义了不同的位运算，下面的表格是对每种位运算操作符及其对应的位运算和功能进行描述：
位运算操作符
对应的位运算
用法
功能描述
~
按位非
~expr
翻转expr的每一个位：1变0,0变1
<<
左移
expr<<n
将expr向左移动n位，移到外面的被丢弃，右边的位补0，因此左移n位相当于乘以2n
>>
右移
expr>>n
将expr向右移n位，移到外面的被丢弃，如果expr是无符号类型，则左边补0，否则，左边插入符号位的拷贝或者0(视具体实现而定)。
&
按位与
expr1&expr2
在每个位所在处，如果expr1和expr2都含有1，那么结果该位为1，否则为0。
|
按位或
Expr1 | expr2
在每个位所在处，如果expr1和expr2都含有0，那么结果该位为0，否则为1。
^
按位异或
Expr1 ^ expr2
在每个位所在处，如果expr1和expr2不相同，那么结果该位为1，否则为0.
除了上面的基本位运算操作符外，还有&=，^=，|=，<<=,>>=等组合符号，它们分别是：按位与赋值，按位异或赋值，按位或赋值，左移赋值，右移赋值。接下来介绍如何实现位操作：
1.将expr的第n（n从0开始）位设置为1: expr |= (1<<n);
2.将expr的第n（n从0开始）位设置为0: expr &= (~(1<<n));
3.判断expr的第n（n从0开始）位是否为1：bool b =expr & (1<<n);
4.翻转expr的第n（n从0开始）位：expr ^=(1<<n)；
注意
1. C标准提供了bitset来进行各种位操作，可以在MSDN中输入bitset了解相关内容，使用时需要包含头文件:#include”bitset”。
2. 位运算只能用于操作有整数类型的数，比如说char,short,int,long等(包含signed 和unsigned)，不能操作浮点数，比如float，double！std：：bitset的构造函数的参数是unsigned long int，尽量不要对负数进行为操作，因为可移植性差，不同的系统平台对负数的右移操作定义不一样（大多数平台规定高位补符号位，有些平台规定高位补0）。
位运算应用实例1：不用任何中间变量，交换两个整数
这个问题是比较经典的了，你可以很容易地在网上找到多种答案，我在这里给出两个方案：
方案1：用算术运算实现(一个不完美的方案)
该方案的思路简单，实现代码很短，如下：
Template<class T>
Void mySwap_1(T& a, T& b)
{
a = a+b;
b = a -b;
a = a-b;
}
简单吧，但是我还要简单说一下：第一句a=a+b;是用a保存原来的a跟原的b的和；第二句b = a-b;使得原来的a的值被保存到了b里面；最后一句a=a-b;使得原来的b的值保存到了a里面。
我们说这个方法是不那么完美的，原因在于算术运算可能会出现结果溢出的问题，假如a，b都非常大，那么第一句a=a+b就会导致结果溢出，比如说原来的a = 2147483647,b = 2,那么a+b就为2147483649，这个数大于了最大的无符号整数2147483648，因此发生溢出，a中保存的结果实际上是：-2147483647，但是让人惊讶的是：虽然第一句程序得到的结果为-2147483647，后面两句得到的结果却是正确的，即能实现交换原始a,b的值，也就是说：只有第一句的结果是错误的，但最后的结果却是正确的，这一点让我很迷惑，至今还没弄清楚缘由，再次向各位求教！
最后，谈谈这种方法相对于后面的方案2的优点：该方法可以用于交换两个非整数(浮点数)，而方案2基于位运算，而对浮点数不能直接使用位运算，因此方案2不能用于交换两个浮点数！
方案2：用位运算实现(较好的方案)
该方案代码与方案1及其相似，思路也不难，先看代码，然后再看我啰嗦的剖析：
template<class T>
void mySwap_2(T& a,T& b)
{
a = a^b;
b = b^a;
a = a^b;
}
对于编程老手来说，这个交换函数并不陌生，但我相信这些编程老手之中有一部分人只记得这么写代码，而不知道三句代码为何这么写，事实上我最初也是这样，因此一开始我就觉得短短3行代码，让我花费时间去理解分析，还不如直接记忆来得划算。事实上，直到今天我写这篇文章时，我舍得消耗一点脑细胞来理解它，下面我尝试着对上述三句代码进行阐述，为了方便，假设数据类型为char，并且a = 5,b=3;那么在内存中a,b存储如下：
a:
0
0
0
0
0
1
0
1
b:
0
0
0
0
0
0
1
1
接下来详细分析每一句：
首先来看第一句：a=a^b;执行该语句后a中保存了a与b的差异位，也就是说如果原来的a和b的某一位不同，那么就将a的该位置为1，因此a在内存中成了如下图的样子，它说明a与b的第2,3个bit有差异：
a:
0
0
0
0
0
1
1
0
接着我们来看第二句：b=b^a；其意思是，将b中有差异的位翻转，如此一来b中保存的值其实就等于原来a中的值，记住当第二个语句执行完之后a仍然保存了原来的a,b的差异信息，而b则变成了原来的a！
最后我们来看第三句：a=a^b;由于异或运算满易做图换律，因此这一句等价于：a=b^a;记住这个语句赋值号右边的b中已经保存了原始的a值，而a中保存了原始的a，b的差异，因此这一句的最终作用是将原始a中有差异的位翻转(变成b)然后赋值给a，如此一来a中就保存了原始的b值。
总结：上述三句中：第一句是记录差异，第2,3句是翻转，最终实现了不用任何中间变量就交换两个变量的值。
分析：位运算不考虑进位问题，因此不会有结果溢出的问题！但是由于不能对浮点数进行直接位运算，因此该方法不能实现交换两个浮点数！当然原题题目是交换两个整数。
备注：还有其他实现两个数交换的方法，比如采用内存拷贝！由于不属于位运算范畴，这里就不赘述了。
位运算应用实例2：进制转换
要求：分别实现十进制整数按二进制、十六进制输出。
两种方法实现按二进制输出：
方法1：由于整数在计算机中是按二进制存储的，我们只需要将其每个bit按顺序打印出来即可，如果某位为1，则打印字符‘1’，否则打印字符‘0’。我给出的代码
补充：软件开发 , C++ ,
