算法位操作总结笔记。

1 前言

C/C++语言提供的位运算符有：

位运算的结果演示：

2 用于整数的奇偶性判断

想想，我们要判断一个数的奇偶性，在没用位运算之前我们可以用下列的代码来实现：

template<class Type>
bool Parity(Type value)
{
	if(value % 2 == 0)
		return false;
	else
		return true;
}
//加以优化 
template<class Type>
inline bool Parity(Type value)
{
	return (value % 2 != 0);
}

要知道，上面的代码我们使用的是对2取余，如果操作数value是小数的话，还勉强行得通，但是value是一个上百万的大数，那么这就白白浪费了CPU的大量时间，程序的效率和性能就很差。我们知道任何数在计算机储存中都是以二进制储存的，细心的你就会发现在二进制的最小一位有个特点，为0就是偶数，为1就是奇数，按照这个原理我们根本没必要让我们的CPU大哥白白做那么多的工作，只要一步判断就可以了。接下来就让我们看看位运算的精妙之处！

那么我们的目的就是判断最小位是0还是1，可是我们怎么判断呢？我们要用位运算阿里判断，就是与或非。在上面的复习之中我们只说了位运算的计算方法，并没有说其用处。那么在这里我们用到的就是“与”！与运算特有的一个功能就是判断指定位上的值（0或1）。我们来看下面的表格（与运算）。

我们要注意一下这里的 操作数2 ，它只有最低位是1，其余位都是0，这就是关键所在，操作数1是随机值。我们看看结果只会有两种结果：0或1。这个结果就取决于操作数1的最低位，它为1时就为1，为0时就为0.

“那么我要判断的是第二位呢？”

好！那我们就把操作数2改为 00000010 那么结果就只会有 00000000 或 00000010 其结果取决于第二位。

有了这个基础那么我们来看看怎么用位运算判断奇偶性吧：

template<class Type>
bool Parity(Type value)
{
	if(value & 0x0001 == 0)
		return false;
	else
		return true;
}
//加以优化 
template<class Type>
inline bool Parity(Type value)
{
	return (value & 1 != 0);
}
//在简化 
#define	PARITY(value) (value&1)

使用a%2来判断奇偶性和a & 1是一样的作用，但是a & 1要快好多。

3 判断n是否是2的整数冪

所谓2的整数冪就是指 1(2的0次冪)，2，4，8，16，32，64，128，256，512，1024，2048………….等数字，若何判断一个数是否是这样的数呢？我们看看不用位运算的计算方法：

#include "math.h" 
 
template<class Type>
bool IsPowerOfTwo(Type value)
{
	for(int i = 0,l = 8*sizeof(value); i < l ;i++)
	{
		if(pow(2,i) == value)
		{
			return true;
		}
	} 
	return false;
}

在这个算法中，我们使用了一个循环。其原理非常简单就是一一的对比，但是其中还调用了数学函数库，效率大大降低。接下来我们讲讲怎样用位运算来判断。我们首先要研究一下这些数的特性，请看下表（与运算）：

我们发现 n &（n-1） = 0 我们可以 用逻辑非 !（n&（n-1）） = 1 。那是不是这样就可以了呢，你会发现 !（0&（0-1）） = 1 但是 0并不是 2的正整数冪。我们可以用 逻辑与 （!（n&（n-1） && n） = 1;请看下面的代码：

template<class Type>
inline bool IsPowerOfTwo(Type n)
{
	if(((!(n&(n-1))) && n) == 1)
		return true;
	else
		return false;
}
//简化 
#define	ISPOWEROFTWO(n) ((!(n&(n-1)) ) && n)

4 统计n在二进制中1的个数

朴素的统计办法是：先判断n的奇偶性，为奇数时计数器增加1，然后将n右移一位，重复上面步骤，直到移位完毕。

template<class Type>
inline bool Parity(Type value)
{
	return (value % 2 != 0);
}
 
template<class Type>
inline int CountOne(Type value)
{
	if(value != 0)
	{
		return Parity(value) + CountOne(value >> 1);
	}
	return 0;
}

朴素的统计办法是比较简单的，那么我们来看看比较高级的办法。

举例说明，考虑2位整数 n=11（十进制为3），里边有2个1，先提取里边的偶数位10，奇数位01，把偶数位右移1位，然后与奇数位相加，因为每对奇偶位相加的和不会超过“两位”，所以结果中每两位保存着数n中1的个数，那么把 n 计算之后得到的值为：（10»1）+01 = 01 + 01 = 10, 把10换成十进制就是 2，2就代表 n(3)=11 中有两个1！

相应的如果n是四位整数 n=0111(十进制7)，先以“一位”为单位做奇偶位提取：偶数位 0010，奇数位0101。然后偶数位移位（右移1位）再相加：（0010»1）+0101=0110；再用0110以“两位”为单位做奇偶提取：偶数为0100，奇数位0010。偶数位移位（这时就需要移2位）再相加：（0100»2）+0010=0011，因为此时每对奇偶位的和不会超过“四位”，所以结果中保存着n中1的个数：（0100»2）+0010=0011 把0011换成十进制就是3，3就是n(7)=0111中有3个1。

依次类推可以得出更多位n的算法。整个思想类似分治法。

在这里就顺便说一下常用的二进制数：

例如：32位无符号数的1的个数可以这样数：

int CountOne(unsigned int n)
{
    //0xAAAAAAAA，0x55555555分别是以“1位”为单位提取奇偶位
    n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555);
    //0xCCCCCCCC，0x33333333分别是以“2位”为单位提取奇偶位
    n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333);
    //0xF0F0F0F0，0x0F0F0F0F分别是以“4位”为单位提取奇偶位
    n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F);
    //0xFF00FF00，0x00FF00FF分别是以“8位”为单位提取奇偶位
    n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF);
    //0xFFFF0000，0x0000FFFF分别是以“16位”为单位提取奇偶位
    n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF);
 
    return n;
}

