黑马程序员技术交流社区

标题: 关于位置交换算法 [打印本页]

---

作者: cro    时间: 2012-6-8 11:58
标题: 关于位置交换算法
哪位能解释一下下面a与b是怎么实现位置交换的，求详细过程，我看了半天也没弄懂！多谢了！！

public class TestTalk {
public static void swapAb(int a, int b) {
  //以下位置交换算法怎么理解
   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}
public static void main(String[] args) {
  int i = 10, j = 5;
  TestTalk.swapAb(i, j);
  
  System.out.println(i); //测试时，i和j的输出值并没有看到交换位置！这是为什么！
  System.out.println(j);
}
}

---

作者: 田建    时间: 2012-6-8 12:10


首先你要知道，一个数异或同一个数两次还是这个数，第一步：a=a^b;(把a异或b的值赋给了a)；第二步：b=a^b;(此时的a已经是a^b的值，再异或b即等于了a，达到了把a赋给b的目的)；第三步：a=a^b;(此时的a等于a^b,而b等于a,因而此时的a^b=a^b^a=b,从而达到了把b赋给a的目的)！经过以上三步a和b的值就交换了，值进行交换的方式总共有3种，这只是一种技巧性方式，真正开发过程中记住第三方变量的方法才是最实用的！
而你下面的打印之所以没有交换，是因为，你打印的还是主函数中的i和j，你需要把两条打印语句放到swapAb( )里面去！

---

作者: 曹操    时间: 2012-6-8 12:10


我们先来回顾一下异或  

^ 异或 特点：同为假，异为真 规律：一个数同时异或这个数两次结果还是这个数。用于加密

所以这个就很好理解了哦

public class TestTalk {
public static void swapAb(int a, int b) {
  //以下位置交换算法怎么理解    //解答：^ 异或 特点：同为假，异为真 规律：一个数同时异或这个数两次结果还是这个数。用于加密


   a = a ^ b;
   b = a ^ b;
   a = a ^ b;
}
public static void main(String[] args) {
  int i = 10, j = 5;
  
   
   int a = a ^ b;
   b = a ^ b;
   a = a ^ b;
  System.out.println(i); //测试时，i和j的输出值并没有看到交换位置！这是为什么！   解答：因为swapAb方法返回值，或者直接把主函数的输出语句直接放swap（）方法里面，这是两个原因 两个解决办法
  System.out.println(j);
}



补充：异或的用法

相同输出0，不同输出1，例如：
System.out.println(1^1); 输出0
System.out.println(1^2)；输出3，因为最后2个低位都不一样，所有输出3

    异域的概念是相同为0不同为1.如果两个数值异或后的值相同，异或前可能不同。
比如二进制：0010^0001=0011 而0000^0011=0011。 异或要慎用。

---

作者: 黑马罗坚    时间: 2012-6-8 12:13
public class TestTalk {
public static void swapAb(int a, int b) {
  //以下位置交换算法怎么理解
   a = a ^ b;                  
   b = a ^ b;              
   a = a ^ b;
}
public static void main(String[] args) {
  int i = 10, j = 5;  
  TestTalk.swapAb(i, j);  //这里有问题哦  传递的是副本哦 这里的i 和j没有改变
  
  System.out.println(i); //测试时，i和j的输出值并没有看到交换位置！这是为什么！
  System.out.println(j);
}
}

---

作者: 黑马罗坚    时间: 2012-6-8 12:16
用异或注意下自己跟自己交换变量的值为0  

---

作者: 李文富    时间: 2012-6-8 12:18
package temp;
public class TestTalk {
public static void swapAb(int a, int b) {
  //以下位置交换算法怎么理解
   a = a ^ b;
   /*
     0000 1010
     0000 0101
     ----------
     0000 1111*/
   b = a ^ b;
/*   0000 1111
     0000 0101
     -------------
     0000 1010
*/ a = a ^ b;
/*   0000 1111
     0000 1010
    ---------------
     0000 0101
     */
}
public static void main(String[] args) {
  int i = 10, j = 5;
  // 10 (0000 1010) 5(0000 0101) 二进制
  TestTalk.swapAb(i, j);
  
  System.out.println(i); //测试时，i和j的输出值并没有看到交换位置！这是为什么！
  System.out.println(j); //因为只是进行了值传递；并没有返回修改后值的引用；
  
}
}
//就是使用异或进行位操作； 上面 注释只写了2个字节；int型是 4个字节的 ，省略没有 写出来

---

作者: 吴小铁你好    时间: 2012-6-8 12:31
你输出语句放错位置了，你要知道赋值语句的存储方式。

1. package pack;
   
2. 
   
3. public class TestTalk {
   
4. public static void swapAb(int a, int b) {
   
5.   //以下位置交换算法怎么理解
   
6.    a = a ^ b;
   
7.    b = a ^ b;
   
8.    a = a ^ b;
   
9.    System.out.println(a); //测试时，i和j的输出值并没有看到交换位置！这是为什么！
   
10.    System.out.println(b);
    
11. }
    
12. public static void main(String[] args) {
    
13.   int i = 10, j = 5;
    
14.   TestTalk.swapAb(i, j);
    
15.   
    
16.   
    
17. }
    
18. }
    

复制代码

---

作者: 杨天皓    时间: 2012-6-8 12:39

你记着一句：一个数同时异或另一个数两次,那么结果还是这个数
a = a ^ b;                  
b = a ^ b;  //到这里时,a已经被赋值是(a^b)  那么这个表达式的完整写法就是  b = a^b^b   结果b = a              
a = a ^ b; // 同上,这个完整的写法就是  a = a^a^b   那么结果就是a = b;   
这样就形成互换了.

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2