0x01——位运算

基础知识及二进制常见用法

• 前言

bit是度量信息的单位，包含0和1两种状态。计算机的各种运算最后无不归结位一个个bit的变化。熟练掌握并利用位运算，能够帮助我们理解程序运行中的种种表现，提高程序循行的时空效率，降低编程复杂度。

• 运算符优先级

从左到右优先级依次降低

加减	移位	比较大小	位与	异或	位或
+，-	<<,>>	<,>==,!=	&	xor(C++^)	|

• 位与memset

我们都知道，memset可以以字节为单位初始化变量或者数组，这里有几个特>别的数字：

• 0x3F3F3F3F 1061109567
  -> 0x7F7F7F7F 2147483647
• 0xFFFFFFFF -1

观察这几个数字，我们会发现0x3F3F3F3F是个很有用的数字，原因如下：

• 可以直接用memset初始化
• 0x3F3F3F3F的两倍不会超过int的最大范围
• 这个数足够大

这也是常常使用INF = 0x3F3F3F3F的原因

memset(a,0x3f,sizeof a);

• 移位运算

>>	<<
即除以2向下取整	$1<<n=2^n,n<<1=2?n$

例题：

1. a^b
2. 64位整数乘法

• 二进制状态压缩

$二进制状态压缩，是指将一个长度为m的bool数组用一个m位的二进制整数表示$
$并储存的方法。利用下列位运算操作可以实现原bool数组中对应下标的存取。$

操作	运算
取出整数n在二进制表示下的第k位	$(n>>k)\&1$
取出整数n在二进制表示下的第0~k-1位(后k位)	$n\&((1<<k)?1)$
把整数n在二进制表示下的第k位取反	$nxor(1<<k)$
对整数n在二进制表示下的第k位赋值1	$n$|$(1<<k)$
对整数n在二进制表示下的第k位赋值0	$n\&($~$(1<<k))$

例题：

1. 最短Hamilton路径
   2.起床困难综合症

• 位的其他应用

1. 成对变换

通过计算可以发现，对于非负整数$n:$

• $当n为偶数时，nxor1等于n+1$
• $当n为奇数时，nxor1等于n?1$

$因此，“0与1”，“2与3”，“4与5”...关于xor1运算构成“成对变换”$

这一性质经常用于图论邻接表的储存。

在具有无向边（双向边）的图中把一对正反方向的边分别储存在邻接表数组的$n$与$n+1$ 位置（$n$为偶数），就可以通过$xor1$的运算获得与当前边$(x,y)$反向的边$(y,x)$的储存位置。详细应用我们将在讲解邻接表时(第0x13节)给出。

2. lowbit运算

   lowbit运算定义非负整数$n$在二进制表示下 $“最低位的1及其后边所有的0”$ 构成的数值。例如 n = 10 的二进制表示为 $(1010{)}_2$，则$lowbit(n)=2=(10{)}_2$。下面我们来推导$lowbit(n)$的公式。

   $设n>0,n的第k位是1，第0$ ~ $k?1位都是0。$
   $为了实现lowbit运算，先把n取反，此时第0$
   ~ $k?1位都是1。$
   $在令n=n+1，此时因为进位，第k位变为1，$
   $第0$ ~ $k?1位都是0。$
   $而且n的第k+1到最高位恰好与原来相反，所以$
   $n\&($~$n+1)仅有第k位为1，$
   $其余位都是0，而在补码表示下$~$n=?1?n,因此：$
   $lowbit(n)=n\&($~$n+1)=n\&(?n)$

   $lowbit$操作可以配合Hash(0x14节)可以找到整数二进制表示下所有是1的位。
   此外，$lowbit$运算也是树状数组(0x42节)中的一个基本运算。