Function to check truth value of a specific statement I want to check the truth of A + B - (A &amp; B) == A | B for N-bit numbers. For example, here's a "truth" table for 2-bit numbers. (I know I'm taking liberty with the concept of a "truth" table.)



Here's the simple code I threw together in Python.

def check_truth(bits):    

    for x in range(2**bits): 
        for y in range(bits*2):
            if x + y - (x &amp; y) != x | y:
                return "False for {} bits".format(bits)

    return "True for {} bits".format(bits)


It spits out the correct answer, but it's obviously really inefficient. I am not good at algorithm analysis, but it's something like \$O(2^N)\$ right?

It's pretty much just a one-time-use function, but I'm curious how it could be improved. For example, I figure you could skip over number pairs that had been tested before. Any other ideas?
Make the function return True or False.
You can use all and a generator comprehension instead of returning early.
You should make the range have the same input.


Putting these together you can get:

def check_truth(bits):
    return all(
        x + y == (x | y) + (x &amp; y)
        for x in range(bits ** 2)
        for y in range(bits ** 2)
    )

print("{} for {} bits".format(check_truth(bits), bits))


The simplest way to prove:

$$x + y = (x \land y) + (x \lor y)$$

Is to think of integers as a bunch of wires that are passed to an infinite full adder. Due to how full adders work, they will not care how the bits are placed, as it makes no logical difference to its functionality.
So \$010 + 101 = 111 + 000\$, which means as long as we know there are the same amount of bits on each section of the equation, then we know they are the same.
Since we know \$a = x \lor y\$ and \$b = x \land y\$, we can test if there are any missing or new bits.
And so using the following 'table' shows that each level will have the same amount of bits:

$$
x, y, a, b\\
0, 0, 0, 0\\
1, 0, 1, 0\\
0, 1, 1, 0\\
1, 1, 1, 1\\
$$

And so to get the best performance we can re-write check_truth:

def check_truth(bits):
    return True




To make a more compelling argument, we could sub \$a\$ and \$b\$ into a full adder equation, and show there's no difference, but if you think about this logically you should notice it's always true.

$$
S = C \oplus (A \oplus B)\\
C_1 = ((A \oplus B) \land C) \lor (A \land B)
$$

Sub \$A = x \lor y\$ and \$B = x \land y\$:

$$
S = C \oplus ((x \lor y) \oplus (x \land y))\\
C_1 = (((x \lor y) \oplus (x \land y)) \land C) \lor ((x \lor y) \land (x \land y))
$$

Simplify some things:

$$
(x \lor y) \oplus (x \land y) = x \oplus y\\
(x \lor y) \land (x \land y) = x \land y
$$

Sub simplified versions into main function:

$$
S = C \oplus (x \oplus y)\\
C_1 = ((x \oplus y) \land C) \lor (x \land y)
$$

See that it works the same way.