微软魅力时刻
数据的机器级表述
位运算就是我们接触的最早的“simd”
每个bit就是一个data
整数也可视作一个bitset，进而引出问题：如何进行集合操作（如成员归属判断，交集等）
遍历集合元素可以借助lowbit实现
一种高效的求二进制中有多少1的实现
这里是求|S|
int bitset_size1(uint32_t S) { // SIMD
S = (S & 0x55555555) + ((S >> 1) & 0x55555555);
S = (S & 0x33333333) + ((S >> 2) & 0x33333333);
S = (S & 0x0F0F0F0F) + ((S >> 4) & 0x0F0F0F0F);
S = (S & 0x00FF00FF) + ((S >> 8) & 0x00FF00FF);
S = (S & 0x0000FFFF) + ((S >> 16) & 0x0000FFFF);
return S;
}
对相邻位进行归并
求log2(x)下取整
即找出最高位的1
二分查找
clz()求出最高位的1前有多少0，31-clz(x)即为所求
int clz(uint32_t x) {
int n = 0;
if (x <= 0x0000ffff) n += 16, x <<= 16;
if (x <= 0x00ffffff) n += 8, x <<= 8;
if (x <= 0x0fffffff) n += 4, x <<= 4;
if (x <= 0x3fffffff) n += 2, x <<= 2;
if (x <= 0x7fffffff) n ++;
return n;
}1+1/2+1/3+…+1/n
从较小数开始累加，和从1开始加相比有较大差异