Bitwise swap without XOR

Question

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.

@Fallen, Yes, I think I can. I was wondering if there is a fundamentally different approach, not just a replacing XOR with more basic operators and using XOR-exchange all over again. Maybe something allowing shifts or more novel combinations of operators. — parsecer, Feb 12 '17 at 01:29

score 2 · Accepted Answer · edited May 23 '17 at 10:30

2

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.

edited May 23 '17 at 10:30

Community

1
1

answered Feb 12 '17 at 01:20

Sergey Kalinichenko

714,442
84
1,110
1,523

1

But are you allowed to use a temporary variable? I mean, if you could do that, you could just swap them directly. – D M Feb 12 '17 at 01:24
So if you take the temporary variable out of this answer, you're left with `return nand(nand(a, nand(a, b)), nand(b, nand(a, b)));`. – D M Feb 12 '17 at 01:27
1

@DM That's just for convenience - one can replace `nab` with a call to `nand(a, b)` in both places where it is used, and be done with it. Obviously, it does not matter anyway, because it's a learning exercise designed to teach students that XOR can be modeled with other operations. – Sergey Kalinichenko Feb 12 '17 at 01:27
1

@dasblinkenlight: Given your last comment, do you feel you have helped or hindered the learning of OP? Just asking... :) – rici Feb 12 '17 at 01:35
@rici Helped, of course: I was taught this trick in a class on integrated circuits back in the eighties; good chances are, OP has not taken this class (I am not sure it's offered anywhere these days). I also think that this trick is about as useful as the knowledge of designing with vacuum tubes :-) – Sergey Kalinichenko Feb 12 '17 at 01:40
@dasblinkenlight: Definitely agree about the utility of the trick; indeed, it may be even less useful. But I sometimes wonder if we're underestimating the importance of figuring things out for yourself. – rici Feb 12 '17 at 02:29
@dasblinkenlight, Thank you. I indeed didn't take a circuits classes and I appreciate your willingness to help. – parsecer Feb 12 '17 at 04:04

score 1 · Answer 2 · edited May 23 '17 at 11:46

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...

Bitwise swap without XOR

2 Answers2