位运算小结操作-阿里云开发者社区

开发者社区> 人工智能> 正文
登录阅读全文

位运算小结操作

简介:

一、前言


输入2 的n 次方: 

如果突然要你输入2 的19 次方,你是不是还要想一下呢?敲个524288 多累啊。用位运算:1 << 19 又快又准。

乘除2 的倍数: 
千万不要用乘除法,非常拖效率。只要知道左移1 位就是乘以2 ,右移1 位就是除以2 就行了。
比如要算 25 * 4 ,用25 << 2 就好啦。

判断偶数: 
a % 2
 取模是最常用的判断方法之一。这样要用到除法运算,不好。实际上,还是用位运算解决:a & 1 。效果和a % 2 是一样的,但是要快得多。

对2 的倍数取模: 
类似上面的方法。对2 的倍数取模,只要将数与2 的倍数-1 做与运算就可以了。如:
a % 8 = a & (8-1)
节省乘除法可以提高效率。

判断一个整数是否是处于 0-65535 之间(常用的越界判断): 
用一般的 (a >= 0) && (a <= 65535) 可能要两次判断。
改用位运算只要一次:
a & ~((1 << 16)-1)
后面的常数是编译时就算好了的。其实只要进行一次与运算就行了。

算掩码: 
比如一个截取低6 位的掩码:0x3F
用位运算这么表示:(1 << 6) - 1
这样也非常好读取掩码,因为掩码的位数直接体现在表达式里。



二、位运算符

位运算方法有七种:

 

  与运算: 当两个位都为1 时结果为1 ,其它为0 。

|  或运算: 当两个位都为0 时结果为0 ,其它为1 。

^  异或运算: 当两个位数值不同时结果为1 ,相同为0 。

~  非运算( 求补) : 位的值为1 时结果为0 ,位的值为0 时结果为1 。

<< 左移运算: 右边空出的位上补0 ,左边的位将从字头挤掉,其值相当于乘2。

>>  右移运算: 右边的位被挤掉。对于左边移出的空位,如果是正数则空位补0,若为负数,可能补0 或补1 ,这取决于所用的计算机系统。

>>>   无符号右移运算: 右边的位被挤掉,对于左边移出的空位一概补上0 。



三、位运算应用口诀

清零取反要用与,某一位置可用或。

若要取反和交换,轻轻松松用异或。



四、需要注意的问题

1
 、优先级

移位运算符, 单目取反运算符的优先级比比较运算符高。但是“& ”、“|”和“^ ”的优先级是比比较运算符低的,这点一定要注意。

如6 & 6 > 4 的结果是0 , 而不是 true 。(6 & 6) > 4 的结果才是true ,所以要注意勤加括号。


2
 、速度

位运算的速度是非常快的,你甚至可以忽略他的耗时,但是毕竟操作肯定是有耗损的。所以,应该尽量使用

“^= ”、“|= ”和“&= ”这样的操作,比如说a ^= b , 速度比 a = a ^ b快,因为前者是直接在a 上进行操作,而 a = a ^ b 的第二个a ,是一个a 的副本,可见在操作中程序对a 复制了一次,运算的结果又对原来的a 做了一次赋值


3
 、范围

要当心移位运算时发生范围溢出。


4
 、位数不同的运算数之间的运算规则

  C 语言中,位运算的对象可以是整型(int )和字符型(char )数据。整形数据可以直接转化成二进制数,字符型数据在内存中以它的ASCII 码值存放,也可以转化成二进制数。当两个运算数类型不同时,位数亦会不同。遇到这种情况,系统将自动进行如下处理:将两个运算数右端对齐,再将位数短的一个运算数往高位扩充,即:无符号数和正整数左侧用0 补全; 负数左侧用1 补全;然后对位数相等的两个运算数,按位进行运算。



五、位运算的应用( 源操作数s ,掩码mask) 

1 
、按位与 &

清零特定位(mask 中特定位置0 ,其它位为1 ,s=s&mask )

取某数中指定位(mask 中特定位置1 ,其它位为0 ,s=s&mask )

 

2 、按位或 |

常用来将源操作数某些位的数值置1 ,其它位不变。(mask 中特定位置1 ,其它位为0 ,s=s|mask )

 

3 、位异或 ^

使特定位的值取反(mask 中特定位置1 ,其它位为0 ,s=s^mask )

不引入第三变量,交换两个变量(a ,b )的值

a = a ^ b;

b = a ^ b;

