Bitwise swap without XOR

I need to swap two variables without both XOR and arithmetic operations. All I can use are bitwise operations like ~, &, |, <<, >>, etc.

I understand the XOR approach, but can't figure out the other way around this..

EDIT: Temporary variables are not allowed either.


Since XOR is a combination of ANDs and NOTs, all you need to do is implementing it in Java:

static int nand(int a, int b) {
    return ~(a & b);
}

static int xor(int a, int b) {
    return nand(nand(a, nand(a, b)), nand(b, nand(a, b)));
}

With this implementation in place, you can swap using XOR.


As shown in the answer of dasblinkenlight, an xor can be emulated with nand , consisting of not and and . Analogously, the xor can be emulated with nor , consisting of not and or .

The expressions will look a bit complex in the end...

public class XorTest
{
    public static void main(String[] args)
    {
        testNand();
        testNor();
    }

    private static void testNand()
    {
        int a = 1234;
        int b = 5678;

        a = xorNand(a, b);
        b = xorNand(b, a);
        a = xorNand(a, b);

        System.out.println(a);
        System.out.println(b);
    }

    private static void testNor()
    {
        int a = 1234;
        int b = 5678;

        a = xorNor(a, b);
        b = xorNor(b, a);
        a = xorNor(a, b);

        System.out.println(a);
        System.out.println(b);
    }

    private static int xorNand(int a, int b)
    {
        return ~(~(a & ~(a & b)) & ~(b & ~(a & b)));
    }

    static int xorNor(int a, int b)
    {
        return ~(~(~(a | a) | ~(b | b)) | ~(a | b));
    }
}

But I can't think of a way that does the same "only" with shifts or other "novel combinations of operators" - whatever this should mean, exactly...

链接地址: http://www.djcxy.com/p/58204.html

上一篇: XOR这两个数字在原地换?

下一篇: 按位交换,无XOR