位运算黑科技

一些位运算的技巧

1 黑科技

先给出大招

位运算的奇技淫巧，题目出自知乎,只用位运算实现比较两整数大小.
直接给出答案

int compare(uint32_t a, uint32_t b) {
		uint32_t diff = a ^ b;
		if (!diff) return 0;
		// 001xxxxx -> 00100000 
		diff |= diff >> 1;
		diff |= diff >> 2;
		diff |= diff >> 4;
		diff |= diff >> 8;
		diff |= diff >> 16;
		diff ^= diff >> 1;
		return a & diff ? 1 : -1;
	}

很难读懂，我也是搜了很多资料，发现了贴吧一大神分析了这一问题，原来这一问题早就有了，估计答案的原始来源就是这。
首先分析第一句diff = a ^ b;我们要明确比较大小，只需要比较第一位不一样的比特位，异或的目的就很明确了，将a,b的不同比特位找出。
之后就是这一大串
>diff |= diff >> 1;
diff |= diff >> 2;
diff |= diff >> 4;
diff |= diff >> 8;
diff |= diff >> 16;

它的目的是将从高位到地位的第一个不同位之后的位都置一，
例如00010000->00011111,具体怎么实现的，以00010000为例，执行第一句后变为00011000，执行第二句后变为00011110…,之后不难理解，为什么依次右移1，2，4，8，16.
最后一句也不难理解只留从高位到地位的第一个不同位，
若a>b则a对应的位是1，反之对应的是0.

2 零碎技巧

功能	实现	例子
最后一位变为1	0000->0001	x|0x01
最后一位变为0	0001->0000	x&0x00
最后一位取反	1111->1110	x^0x01
右数第k位变成1	1011->1111	x|(1<<\k)
右数第k位变成0	1111->1011	x&~(1<<\k)
右边连续的1变成0	10011111->10000000	x|(x+1)
右边连续的0变成1	10000000->11111111	x|(x-1)
右起第一个0变成1	1011->1111	x|(x+1)
取右边连续的1	1011->0011	x^(x+1)
去掉右起第一个1的左边	1010->0010	x&(-x)
## 3一些运用
位运算的运用就不得不提树状数组了
下面是维基百科的解释。

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. This structure was proposed by Peter Fenwick in 1994 to improve the efficiency of arithmetic coding compression algorithms.

他的作用是计算前缀和，由于巧妙运用位运算时间复杂度只有$O(logn)$.

int bit[maxn],n;
int sum(int i){
    int s=0;
    while(i>0){
        s+=bit[i];
        i-=(i&i-1);
    }
}
void add(int i,int x){
    while(i<=n){
        bit[i]+=x;
        i+=(i&-x);
    }
}