a = a ^ b;



六、二进制补码运算公式

-x = ~x+1 = ~(x-1)
~x = -x-1
-(~x) = x+1
~(-x) = x-1
x+y = x-~y-1 = (x|y) + (x&y)
x-y = x+~y+1 = (x|~y) - (~x&y)
x^y = (x|y) - (x&y)
x|y = (x&~y) + y
x&y = (~x|y) - ~x
x==y : ~(x-y|y-x)
x!=y : x-y|y-x
x< y : (x-y)^((x^y)&((x-y)^x))
x<=y : (x|~y)&((x^y)|~(y-x))
x< y : (~x&y)|((~x|y)&(x-y))      
// 无符号x,y 比较
x<=y : (~x|y)&((x^y)|~(y-x))      // 无符号x,y 比较



七、应用举例


01
 、判断int 型变量a 是奇数还是偶数

a&1 = 0 偶数

a&1 = 1 奇数

02
 
、取int 型变量a 的第k 位 (k=0,1,2 ……sizeof(int)) ,即a>>k&1

03 、将int 型变量a 的第k 位清0 ,即a=a&~(1<<k)

04 、将int 型变量a 的第k 位置1 , 即a=a|(1<<k)

05 、int 型变量循环左移k 次,即a=a<<k|a>>16-k ( 设sizeof(int)=16)

06 、int 型变量a 循环右移k 次,即a=a>>k|a<<16-k (设sizeof(int)=16)

07 、整数的平均值

对于两个整数x 、y ,如果用 (x+y)/2 求平均值,会产生溢出,因为 x+y 可能会大于INT_MAX ,但是我们知道它们的平均值是肯定不会溢出的,我们用如下算法:

int average(int x,int y) // 返回X,Y 的平均值

{

    return (x&y)+((x^y)>>1);

}

08
 
、判断一个整数是不是2 的幂

对于一个数 x >= 0 ,判断它是不是2 的幂

boolean power2(int x)

{

    return ((x&(x-1))==0)&&(x!=0);

}

09
 
 不用 temp 交换两个整数

void swap(int x,int y)

{

  x ^= y;

  y ^= x;

  x ^= y;

}

10
 
、计算绝对值

int abs( int x )

{

    int y;

    y = x >> 31;

    return (x^y)-y ;  // 或者return (x+y)^y;

}

11
 
、取模运算转化成位运算 ( 在不产生溢出的情况下)

a % (2^n) 等价于 a & (2^n - 1)

12
 
、乘法运算转化成位运算 ( 在不产生溢出的情况下)

a * (2^n) 等价于 a<< n

13
 
、除法运算转化成位运算 ( 在不产生溢出的情况下)

a / (2^n) 等价于 a>> n

例: 12/8 == 12>>3

14
 
、a % 2 等价于 a & 1

15 、

if(x==a)

    x=b;

else

    x=a;

等价于

x=a^b^x;

16
 
、x 的相反数表示为(~x+1)



八、实例

   

功能

示例

位运算

去掉最后一位

101101->10110

x >> 1

在最后加一个0

101101->1011010

x < < 1

在最后加一个1

101101->1011011

x < < 1+1

把最后一位变成 1

101100->101101

x | 1

把最后一位变成 0

101101->101100

x | 1-1

最后一位取反

101101->101100

x ^ 1

把右数第 k位变成 1

101001->101101(k=3 )

x | (1 < < (k-1))

把右数第 k位变成 0

101101->101001(k=3 )

x & ~ (1 < < (k-1))

右数第 k 位取反

101001->101101(k=3 )

x ^ (1 < < (k-1))

取末三位

1101101->101

x & 7

取末 k 位

1101101->1101(k=5 )

x & ((1 < < k)-1)

取右数第 k位

1101101->1(k=4 )

x >> (k-1) & 1

把末k 位变成1

101001->101111(k=4 )

x | (1 << k-1)

末k 位取反

101001->100110(k=4 )

x ^ (1 << k-1)

把右边连续的1 变成0

100101111->100100000

x & (x+1)

把右起第一个0 变成1

100101111->100111111

x | (x+1)

把右边连续的0 变成1

11011000->11011111

x | (x-1)

取右边连续的1

100101111->1111

(x ^ (x+1)) >> 1

去掉右起第一个1 的左边

100101000->1000

x & (x ^ (x-1))

判断奇数

(x&1)==1

 

判断偶数

(x&1)==0

 

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章
最新文章
相关文章