Here's a design challenge/puzzle for anyone that might be interested.

Imagine that you are tasked with producing the bitwise XOR of two multi-bit words. For simplicity, let's make them 8-bit words and call them X and Y.

We are therefore trying to get

Z = X xor Y

Here's the catch: You are given a box that has two 8-bit cascadable adders (i.e., have a carry-in and a carry-out) and eight two-input NAND gates -- perhaps four 74xx283 4-bit full adders and two 74xx00 quad NAND gates, to give something concrete. This is all you have.

Can you produce Z using just these parts?

 

one you can do anything using just NAND gates (though it would need more than offered).
so given parts limitation and without thinking deep about it, it is probably 2s complement trick.
for example i use all the time Z=A AND (-A) to see least significant set bit in a word

 

The solution definitely involves exploiting two's complement.

 

Use 4 pieces of 74x283 to have a 16-bit full adder, with carry inputs tied to GND. Connect the 8 pairs of inputs to the 8 ODD the adder bits' inputs, and tie the 8 EVEN adder bits' inputs to GND. The 8 ODD adder bits' outputs are the bit-wise XORs of two 8-bit input words. Without carry in, a single adder bit's sum is an XOR of the two input bits. As we tie the EVEN adder bits' inputs to GND, no carry will be generated from these bits to propagated to the next (odd) bit.

 

Use 4 pieces of 74x283 to have a 16-bit full adder, with carry inputs tied to GND. Connect the 8 pairs of inputs to the 8 ODD the adder bits' inputs, and tie the 8 EVEN adder bits' inputs to GND. The 8 ODD adder bits' outputs are the bit-wise XORs of two 8-bit input words. Without carry in, a single adder bit's sum is an XOR of the two input bits. As we tie the EVEN adder bits' inputs to GND, no carry will be generated from these bits to propagated to the next (odd) bit.

Not the solution I had in mind, but it should work just fine.

See if you can figure out another way that would also lend itself to being done programmatically. The problem with this approach, in that regard, is that it is very inefficient to spread the bits out.

Minor point, if all of the carry inputs are tired to GND, then you don't have a 16-bit full adder. But that's neither here nor there in this case, as you don't need to cascade them at all. You are simply using two non-adjacent inputs from each 4-bit adder in order to access just the XOR functionality in that channel.

This is actually faster and more efficient than the solution I was trying to steer people towards, so let me narrow things a bit by requiring that all parts provided must be used in a non-trivial way.

 

Thanks for the hint. We can use the following equations:
A^B = A+B-2(A&B)
= A+B+~((A&B)<<1)+1
= A+B+(~(A&B)<<1+1)+1
For 8-bit words A and B, use a 8-bit adder. This is two cascaded 74x283s with CARRY-In tied to 1'b0.
S[7:0] = A[7:0] + B[7:0]
Make a 7-bit NAND, using two 74x00s.
N[7:1] = ~(A[6:0] & B[6:0])
N[0] = 1'b1
Use a second 8-bit adder, with CARRY-In tied to 1'b1, and
XOR[7:0] = S[7:0] + N[7:0]

 

Thanks for the hint. We can use the following equations:
A^B = A+B-2(A&B)
= A+B+~((A&B)<<1)+1
= A+B+(~(A&B)<<1+1)+1
For 8-bit words A and B, use a 8-bit adder. This is two cascaded 74x283s with CARRY-In tied to 1'b0.
S[7:0] = A[7:0] + B[7:0]
Make a 7-bit NAND, using two 74x00s.
N[7:1] = ~(A[6:0] & B[6:0])
N[0] = 1'b1
Use a second 8-bit adder, with CARRY-In tied to 1'b1, and
XOR[7:0] = S[7:0] + N[7:0]

You got it!

The only question (which I doubt applies to you) is whether the starting equation is something that is understood, or just something that is just pulled from the Internet, probably in the form:

A+B = (A^B) + 2(A&B)

Where this comes from, and its validity, is not at all obvious. Even when looking at the structure of a half-adder or a full-adder.

It is often stated that this equation translates between arithmetic and logical operations, but it really doesn't since the two classes of operations are not separated with arithmetic operations exclusively on one side and logical operations exclusively on the other.

 

In the best tradition of obfuscated C, we have:

z=1+x+(~(x&y)<<1|1)+y;

 

It would be helpful to think backwards, how to reach from XOR[7:0] to SUM[7:0]. Each bit produces a partial sum bit s=a^b and a partial carry-out bit cout=a&b. But the carry-out-bit has one higher power, ie, it goes to the next higher bit, or *2 arithmetically. Combining these partial sum bits and carry-out bits, we get
SUM[7:0] = XOR[7:0] + 2*CARRYOUT[6:0] = XOR[7:0] + 2*(A[6:0] & B[6:0])

 

It would be helpful to think backwards, how to reach from XOR[7:0] to SUM[7:0]. Each bit produces a partial sum bit s=a^b and a partial carry-out bit cout=a&b. But the carry-out-bit has one higher power, ie, it goes to the next higher bit, or *2 arithmetically. Combining these partial sum bits and carry-out bits, we get
SUM[7:0] = XOR[7:0] + 2*CARRYOUT[6:0] = XOR[7:0] + 2*(A[6:0] & B[6:0])

What trips most people up when trying to analyze this is the cascading nature of the carries. They tend to think that the equation involving the XOR and the AND somehow eliminates this (because that is what they think that the presence of bitwise operations "should" do), without realizing that the arithmetic addition of the two preserves that propagating behavior.

 

the only reasonable cause to put effort on this is . . . when the listed devices are a leftover of the remaining design . . .
one must realize such as an impossible (read extremely rare) occasion . . .
. . . further on the implementation of such may require excess board space (design cost) and longer routings than a dedicated approach & introduce extra delay and/or chance of an interference . . . increase power demand (incase of cmos the idle gates draw almost no power)
? what's your question . . .

(((( otherwise it's obvious that iterleaved odd/even bits give you xor ))))

 

What trips most people up when trying to analyze this is the cascading nature of the carries. They tend to think that the equation involving the XOR and the AND somehow eliminates this (because that is what they think that the presence of bitwise operations "should" do), without realizing that the arithmetic addition of the two preserves that propagating behavior.

Your stated problem is very contrived, an arbitrary set of components that can be used to produce the result. You could just alter that chosen set slightly and ask it again.

More instructive would be to prove if some set of gates, can or cannot be used to reach the desired outcome.

 

the only reasonable cause to put effort on this is . . . when the listed devices are a leftover of the remaining design . . .
one must realize such as an impossible (read extremely rare) occasion . . .
. . . further on the implementation of such may require excess board space (design cost) and longer routings than a dedicated approach & introduce extra delay and/or chance of an interference . . . increase power demand (incase of cmos the idle gates draw almost no power)
? what's your question . . .

(((( otherwise it's obvious that iterleaved odd/even bits give you xor ))))

It's a puzzle! It is not meant to be practical, it is meant to be a problem-solving challenge. If you don't want to try to solve the puzzle, then don't.

 

Your stated problem is very contrived, an arbitrary set of components that can be used to produce the result. You could just alter that chosen set slightly and ask it again.

More instructive would be to prove if some set of gates, can or cannot be used to reach the desired outcome.

Of course it's contrived -- as are most puzzles and design challenges.

How would asking if a particular set of gates can or can't be used to reach the desired outcome any less contrived? After all, I could just alter that chose set slightly and ask it again.

If I were to ask it again, though, I probably would leave open the possibility that it can't be done, and have people either provide a solution or an explanation for why it can't be done. If nothing else, this would likely trip up many people that just throw it at an LLM and regurgitate whatever it spouts forth. I threw it at ChatGPT and it's first response told me to feed the output of the first adder into the output of the second adder and take the end result from the input. When I asked how I could apply a signal to the output of an adder, it congratulated me on my wonderful observation and then told me that it couldn't be done because I needed AND gates and not NAND gates (it at least produced the correct equation). When I then asked it why I couldn't exploit two's complement to do the subtraction with the adder, it finally produced the correct solution (including applying a 1 to both the lsb of the second counter as well as the carry-in). It never did suggest splitting up the bits and using alternate channels of the adders. A friend also threw it at two LLMs (I think Claude and Grok, but not sure) and both said that it couldn't be done.

 

A friend also threw it at two LLMs (I think Claude and Grok, but not sure) and both said that it couldn't be done.

Unconfirmed answer below, but it didn't say it couldn't be done.

Edit: BTW, inline Latex renders horribly on AAC.

Here's a design challenge/puzzle for anyone that might be interested.

Imagine that you are tasked with producing the bitwise XOR of two multi-bit words. For simplicity, let's make them 8-bit words and call them X and Y.

We are therefore trying to get

Z = X xor Y

Here's the catch: You are given a box that has two 8-bit cascadable adders (i.e., have a carry-in and a carry-out) and eight two-input NAND gates -- perhaps four 74xx283 4-bit full adders and two 74xx00 quad NAND gates, to give something concrete. This is all you have.

Can you produce Z using just these parts? And, show me the solution using boolean algebra.

Yes — here is a complete, working solution using exactly two 8-bit cascadable adders (e.g., two groups of cascaded 74xx283 4-bit adders) and seven of the eight available 2-input NAND gates (the eighth is unused).

Core Mathematical Identity (Boolean/Arithmetic)

We start from the well-known relationship between addition, XOR, and AND:


\[ X + Y = (X \oplus Y) + 2 \cdot (X \land Y) \]

Rearranged:

\[ X \oplus Y = (X + Y) - 2 \cdot (X \land Y) \]

Let:

• \( S = X + Y \) (computed directly by the first adder)
• \( P = X \land Y \) (bitwise AND)
• \( M = 2P = P \ll 1 \) (P shifted left by 1, LSB = 0)

Then the expression becomes:

\[ Z = S - M \]

In two’s-complement arithmetic (modulo \( 2^8 \) for 8-bit words), subtraction of \( M \) is implemented as addition of its negation:

\[ -M \equiv \sim M + 1 \pmod{2^8} \]

So:

\[ Z = S + (\sim M + 1) \]
How \( \sim M \) Is Constructed with NAND Gates

Let \( M = P \ll 1 \). Then the bits of \( \sim M \) (in 8 bits) are:

• Bit 0 of \( \sim M \): \( \sim 0 = 1 \)
• Bit \( k \) (for \( k = 1 \dots 7 \)) of \( \sim M \): \( \sim P_{k-1} = \sim (X_{k-1} \land Y_{k-1}) \)

The term \( \sim (X_{k-1} \land Y_{k-1}) \) is produced directly by one 2-input NAND gate with inputs \( X_{k-1} \) and \( Y_{k-1} \).

Thus we need only 7 NAND gates (one for each bit position 1 through 7 of the correction word N N N):

• \( N_0 = 1 \) (hard-wired to logic high / Vcc)
• \( N_k = \overline{X_{k-1} \land Y_{k-1}} \) for \( k = 1 \dots 7 \) (NAND outputs)

This \( N \) is exactly \( \sim M \) (with the LSB correctly set to 1).

Circuit Implementation

Adder 1 (first 8-bit adder, Cin = 0):

• Inputs: \( X[7:0] \), \( Y[7:0] \)
• Carry-in: tied low (0)
• Output: \( S[7:0] = X + Y \)

NAND array (7 gates used):

• For each k=1 to 7: one NAND with inputs \( X[k-1] \) and \( Y[k-1] \); its output drives \( N[k] \)
• \( N[0] \) tied directly to logic 1
• (The 8th NAND gate is unused)

Adder 2 (second 8-bit adder, Cin = 1):

• Inputs: \( S[7:0] \), \( N[7:0] \)
• Carry-in: tied high (1)
• Output: \( Z[7:0] = S + N + 1 \) (mod \( 2^8 \))

This \( Z \) is exactly \( X \oplus Y \).

Why It Works (Step-by-Step Algebraic Proof)

1. \( S = X + Y = (X \oplus Y) + 2P \)
2. We compute \( N + 1 = \sim M + 1 = -M = -2P \)
3. Therefore \( Z = S + (-2P) = (X \oplus Y + 2P) - 2P = X \oplus Y \)

All carries (both in the original addition and in the correction addition) are handled automatically by the adder hardware, so the identity holds for every bit pattern, including cases with heavy carry propagation.

Verification Examples (8-bit unsigned)

• \( X = 0x03 \), \( Y = 0x01 \): \( S = 0x04 \), \( N \approx 0xFD \), \( Z = 0x02 \) (correct \( 0x03 \oplus 0x01 = 0x02 \))
• \( X = 0xFF \), \( Y = 0xFF \): \( S = 0xFE \), \( Z = 0x00 \) (correct)
• \( X = 0xAA \), \( Y = 0x55 \): \( Z = 0xFF \) (correct)
• Many other patterns (including edge cases) also match exactly.

Practical Notes for 74xx Implementation

• Use two groups of cascaded 74xx283s (or equivalent) for each 8-bit adder.
• The NANDs come from two 74xx00 quad packages (exactly eight 2-input NANDs available; seven used).
• \( N[0] \) tied high — standard TTL/CMOS practice (or use the spare NAND if you prefer to generate a clean logic-1).
• No clocks or sequential logic required — fully combinational.
• Works for any word width (scale the number of NANDs accordingly: width-1 NANDs).

This is an elegant “roundabout” use of the arithmetic relationship between addition and XOR, cleverly leveraging the adders’ built-in carry chains while using the minimal number of NANDs only where they are irreplaceable (generating the complemented AND terms).


If you want a gate-level schematic (textual ASCII or further expansion to individual 74xx283 pinouts), Verilog simulation, or variations (e.g., for different word sizes), just let me know!

 

Unconfirmed answer below, but it didn't say it couldn't be done.

Edit: BTW, inline Latex renders horribly on AAC.



Yes — here is a complete, working solution using exactly two 8-bit cascadable adders (e.g., two groups of cascaded 74xx283 4-bit adders) and seven of the eight available 2-input NAND gates (the eighth is unused).

Core Mathematical Identity (Boolean/Arithmetic)

We start from the well-known relationship between addition, XOR, and AND:


\[ X + Y = (X \oplus Y) + 2 \cdot (X \land Y) \]

Rearranged:

\[ X \oplus Y = (X + Y) - 2 \cdot (X \land Y) \]

Let:

• \( S = X + Y \) (computed directly by the first adder)
• \( P = X \land Y \) (bitwise AND)
• \( M = 2P = P \ll 1 \) (P shifted left by 1, LSB = 0)

Then the expression becomes:

\[ Z = S - M \]

In two’s-complement arithmetic (modulo \( 2^8 \)8 for 8-bit words), subtraction of \( M \) is implemented as addition of its negation:

\[ -M \equiv \sim M + 1 \pmod{2^8} \]

So:

\[ Z = S + (\sim M + 1) \]
How \( \sim M \) Is Constructed with NAND Gates

Let \( M = P \ll 1 \). Then the bits of \( \sim M \) (in 8 bits) are:

• Bit 0 of \( \sim M \): \( \sim 0 = 1 \)
• Bit \( k \) (for \( k = 1 \dots 7 \)) of \( \sim M \): \( \sim P_{k-1} = \sim (X_{k-1} \land Y_{k-1}) \)

The term \( \sim (X_{k-1} \land Y_{k-1}) \) is produced directly by one 2-input NAND gate with inputs \( X_{k-1} \) and \( Y_{k-1} \).

Thus we need only 7 NAND gates (one for each bit position 1 through 7 of the correction word N N N):

• \( N_0 = 1 \) (hard-wired to logic high / Vcc)
• \( N_k = \overline{X_{k-1} \land Y_{k-1}} \) for \( k = 1 \dots 7 \) (NAND outputs)

This \( N \) is exactly \( \sim M \) (with the LSB correctly set to 1).

Circuit Implementation

Adder 1 (first 8-bit adder, Cin = 0):

• Inputs: \( X[7:0] \), \( Y[7:0] \)
• Carry-in: tied low (0)
• Output: \( S[7:0] = X + Y \)

NAND array (7 gates used):

• For each k=1 to 7: one NAND with inputs \( X[k-1] \) and \( Y[k-1] \); its output drives \( N[k] \)
• \( N[0] \) tied directly to logic 1
• (The 8th NAND gate is unused)

Adder 2 (second 8-bit adder, Cin = 1):

• Inputs: \( S[7:0] \), \( N[7:0] \)
• Carry-in: tied high (1)
• Output: \( Z[7:0] = S + N + 1 \) (mod \( 2^8 \))

This \( Z \) is exactly \( X \oplus Y \).

Why It Works (Step-by-Step Algebraic Proof)

1. \( S = X + Y = (X \oplus Y) + 2P \)
2. We compute \( N + 1 = \sim M + 1 = -M = -2P \)
3. Therefore \( Z = S + (-2P) = (X \oplus Y + 2P) - 2P = X \oplus Y \)

All carries (both in the original addition and in the correction addition) are handled automatically by the adder hardware, so the identity holds for every bit pattern, including cases with heavy carry propagation.

Verification Examples (8-bit unsigned)

• \( X = 0x03 \), \( Y = 0x01 \): \( S = 0x04 \), \( N \approx 0xFD \), \( Z = 0x02 \) (correct \( 0x03 \oplus 0x01 = 0x02 \))
• \( X = 0xFF \), \( Y = 0xFF \): \( S = 0xFE \), \( Z = 0x00 \) (correct)
• \( X = 0xAA \), \( Y = 0x55 \): \( Z = 0xFF \) (correct)
• Many other patterns (including edge cases) also match exactly.

Practical Notes for 74xx Implementation

• Use two groups of cascaded 74xx283s (or equivalent) for each 8-bit adder.
• The NANDs come from two 74xx00 quad packages (exactly eight 2-input NANDs available; seven used).
• \( N[0] \) tied high — standard TTL/CMOS practice (or use the spare NAND if you prefer to generate a clean logic-1).
• No clocks or sequential logic required — fully combinational.
• Works for any word width (scale the number of NANDs accordingly: width-1 NANDs).

This is an elegant “roundabout” use of the arithmetic relationship between addition and XOR, cleverly leveraging the adders’ built-in carry chains while using the minimal number of NANDs only where they are irreplaceable (generating the complemented AND terms).


If you want a gate-level schematic (textual ASCII or further expansion to individual 74xx283 pinouts), Verilog simulation, or variations (e.g., for different word sizes), just let me know!

Isn't AI wonderful!

 

Isn't AI wonderful!

If you have a point, perhaps try to make it?

 

If you have a point, perhaps try to make it?

AI is good at solving the problem, that's my point. The "why it works" part is a dead give away.

 

AI is good at solving the problem, that's my point. The "why it works" part is a dead give away.

I like AI (LLMs for the pedantic). Mainly for the reason that it directs me to avenues of investigation that I might otherwise overlook.

Wonderful? Not yet.

But, soon.

EDIT: Further, I always assume the answer it gives me is wrong. Therefore, I am never disappointed.

Anyone who refuses to work with AI -- especially just from a point of principle -- is missing out.

 

100% agree...