巧用位运算

发表于

在设计算法的时候通过位运算可减小操作的时间复杂度，甚至是空间复杂度，同时也能够减少代码，让代码片看起来更为简洁。

先看第一个问题

设计一个算法，判断一个整数是不是2的n(n>=0)次方。

传统的思路如下，通过穷举法逐个判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
boolean isPowOfNN(int number) {
    if (number ==0) {
        return false;
    } else if (number ==1) {
        return true;
    }
    int i = 1;
    while (i<=number/2) {
        if (Math.pow(2, i) == number) {
            return true;
        }
        i++;
    }
    return false;
}

这样设计算法的话，循环的每一次都要先进行一次幂运算，然后再和要处理的数比较，如果要处理的整数很大，无疑运行起来效率不是很高。

现在看看加入位操作的算法是什么样子的。

1
2
3
4
5
6
7
8
9
boolean isPowOfN(int number) {
    if (number ==0) {
        return false;
    } else if (number ==1) {
        return true;
    }
    return (number & (number-1)) != 0;
}

主要代码 return (number & (number-1)) != 0 只有一句话，是不是很简洁？
先对number和number-1进行与操作，判断结果是否为0,为0的话返回true,不为0则返回false。

具体原理是这样。通过观察我们得知，一个等于2的n次幂的数转换为二进制都有这样一个特征： 只有最高位为1,其余的低位全部为0,我们假设 number 是16，转换为二进制为 1 0000 , 那么number-1 即15转换为二进制为 1111 ,两者进行与运算结果必然为0。如果number不等于2的n次幂，假设number为12,其二进制为 1100，number-1即11则为1011，两者进行与运算结果肯定不为0。只要number不等于2的n次幂，那么number&(number-1)的结果就不为0。

再看另外一个问题

对于任意一个整数，把其转换成二进制，求它包含的1的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 int countOne(int number){
    int count = 0 ;
    if (number < 0) {
        number = -number;
        count++;  // 负数比正数多一个1
    }
    while (number > 0) {
        if ((number&1) == 1) {
            count++;
        }
        number=number>>1;
    }
    return count;
}

对于负数，我们要先换算为正数，而且它比与它绝对值相等的整数多了一个1。先把它与1进行与运算，如果它最低位上是1的话，结果必然为1。如果为1,则 count++ ,接着右移1位，相当于丢掉最低位，再将其与1作与运算，如此循环，直到这个数为0为止。

对于比较字符串的问题

给定一个字符串，假设全部的字符都在 a~z 之间，设计一个算法判断该字符串是否所有的字符都不相同。

对于这个问题，我们先新建一个临时变量存放字符串里每个字符的信息。对于一个32位的整型变量而言，足够存放26的英文字符的数据信息。由于每个字符的信息不一样，如果字符串包含某个字符，就把处理后的信息写入到临时变量里。先将这个字符的值减去 ‘a’ ，得到一个差值offset，将1左移offset位，对于 int offset = str.charAt(i)-‘a’ ,如果字符为 ‘a’ ,那么得到移位后的值为1,如果是‘b’，得到的值是2,这样对于临时变量temp而言，从低到高的第一位、第二位…将分别存储字符 ’a‘、’b’… 的信息。每次将此变量与字符经过处理后得到的值进行比较，如果比较结果大于0,说明字符串至少包含两个同样的字符。

1
2
3
4
5
6
7
8
9
10
11
boolean isDiffStr(String str) {
    int temp = 0;
    for(int i=0; i<str.length(); i++) {
        int offset = str.charAt(i)-'a';
        if ((temp & (1<<offset)) > 0) {
            return false;
        }
        temp |= (1<<offset);
    }
    return true;
}