位运算符基础

四个位运算符:与&  或 ||   非 ~   异或^

设二进制数 a= 0101  b = 1101

 

a&b : 位与运算,两个位都为1,结果才为1

    0101
  & 1101
———————————
    0101

 

a||b : 或运算,只要有任意一个位为1结果即为1

 

    0101
|| 1101
———————————
    1101

 

~a : 按位取反

 

  ~ 0101
———————————
    1010
 

a^b : 异或运算:两个位相异为1

 

    0101
  ^ 1101
———————————
    1000
 

实例1:使用位运算交换两个整数

问题:写一个函数,完成两个整数的交换。(要求:不使用额外变量)

解答

int swap(int *x,int *y)
{
    *y = *x^*y;
    *x = *x^*y;
    *y = *x^*y;
}
 

实例2:数组反转

问题:如下程序完成数组的反转功能。其中用到的swap()函数如实例1所示。请问,下列程序能否正常工作?如果有问题该如何改正?

void reverse_array(int a[],int cnt)
{
    int first,last;
    for(first = 0,last = cnt -1;first <= last;first++,last--)
        swap(&a[first],&a[last]);
}

 

解答

当输入数组的元素个数为偶数个时,函数revers_array能够正常工作,但如果数组元素个数为奇数时,则最中间的那个元素将会变为0.

例如,当输入数组为[1,2,3,4]时,得到的结果为[4,3,2,1]

当输入数组为[1,2,3,4,5]时,得到的结果为[5,4,0,2,1]

修改方案:将for循环中判断条件first<= last 改为first<last即可。

 

实例3:理解并使用位运算

问题:给定两个函数bis()、bic(),通过调用者两个函数,实现位或运算和异或运算。

函数bis()、bic()功能说明如下:输入参数为一个数字x和一个掩码字m,他们生成一个结果z,z是由根据掩码m的位来修改x的位得到。

int bis(int x,int m);//通过掩码m将x的对应位置1

int bic(int x,int m);//通过掩码m将x的对应位清零

仅通过调用上述两个函数实现以下两个功能函数:

int bool_or(int x,int y);//返回x和y的或运算结果

int bool_xor(int x,int y);//返回x和y的异或运算结果

解答

int bool_or(int x,int y)
{
    return bis(x,y);
}

int bool_xor(int x,int y)
{
    return bis(bic(x,y),bic(y,x));
}

 

实例4:判断字符串是否包含重复字符

问题:实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).不能使用额外的数据结构。 (即只使用基本的数据结构)

解答:若字符为ASCII字符集合。则一个时间复杂度为O(n)的解法如下。

我们还可以通过位运算来减少空间的使用量。 用每一位表征相应位置字符的出现。对于ASCII字符,我们需要256位,即一个长度为8的int 数组a即可。这里的关键是要把字符对应的数字,映射到正确的位上去。比如字符’b’对应的 代码是98,那么我们应该将数组中的哪一位置为1呢?用98除以32,得到对应数组a的下标: 3。98对32取模得到相应的位:2。相应代码如下:

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;
}

更详细的关于字符串判重的解析见:1.1 判断一个字符串中的字符是否唯一

 

实例5:Bitmap应用

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。

问题实例:

1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。

    8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。 (可以理解为从0-99 999 999的数字,每个数字对应一个Bit位,所以只需要99M个Bit==1.2MBytes,这样,就用了小小的1.2M左右的内存表示了所有的8位数的电话)

2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。

    将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上,在遍历这些数的时候,如果对应位置的值是0,则将其置为1;如果是1,将其置为2;如果是2,则保持不变。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map,都是一样的道理。

 更详细的关于bitmap解析请见:海量数据处理面试题集锦

 

实例6:布隆过滤器(Bloom Filter)

Bloom Filter是一种空间效率很高的随机数据结构,它的原理是,当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。这就是布隆过滤器的基本思想。

但Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

问题实例:
给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?
 
根据这个问题我们来计算下内存的占用,4G=2^32大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。 现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。
 

更详细的关于布隆过滤器的解析请见:海量数据处理之Bloom Filter详解