位运算的用法虽然不多,但是所用之处大多有出神入化的作用。
总结一下常用的场景。
-
位与运算&,位或运算|,非~,异或运算^
-
不使用额外变量交换两个数
int swap(int *x,int *y) { *y = *x^*y; *x = *x^*y; *y = *x^*y; }
都是适用异或运算,原理其实是把临时变量和另外一个数混合起来了。
而且异或运算有两个特点:
一个数亦或本身恒等于0,一个数亦或0等于本身。
所以上面的第二步其实为*x=*x^*x^y=0^*y=y,这样就把数交换了。
同理,第三步y=*y^*x^*y=0^*x=*x。 -
翻转数组就可以用上面的swap进行。
-
a»1,向右位移1位等效于a/2,a«1,向左位移等效于a*2
左移右移都丢弃溢出的位并补零,但是右移的时候当为有符号整型时情况有点不同。
在二分查找时这种方法用的多,一般用到的*2或者/2的时候最好用这种方法提升效率。
-
bitmap
-
对于查找字符串的重复字符,看代码
bool isUnique2(string s) { int a[8]; memset(a, 0, sizeof(a)); int len = s.length(); for(int i=0; i < len; ++i) { int v = (int)s[i]; int idx = v/32, shift=v%32; if(a[idx] & (1 << shift)) return false; a[idx] |= (1 << shift); } return true; }
这里要注意几点,ascii字符256个,而int为32位4bit,所以需要8个int的数组。这儿类似bitmap。
要首先确定是在哪个数组,所以idx代表数组的下标。
**1«shift,这儿就相当于把二进制0001向左位移shift位,shift为余数。**然后和int进行位与运算,当前位和已经存在的当前位都为1才代表已经存在了。
上面的这个方法应该是bitmap里面常用的。 -
布隆过滤,参见这