计算机安全：快速比特操纵算法

快速比特操纵算法含义

使用机器字操作(算术、逻辑运算)实现机器字中的比特的计算和变换，是一种时间复杂度与机器字长无关的算法。

计算1的个数

unsigned int v; 	//c的值即1的个数	
	unsigned int c; 		
	for (c = 0; v; c++)
    v &= v - 1;

分块和

对于一个二进制数x（总位数为w），将其划分为多段相同长度u的区间，将每个区间内的1的个数转化为二进制，首尾相接得到y：y称为x的u分块和。

例如：101010的1分块和是1,0,1,0,1,0,101010的2分块和是01,01,01，101010的6分块和是000011。

因为u位能表示的最大个数，大于等于u的长度，故该方式能正确表达出分块和而不发生溢出。

递推表达式

$x^{[2 u]} = y A N D (0^{u} 1^{u})^{w / 2 u} + (x^{[u]} >> u) A N D (0^{u} 1^{u})^{w / 2 u}$
说明

简单来说，便是将奇数个u区间和偶数个u区间相加。

例如上面01010101的例子：
先将01010101和00110011按位与，只保留奇数位u区间得到00010001；
再将01010101右移u位，得到00010101，与00110011按位与，只保留偶数个u区间得到00010001。

再将两数相加，完成合并。

这种方法参照了递归方式，计算1的个数的时间复杂度是O(log w)，小于上一方法的O(w)。

特例

若一个数，每个区间除了最后一位为0/1，其他位都为0：换而言之，最低位的数表示这个u区间有多少个1：

形如001001001001、000000001001，将其与001001001001相乘，结果的从右往左数的第m-1=w/u-1（从0开始计数）个u区间的值为此二进制数的1的个数。

对于这个例子，001001001001与001001001001相乘，结果为1010011100011010001，得到001001001001中1的个数是4。

推广

$所有 u 区间的第 i 个比特中 1 的数量 C_{i} = ((x >> i) A N D (0^{u - 1} 1)^{m}) * (0^{u - 1} 1)^{m}$
即：通过移位和按位与，强制将每一部分的数变成“每个区间除了最后一位为0/1，其他位都为0”的形式。

如110110，分块为110，110，求第0,1,2位的1的个数的操作分别为000000*001001，001001*001001，001001*001001。

将上面的结果相加，取从右往左数的第w/u-1（从0开始计数）个u区间的值，便是110110中1的个数，得到4。注意：分块长度至少为lgw，否则相加时会产生进位(即需满足w<2^{u})。