看起来似乎采用位运算的代码比朴素方法代码要复杂的多，但是在性能上有着朴素方法无法比拟的优越性，只要四步简单的运算就能达到目的，而朴素方法不是用循环就是递归，这大大降低了CPU的运算性能。

5 对于正整数的模运算（注意，负数不能这么算）

先说下比较简单的：

乘除法是很消耗时间的，只要对数左移一位就是乘以2，右移一位就是除以2，据说用位运算效率提高了60\%。

乘$2^k$ 众所周知： $n«k$。所以你以后还会傻傻地去敲$2566*4$的结果10264吗？直接$2566«2$就搞定了，又快又准确。

除$2^k$众所周知： $n»k$。

那么 $\mod 2^k$ 呢？（对2的倍数取模）

$n \& ((1«k) -1)$

用通俗的言语来描述就是, 对2的倍数取模，只要将数与2的倍数-1做按位与运算即可。

好！方便理解就举个例子吧。

思考：如果结果是要求模$2^k$时，我们真的需要每次都取模吗？

在此很容易让人想到快速幂取模法。

5.1 快速幂取模算法

经常做题目的时候会遇到要计算 $a^b \mod c$ 的情况，这时候，一个不小心就TLE(算法计算超时，ACM题目测试结果常见问题)了。那么如何解决这个问题呢？位运算来帮你吧。

首先介绍一下秦九韶算法：(数值分析讲得很清楚)

把一个$n$次多项式$f(x) = a[n]x^n+a[n-1]x^{(n-1)}+\cdots +a[1]x+a[0]$改写成如下形式：

求多项式的值时，首先计算最内层括号内一次多项式的值，即

$v[1]=a[n]x+a[n-1]$

然后由内向外逐层计算一次多项式的值，即

这样，求 $n$ 次多项式 $f(x)$ 的值就转化为求$n$个一次多项式的值。

好！有了前面的基础知识，我们开始解决问题吧。

由 $(a \times b) \mod c=( (a \mod c) × b) \mod c$ .

我们可以将 $b$先表示成：

$b = a[t] × 2^t + a[t-1]× 2^{(t-1)} +\cdots + a[0] \times 2^0. (a[i]=[0,1]).$

这样我们由 $a^b mod c = a^(a[t] × 2^t + a[t-1] × 2^{(t-1)} + \times a[0] \times 2^0) \mod c$.

然而我们求 $a^{(2^{(i+1)})} \mod c=((a^(2^i)) \mod c)^2 \mod c $ 求得。

具体实现如下：

使用秦九韶算法思想进行快速幂模算法，简洁漂亮

// 快速计算 $(a ^ p) \% m$ 的值

__int64 FastM(__int64 a, __int64 p, __int64 m)
{ 
    if (p == 0) return 1;
    __int64  r = a % m;
    __int64  k = 1;
    while (p > 1)
    {
        if ((p & 1)!=0)
        {
            k = (k * r) % m; 
        }
        r = (r * r) % m;
        p >>= 1;
    }
    return (r * k) % m;
}

http://acm.pku.edu.cn/JudgeOnline/problem?id=3070

6 计算掩码

什么是掩码？掩码是一串二进制代码对目标字段进行位与运算，屏蔽当前的输入位。用于从一个或多个字节中选出的位的集合。 举个例子：

我们有一个IP地址：192.168.1.111 对应二进制：11000000.10101000.00000001.01101111。

我们让这个IP位与：255.255.255.0 对应二进制：11111111.11111111.11111111.00000000。

可以得到子网地址：192.168.1.0 对应二进制：11000000.10101000.00000001.00000000。

在例子中我们通过观察二进制码就知道，这个过程就是拿到IP的前三个字节的数据信息，这里用到的255.255.255.0就是掩码，也就是我们常说的子网掩码。通过子网掩码可以轻松的得到子网地址。那么通过掩码我们就可以轻松的得到多个字节中指定的位的集合。

我们现在有一个需求：获得数$x$的低$n$位的集合。

假设$x = 233, n= 6$，我们就知道计算方法：233的二进制是 11101001，所以结果集为 $11101001 \& 00111111$ = 00101001 十进制为 41。在这个计算中233可以轻易改变，但是 00111111 已经指定 $n = 6$，要可以让$n$也随意改变怎么办呢？

我们用位运算的思维就可以得到 $n = 6$ 时 00111111 可以表示为 $(1 « 6) - 1$.

那么掩码的计算公式就为：$(1 « n) - 1$.

现在根据需求可以写出模版函数如下：

template<class Type>
inline Type LowByte(Type x, int n)
{
	return x & ((1 << n) - 1);
}
//简化 
#define	LOWBYTE(x,n) x & ((x << n) - 1)

如果是高位集合呢？我们只需要把掩码左移就可以了：$n = 6$ 时 $00111111«2$ 公式为：$((1 « 6) - 1)«2$.

template<class Type>  
inline Type HeightByte(Type x, int n)  
{  
    return x & (((1 << n) - 1) << (sizeof(x)-n));  
}  
//简化  
#define HEIGHTBYTE(x,n) x & (((1 << n) - 1) << (sizeof(x)-n))

7 子集

假设我们有一个集合 $mask =｛‘c’，‘b’，‘a’｝$，要求列出集合的所有子集。我们可以使用位运算思想，把集合的元素的有无看成二进制的0和1那么我们展开举例：

枚举出一个集合的子集。设原集合为mask，则下面的代码就可以列出它的所有子集：

for (i = mask ; i ; i = (i - 1) & mask) ;