I want to fly higher
programming Explorer
posts - 112,comments - 263,trackbacks - 0
        今天复习C语言的时候,看到位运算这章。记得以前学习C语言的时候,都没怎么关注这一章。只是记得几个位运算符,&:按位与,|:按位或,^:按位异或,~:取反,<<:左移,>>:右移,知道其中的含义罢了。不过当看完这一章,确实是受益匪浅。尤其是利用”异或“运算,实现交换两个值,而不用临时变量。
        通常我们交换两个值,都是用一个临时的变量temp,拿交换a,b的值为例,通常的做法是:temp = a;a = b;b = temp;不过利用位运算,真的是方便很多:
        假如 a = 3,b = 4。想将a和b的值互换,可以用一下赋值语句实现:

        a = a ^ b;
        b = b ^ a;
        a = a ^ b;

        下面用竖式进行简单说明:(10进制化为二进制)
    
        a = 011
(^)    b = 100
则    a = 111(a ^ b的结果赋值给a,a已变成了7)
(^)    b = 100
则    b = 011(b^a的结果赋给b,b已经变成了3)
(^)    a = 111
则    a = 100(a^b的结果赋给a,a已经变成了4)    

        从上面的竖式可以清楚的看到利用异或运算实现两个值交换的基本过程。
       
        下面从深层次剖析一下:

        1.对于开始的两个赋值语句,a = a ^ b,b = b ^ a,相当于b = b ^ (a ^ b) = a  ^ b ^ b,而b ^ b 显然等于0。因此b = a ^ 0,显然结果为a。
        2. 同理可以分析第三个赋值语句,a = a ^ b = (a ^ b) ^ a = b

        注:1.^ 即”异或“运算符。它的意思是判断两个相应的位值是否为”异“,为”异"(值不同)就取真(1);否则为假(0)。
                2.^运算符的特点是与0异或,保持原值;与本身异或,结果为0。
posted on 2010-03-12 18:18 landon 阅读(5785) 评论(8)  编辑  收藏 所属分类: Program

FeedBack:
# re: 交换两个值,不用临时变量(C位运算)
2010-04-01 19:05 | sysubo
用这么麻烦么?
a = a + b;
b = a - b;
a = a - b;  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)
2010-04-01 20:04 | landonlv
哈哈,我今天的面试题就是这个。赞一个。@sysubo
  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)
2012-07-18 02:47 | zminds
@sysubo
a+b或者a-b超出表示范围的时候就不能这么用了  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)
2013-04-12 17:11 | 老何
这个算法在a==b的情况下会出错,因为 a ^ b=a^a=0,同理后面都会算出0,所以这里要对a==b的情况做特殊处理  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)[未登录]
2013-04-15 11:07 | K
@老何
a = b = 2;
a ^= b; //a = 0
b ^= a; //b = b ^ 0;b = b = 2
a ^= b; //a = 0 ^ b;a = b = 2

你说的情况是函数传参时的地址相同  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)
2014-08-04 14:36 | cch
@sysubo
位运算比加减快
当然任何互逆的运算都是可以的  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)
2014-08-04 14:40 | cch
@老何
不会出错。
例:a=b=5;
a=a^b=5^5=0
b=b^a=5^0=5
a=a^b=0^5=5  回复  更多评论
  
# re: 交换两个值,不用临时变量(C位运算)[未登录]
2016-06-16 20:49 | 123
#include<stdio.h>
void swap(int *a, int *b)
{
*a = (*a) ^ (*b);
*b = (*a) ^ (*b);
*a = (*a) ^ (*b);
}
int main(void)
{
int a, b;
printf("please input two integers for example\n");
scanf("%d %d",&a,&b);
printf("Before swap a = %d, b = %d\n",a,b);
swap(&a,&b);
printf("After swap a = %d, b = %d\n",a,b);
}
  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: