The basic Fredkin gate is a controlled swap gate that maps three inputs onto three outputs . The "C" input is mapped directly to the "C" output. If "C" = 0, no swap is performed; maps to , and maps to . Otherwise, the two outputs are swapped so that maps to , and maps to . It is easy to see that this circuit is reversible, i.e., "undoes" itself when run backwards. A generalized "n"×"n" Fredkin gate passes its first "n"−2 inputs unchanged to the corresponding outputs, and swaps its last two outputs if and only if the first "n"−2 inputs are all 1.