Chinaunix首页 | 论坛 | 博客
  • 博客访问: 648969
  • 博文数量: 45
  • 博客积分: 931
  • 博客等级: 准尉
  • 技术积分: 590
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-17 13:27
文章分类

全部博文(45)

文章存档

2013年(6)

2012年(15)

2011年(23)

2005年(1)

分类: Java

2011-11-21 18:57:20

今天无意之中发现了一个关于异或运算的一个有趣的现象。

假设函数f(n)是自然数1,2,3,...,n的所有数的异或,即f(n)=1^2^3^...^n, 那么,任意的n(n为自然数),我们能够很快的计算出f(n)的值
  
  1. if n == 4*m, then f(n) = n
  2. else if n == 4*m + 1, then f(n) = 1
  3. else if n == 4*m + 2, then f(n) = n+1
  4. else n = 0

其中m为整数,哈哈这个公式是不是很简单呢?公式的证明可以采用数学归纳法,这儿就不啰嗦了。

另外,异或的一些基本的性质:

1. 交换律
2. 结合律
3. x^x = 0, 0^x=x, a^b^a=b

利用异或的这些性质,我们可以在不需要任何额外空间的情况下交换两个变量的值:
方法如下:利用异或交换整数a,b的值

  1. a ^= b;
  2. b ^= a;
  3. a ^= b;
是不是看上去很绕啊? 其实原理很简单,

  1. new_b = (a^b)^b = a^b^b = a^(b^b) = a^0 = a
  2. new_a = (a^b)^a = a^b^a = a^a^b = (a^a)^b = 0^b = b
这下明白了吧?

一道有趣的题目:

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现
一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空
间,能否设计一个算法实现?


这题一个很简单的解法是将1001个数相加再减去1-1000的和,但是如果数据更大可能导致计算的和太大而溢出。 但是如果用异或运算则不会有这个担心,方法也很简单,可以先想一想了。

方法: 将1001个数进行异或,在与1-1000的异或进行异或。 即 x = (1001个数的异或)^ (1^2^3^...^1000), 计算1-1000的异或就可以采用我上面提到的公式了,很简单的。

下面一道更加复杂一点的题目:

有N个整数,除了其中的两个数只出现一次以外,其余的所有的数都正好出现两次,如何用最快的方法求出只出现一次的两个数,要求空间复杂度是O(1).

大家可以思考一下。

阅读(5619) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~