课程主页:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2018/index.htm

课程视频:

https://www.bilibili.com/video/BV1wA411h7N7

这次回顾第三讲,这一讲介绍了位级的技巧。

Lecture 3 Bit Hacks

二进制表示

是$w$比特计算机单词。

如果$x$表示无符号整数,那么其对应的值为

如果$x$表示带符号整数,那么其对应的值为

特例:

考虑

x = 0b11...1

那么

互补关系

因为我们有

x + ~x = -1

所以可得

-x = ~x + 1

设置第k个比特

y = x | (1 << k);

清除第$k$个比特

y = x & ~(1 << k);

翻转第k个比特

y = x ^ (1 << k);

提取比特域

(x & mask) >> shift

例子:

设置比特域

x = (x & ~mask) | (y << shift)

不利用临时变量交换两数

x = x ^ y;
y = x ^ y;
x = x ^ y;

原因:

(x ^ y) ^ y = x

不使用分支计算最小值

r = y ^ ((x ^ y) & -(x < y));

原因:

如果$ x<y$,那么

-(x < y) = 0b1...1
(x ^ y) & -(x < y) = (x ^ y)
r = y ^ (x ^ y) = x

如果$x\ge y$,那么

-(x < y) = 0b0...0
(x ^ y)  & -(x < y) = 0
r = y ^ 0 = y
应用

对不可预测的分支,可以利用之前的方法进行优化:

条件1,2,4大多数情形都成立,所以称其为可预测的,条件3无法判断何时成立,对此处进行之前的优化:

static void merge(long * __restrict C,
				 long * __restrict A,
                  long * __restrict B,
                  size_t na,
				 size_t nb) {
	while (na > 0 && nb > 0) {
		long cmp = (*A <= *B);
		long min = *B ^ ((*B ^ *A) & (-cmp));
		*C++ = min;
		A +=  cmp; na -=  cmp;
         B += !cmp; nb -= !cmp;
	}
    while (na > 0){
    	*C++ = *A++;
         na--;
    }
    while (nb > 0){
    	*C++ = *B++;
         nb--;
    }
}

模加法

假设我们计算

我们假设

优化方式如下:

z = x + y;
r = z - (n & -(z >= n));

向上近似到$2$的幂

计算

实际上只要找到为$1$的最高位即可,方式如下:

uint64_t n;
--n;
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
++n;

效果:

一开始让$n$减$1$是为了处理$n=2^k$的情形。

备注:此处

最低有效位的1

方法如下:

r = x & (-x)

例子:

计算$\lg x$,其中$x$为$2$的幂

方法如下:

原因如下:

长度为$2^k$的deBruijn序列$s$是0-1循环序列,使得长度为$k$的$2^k$个0-1串中作为$s$的子串恰好出现一次。

考虑$k=3$:

原因:

https://www.cnblogs.com/shangdawei/p/3967505.html

N皇后问题的比特向量表示

利用比特表示放置情况,比特位为$1$表示放置了queen。

在$c$列中放置queen是不安全的,如果下式非零:

down & (1 << c)

其中down的第$k$位为$1$,当且仅当第$k$列放置了queen。

其中left是长度为$2n-1$的比特数组,left的第$k$位为$1$,当且仅当第$k$个对角线上放置了queen,所以判断条件为:

left & (1 << (r + c))

同理right数组存储副对角线,判断条件为:

right & (1 << (n - 1 - r + c))

计算$x$的比特表示中$1$的个数

方法1:

for (r=0; x!=0; ++r)
	x & = x - 1;

该操作每次消除最低有效位的$1$:

方法2:

static const int count[256]=
{ 0, 1, 1, 2, 1, 2, 2, 3, 1,, 8};
for (int r = 0; x !=0; x >>= 8)
    r += count[x & OxFF];

思路是预先计算所有$8$比特数所含$1$的个数。

方法3:

Compute popcount的前两步是为了防止溢出。

计算流程:

原因解释:

第一步操作计算每两个位置中$1$的个数:

x = ((x >> 1) & M0) + (x & M0)

第二步操作计算了每四个位置中$1$的个数:

x = ((x >> 2) & M1) + (x & M1)

其余操作以此类推。。。

内置函数:

int builtin_popcount (unsigned int x);

补充材料

http://graphics.stanford.edu/~seander/bithacks.html