位运算

位运算的用法虽然不多,但是所用之处大多有出神入化的作用。

总结一下常用的场景。

  1. 位与运算&,位或运算|,非~,异或运算^

  2. 不使用额外变量交换两个数

    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。

  3. 翻转数组就可以用上面的swap进行。

  4. a>>1,向右位移1位等效于a/2,a<<1,向左位移等效于a*2

    左移右移都丢弃溢出的位并补零,但是右移的时候当为有符号整型时情况有点不同。

    在二分查找时这种方法用的多,一般用到的*2或者/2的时候最好用这种方法提升效率。

  5. bitmap

  6. 对于查找字符串的重复字符,看代码

    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里面常用的。

  7. 布隆过滤,参见这

← 破解联通HG8346R  C程序设计语言 →