V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
wumingxiaoQ
V2EX  ›  Java

谁给讲下下下面的算法是怎么个原理 没看懂( Java 异或)

  •  1
     
  •   wumingxiaoQ · 2017-11-16 17:57:15 +08:00 · 1950 次点击
    这是一个创建于 2324 天前的主题,其中的信息可能已经有所发展或是发生改变。
    java 的位运算符中有一个叫异或的运算符,用符号(^)表示,其运算规则是:两个操作数的位中,相同则结果为 0,不同则结果为 1。下面看一个例子:
    public class TestXOR{
    public static void main(String[] args)
    {
    int i = 15, j = 2;
    System.out.println("i ^ j = " + (i ^ j));
    }
    }
    运行结果是:i ^ j = 13.
    分析上面程序,i=15 转成二进制是 1111,j=2 转成二进制是 0010,根据异或的运算规则得到的是 1101,转成十进制就是 13.
    利用这个规则我们可以灵活运用到某些算法。比如,假定有 2K+1 个数,其中有 2k 个相同,需要找出不相同的那个数,比如:2、3、4、4、3、5、6、6、5。我们利用异或运算符就可以这样写:
    public class TestXOR{
    public static void main(String[] args)
    {
    int[] array = {2,3,4,4,3,5,6,6,5};
    int v = 0;
    for (int i = 0;i < array.length;i++) {
    v ^= array[i];
    }
    System.out.println("只出现一次的数是:" + v);
    }
    }
    结果是:只出现一次的数是 2.
    我们就是巧用异或运算符的规则,得出一个数和 0 异或还是自己,一个数和自己异或是 0 的原理。


    原文地址: http://blog.csdn.net/renjie_998003/article/details/50738025


    不理解 for 循环出来的为什么是只出现一次的数字
    5 条回复    2017-11-28 10:05:41 +08:00
    crab
        1
    crab  
       2017-11-16 18:25:41 +08:00
    v 都被重新赋值了,怎么可能。
    hustlike
        2
    hustlike  
       2017-11-16 20:07:00 +08:00
    因为相等的两个数字 异或的结果是 0 . 0 异或 任何数 x = x

    a a b b c c d => a ^ a ^ b ^ b ^ c ^ c ^ d => 0 ^ d => d
    neosfung
        3
    neosfung  
       2017-11-16 21:37:34 +08:00 via iPhone
    #2 正解
    ffkjjj
        4
    ffkjjj  
       2017-11-24 22:23:48 +08:00 via iPhone
    @neosfung 要是相同的元素有奇数个呢…… a^a^a^b^b^b
    artyama
        5
    artyama  
       2017-11-28 10:05:41 +08:00
    这个算法告诉我们,“解铃还须系铃人”。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   5411 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 923ms · UTC 07:50 · PVG 15:50 · LAX 00:50 · JFK 03:50
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.