关于位运算

确认实习offer之后,整个人懒了很多,加上忙着学校各种乱七八糟的事情,真是好久没写文章了。今天在小伙伴带动下准备开始刷点leecode陶冶下情操,顺便注意了一下其中的效率问题顺手记录

最开始的原题是一道智力题(leecode题号292,Nim Game),我做出的结果是

1
2
3
var canWinNim = function(n) {
return n % 4 !== 0;
}

通过,运算104ms,无聊之下看了下排行,c的效率果然不是一般的高,问小伙伴js有没有更高效写法,获得位运算の必杀技,总结一下常见技巧先。

以下是正题:

基本运算

乘以2的次方

1
2
3
return n << m;  //计算n*(2^m)
// eg.
return n << 1; // n*2

除以2的次方

1
2
3
return n >> m;  //计算n/(2^m)
// eg.
return n >> 1; // n/2

乘以2的m次方

1
2
//计算n*(2^m)  
return n << m;

除以2的m次方

1
2
//计算n/(2^m)  
return n >> m;

计算2的n次方

1
2
3
int getFactorialofTwo(int n){//n > 0  
return 2 << (n-1);//2的n次方
}

判断

判断一个数的奇偶性

1
return (n & 1) == 1;

判断符号是否相同

1
2
3
boolean isSameSign(int x, int y){ //有0的情况例外  
return (x ^ y) >= 0; // true 表示 x和y有相同的符号, false表示x,y有相反的符号。
}

判断一个数是不是2的幂

1
2
3
4
5
boolean isFactorialofTwo(int n){  
return n > 0 ? (n & (n - 1)) == 0 : false;
/*如果是2的幂,n一定是100... n-1就是1111....
所以做与运算结果为0*/

}

取值

取绝对值(某些机器上,效率比n>0 ? n:-n 高)

1
2
3
4
int abs(int n){  
return (n ^ (n >> 31)) - (n >> 31);
/* n>>31 取得n的符号,若n为正数,n>>31等于0,若n为负数,n>>31等于-1,若n为正数 n^0=0,数不变,若n为负数有n^-1 需要计算n和-1的补码,然后进行异或运算, 结果n变号并且为n的绝对值减1,再减去-1就是绝对值 */
}

取两个数的最大值(某些机器上,效率比a>b ? a:b高)

1
2
3
4
5
6
7
8
9
10
11
12
13
通用版
[cpp] view plain copy
int max(int a,int b){

return b & ((a-b) >> 31) | a & (~(a-b) >> 31);
/*如果a>=b,(a-b)>>31为0,否则为-1*/
}
C语言版
[cpp] view plain copy
int max(int x,int y){

return x ^ ((x ^ y) & -(x < y));
/*如果x<y x<y返回1,否则返回0,
、 与0做与运算结果为0,与-1做与运算结果不变*/

}

取两个数的最小值(某些机器上,效率比a>b ? b:a高)

1
2
3
4
5
6
7
8
9
10
11
// 通用
int min(int a,int b){
return a & ((a-b) >> 31) | b & (~(a-b) >> 31);
/*如果a>=b,(a-b)>>31为0,否则为-1*/
}
// C语言
int min(int x,int y){
return y ^ ((x ^ y) & -(x < y));
/*如果x<y x<y返回1,否则返回0,
与0做与运算结果为0,与-1做与运算结果不变*/

}

对2的n次方取余

1
2
3
4
5
int quyu(int m,int n){//n为2的次方  
return m & (n - 1);
/*如果是2的幂,n一定是100... n-1就是1111....
所以做与运算结果保留m在n范围的非0的位*/

}

求两个整数的平均值

1
2
3
4
5
6
7
8
9
10
11
int getAverage(int x, int y){  
return (x + y) >> 1;

另一种写法
[java] view plain copy
int getAverage(int x, int y){

return ((x ^ y) >> 1) + (x & y);
/*(x^y) >> 1得到x,y其中一个为1的位并除以2,
x&y得到x,y都为1的部分,加一起就是平均数了*/


}

二进制位的操作

  • 从低位到高位,取n的第m位

    1
    2
    3
    int getBit(int n, int m){  
    return (n >> (m-1)) & 1;
    }
  • 从低位到高位.将n的第m位置1

    1
    2
    3
    4
    5
    int setBitToOne(int n, int m){  
    return n | (1 << (m-1));
    /*将1左移m-1位找到第m位,得到000...1...000
    n在和这个数做或运算*/

    }
  • 从低位到高位,将n的第m位置0

    1
    2
    3
    4
    5
    int setBitToZero(int n, int m){  
    return n & ~(1 << (m-1));
    /* 将1左移m-1位找到第m位,取反后变成111...0...1111
    n再和这个数做与运算*/

    }

int相关

  • 获得int字节数

    1
    2
    3
    int getMaxInt(){  
    return ((unsigned int) - 1) >> 1;//2147483647
    }
  • 获得int型最大值

    1
    2
    3
    int getMaxInt(){  
    return (1 << 31) - 1;//2147483647, 由于优先级关系,括号不可省略
    }

另外一种写法:

1
2
3
int getMaxInt(){//有些编译器不适用  
return (1 << -1) - 1;//2147483647
}

  • 获得int型最小值
    1
    2
    3
    int getMinInt(){  
    return 1 << 31;//-2147483648
    }

另外一种写法:

1
2
3
int getMinInt(){//有些编译器不适用  
return 1 << -1;//-2147483648
}

其他

不用临时变量交换两个数

1
2
3
4
5
6
7
8
// C语言
void swap(int *a,int *b) {
(*a) ^= (*b) ^= (*a) ^= (*b);
}
// 通用
a ^= b;
b ^= a;
a ^= b;

另外一些可能没实质提升的写法:
计算n+1: -~n
计算n-1: ~-n
取相反数:~n + 1

最后,位运算基本常用的也总结得差不多。虽然通常在实际程序中用得不是很多,而且如果大面积使用对后期的可维护性是大大的降低。不过呢,学好位运算,理解一定的计算机基础知识对于编程而言还是很重要的呐(例如0.1+0.2 != 0.3之类的问题不用问搜索引擎就知道为什么了),还有,用位运算还可以很好的装逼(嗯..不过感觉大多妹子没兴趣,摊手~ >▽<)

最后的最后,回到最开始说的判断,小伙伴测试得出的return n%4 !== 0是102ms,,return !!(n&3)是97ms,return (n&3)>0;是92ms看到有80的提交,然后表示暂时还没想出其他更快的方法了(/ □ ),如有看到欢迎交流~