总结：如果设区间长度为lgw，则需要做[0,lgw）次乘法，并将乘法得到的结果相加，最后取第m-1(从0开始计数)个u区间的值。

加法方法进行到区间长度 u = lgw 时；

用一次乘法，结果的第 m - 1 个 u 区间的值等于 x 中 1 的个数。

时间复杂 O(loglog w)

此时虽然y的每个分块不满足“每个区间除了最后一位为0/1，其他位都为0”,但满足“表示的数的大小为x的对应分块的1的个数”。即结果的第 m - 1 个 u 区间的值并非为y中1的个数，而是x的1的个数。

额外的：

$x^{[l g w]} m o d (2^{l g w} - 1) 等于所有 u 区间的和$

例子：

0001001010001111，分块为4，则x[lgw]为0001,0001,0001,0100(十进制为4372)。

其乘以0001000100010001的结果的第3个数为0111，值为7。同时，4372模15的值也为7。

前导知识

log*(n)的定义：满足log( log( ··· log(n) ··· ) ) ＜1 的最小log个数。

lg*(32) = lg*(64) = lg*(128) = ··· = lg*(2^16) = 4

u个比特能表示2的u次方-1大小，也即(2的u次方-1)/u个u区间的1的个数之和。

思想：让每次乘法尽最大可能扩张区间长度。

解决

$设 u^{'} 是用一次乘法能得到的最大区间长度，则 u^{'} = u ⌊ \frac{2^{u} - 1}{u} ⌋$

$定义 L (1) = l g w, L (2) = l g l g w, . . ., L (i) = l g (i) w . 则: x^{[L (i - 1)]} = (x^{[L (i)]} * (0^{L (i)} 1)^{\frac{L (i - 1)}{L (i)}}) >> (L (i - 1) - L (i))$

说明：从L(i)区间开始，每次将区间放大为原来的2次幂倍，直到区间长度为lgw。此时运用一次分块乘法，便能得到结果。

原理：存在y，x[u] * y = z，对于 z 的每个u’区间，其最高 u 比特的值是x[ u’]对应区间的值。通过移位等处理，可得到x [u’]

具体公式课堂略过

LSB计算

前导知识

二元de Bruijn序列是一种特殊的周期为2的n次方的序列，满足任意一个二元n长向量都在de Brujn序列的一个周期中恰出现一次。

如n取3时，序列为0001011100，也即00010111的循环：其中000,001,010,011,100,101,110,111只出现了一次。

构造方法

构造哈希函数h(x)：其中x是2的幂次方，最大值小于2的w次方，h(x)为0到w-1的任意一个数。
h(x) =B * x >> (w – lg w)，lgw整除w(why?)。

这个操作相当于对B进行移位后取高lgw(即上文中的n)位，因为B的特殊性，所以h(x)和x是一一对应的。

构造表D：对于长度为lgw的数(或者说0<=x<w)x，找到lgw维de Bruijn的第x位，取lgw个，得到的数记为y，D[y]=x。(y互不相同；O(w)时间，O(wlgw)空间)

这一步实际上就是由x确定h(x),不同的是，这里的x是LSB的值，而上文的的x是2的幂次方。h(x)的作用是，作为枢纽，连接这两个值。

将word的除了最低置位bit之外的bit置 0(一个方式：(~word+1) AND word,~即按位取反)

结果与De Bruijn序列相乘，取乘积的前lgw bit得到数x’(这一步实际上就是进行h(x))

用结果查表D，得到D[x’]，即为LSB的位置

原理

LSB的值根据de Bruijn序列，映射成了唯一的长度为lgw的值，而这长度为lgw的值又通过de Bruijn序列映射成了唯一的2的幂次方。当de Bruijn序列确定时，这两个映射关系是唯一确定的。

构造方法

将 x分为 u bit区间。

将LSB隔离出来，其他bit都是0。(一个方式：(~word+1) AND word,~即按位取反)

注意：其中 u 应该大于根号w,否则做乘法时，00..1串无法覆盖所有的u区间。
计算LSB所在的区间号i

生成一个机器字 $F = (0^{u - 1} 1)^{u}$
$将第 i 位之后的 u 区间的最低位比特置 1 ： y = (x << 1 - 1) A N D F$
$通过如下操作将所有 i 之后 u 区间的最后的比特相加到一个区间里: y = y * (0^{u - 1} 1)^{u}$
$在机器字 Y 的最高 u 比特中存放的数值就是 L S B 所在的 u 区间的编号:(截断为w位) i = y >> (w - u)$

原理

LSB后面的所有u区间的最低位为1，故在LSB及其后面有多少个u区间，便有多少个1被加。注意：这里的01串的重复次数是u，而非w/u

计算LSB在区间中的位置j

将x的i区间复制成u份： $y = x >> ((i - 1) * u) * (0^{u - 1} 1)^{u}$
只将第j个u区间保留下来： $y = y A N D (0^{u} 1)^{u}$
采用计算区间号i的方法，得到j

则y = u*(i-1)+j。

例子：

100(u为3):

计算i：(0111&(001001001))*(001001001)=001001001,取高u位，即i=1。

计算j：100复制三次：100100100，再与上000100010001得100000000,利用计算i的方法，得到j=3。

最终：(1-1)*3+3=3。

反例：

100 000 000 000…(u为3)：

此时不管后面有多少个000，最后都会得到LSB在第三个区间，而这是错误的。那为什么不动态改变机器字F来使得其正确:耗时。

前导知识

SetR(x,u)

此操作根据机器字x中u区间是否为0对u区间进行设置，如果为0，则u区间不变，否则最低位置为1。

$（ 1 ）将每个 u 区间最高位置为 1 。 x = x A N D (10^{u - 1})^{u} 。$
$（ 2 ） y = x - (0^{u - 1} 1)^{u}$
$（ 3 ）将等于 10^{u - 1} 的 u 区间的最高为置为 1 。 x = y | (x A N D (10^{u - 1})^{u}) .$
$（ 4 ） x = x >> u$

反向聚合操作compr(x,u)

此操作将每个区间的最后一个比特聚合在一个u区间中，但顺序相反。

$（ 1 ） y = S e t R (x, u)$
$（ 2 ）将每个 u 区间的最低位比特反向聚集在 y 的最高 u 区间。 y = y * (0^{u} 1)^{u}$
$（ 3 ） x = y >> (w - u)$

扩散操作diffu(x,u)

此操作将一个u区间的每个比特放置到每个u区间的最低比特上，顺序不变。

$1 ）将 0 区间复制 u 份 y = x * (0^{u - 1} 1) u$
$（ 2 ）保留第 i 区间的第 i 个比特 y = y A N D (0^{u} 1) u$
$（ 3 ） S e t R (y, u)$

计算方法

首先计算MSB所在的u区间的号

（1）y = SetR(x)

（2）y = Compr(y,u)

（3）y = diffu(y,u)

（4）计算y中的MSB的位置 i，因此MSB在x中所在区间为 i’= u-i

计算i’区间中MSB位置

（5）y = x>>(i’u)

（6）y = diffu(y,u)

（7）计算y中的MSB的位置 j，因此MSB所在区间为 j’= u-j

最终可得到MSB的位置为 i’u+j’
此部分在课堂略过

比特置换

递归方法实现完全比特反转O(lgw)

unsigned int reverse(unsigned int x)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    
    return((x >> 16) | (x << 16));
}