手机版
你好,游客 登录 注册
背景:
阅读新闻

来谈谈C++ 位运算 & | << >> ^ ~ %

[日期:2014-03-17] 来源:Linux社区  作者:fox64194167 [字体: ]

老实说,我对+ = * / % && || ==一些比较简单的运算符比较熟悉。对位运算就陌生了,主要用的少。我觉得高手用的会比较多,因为位运算速度比较快。位运算应该适用于大多数的语言,不限于c++

 

1.&

 

如果两个相应的二进制位都为1,则该位的结果值为1;否则为0。

注:下面都用8位的 unsigned char 来做例子。

 

目录 [隐藏]

&简单举例:
&比较实用的例子:
2. |
| 简单例子:
| 比较实用的例子
3. << 向左移位移
4. >> 向右位移
5. ^ 异或
6 ~
7 再扯下%
8.位运算优先级
&简单举例:
 

11&3  = 3

 

    00001011

&  00000011

=  00000011 = 3

 

&比较实用的例子:
比如我们经常要用的是否被2整除,一般都写成  if(n % 2 == 0)

可以换成 if((n&1) == 0)

 

2. |
 

如果两个相应的二进制位只要有一个是1,结果就是1;否则为0。

 

| 简单例子:
 

11 | 3 = 11

    00001011

|    00000011

=  00001011 = 11

 

| 比较实用的例子
可以用一个unsigned int 来存储多个布尔值。比如一个文件有读权限,写权限,执行权限。看起来要记录3个布尔值。我们可以用一个unsigned int也可以完成任务。

 

一个数r来表示读权限,它只更改个位来记录读权限的布尔值

00000001  (表示有读权限)

00000000  (表示没有读权限)

 

一个数w表示写权限,它只用二进制的倒数第二位来记录布尔值

00000010 (表示有写权限)

00000000 (表示没有写权限)

 

一个数x表示执行权限,它只用倒数第三位来记录布尔值

00000100 (表示有执行权限)

00000000 (表示没有执行权限)

 

那么一个文件同时没有3种权限就是

~r | ~ w | ~ x 即为 00000000,就是0

 

只有读的权限就是

r | ~w | ~x 即为 00000001,就是1

只有写的权限就是

~r | w | ~x 即为 00000010,就是2

一个文件同时有3种权限就是

r | w | x 即为 00000111,就是7

 

3. << 向左移位移
 

<<简单例子(向左移一位,右边自动补0)

11 << 1 = 22

  00001011 << 1

  00010110 = 22

相当于二进制的每个数都变成当前值的两倍,结果就是变成当前值的两倍。

n * 2 == (n << 1)

推广下就是(注意可能会溢出)

 

 

4. >> 向右位移
 

>>简单例子(向右移一位,左边自动补1)

11 >> 1 =  5

00001011 >> 1

00000101 = 5

注意到最后一位的1被干掉了。

比较实用的例子是:

int n = n / 2    等价于  int n = n >> 1  等价于 int n >>= 1

 

 

5. ^ 异或
 

两个相同的数会变成0,反之是1

例子:

11^3 = 8

    00001011

^  00000011

=  00001000 = 8

 

我觉得理解异或,一定要用异或来解下面的题目:

Given an array of integers, every element appearstwice except for one. Find that single one.

就是一个数组中,所有数字都出现了两次,只有一个没有

比如 int t = {1,2,3,3,2,1,5} 要找到5。

用异或就完美了,所有相同的都会消失,留下来的就是5了。我发现异或是嫉妒成双成对的。

int singleNumber(int A[], int n) {
for(int i = 1; i < n; ++i){
A[0] ^= A[i];
}
return A[0];
}

还有就是用不tmp值来交换两个数

//不用temp交换两个整数
void swap(int& x , int& y)
{
x ^= y;
y ^= x;
x ^= y;
}

扯点别的,^在lua中表示pow的意思,这是要逆天。

 

6 ~
 

这个在加法中用到

x-y = x + ~y + 1

所以~y = – y  -1

 

比如 ~11 = -11 -1 = -12

 

7 再扯下%
 

居然有道题目是这样的: 求 100 % 8的 优化解法。我们知道:

8刚好是2的3次方

所以 100 % 8 == 100 – math.floor(100 / 8) * 8 == 100 -  ((100 >> 3) << 3)

 

8.位运算优先级
 

总的来说比较低,一定要加括号。

linux
本文评论   查看全部评论 (1)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的���事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款
第 1 楼
* 匿名 发表于 2017/3/14 7:01:18
错了,错了,第四点向右唯一应该是高位补“0(零)”不是“1”啊!!!“>>简单例子(向右移一位,左边自动补1)”