I'm trying to calculate the sum of 2 bits using basic binary arithmetic and currently, I'm doing this:

function Add(bool a, bool b, bool carry)
         Result: a ^ b ^ carry,
         Carry: a & b | a & carry | b & carry

Is there a way to shorten the expression that calculates the Carry or I have to manually check all possible combinations?


There is only a minor simplification:

a & b | (a | b) & carry

This is equivalent to

a & carry | (a | carry) & b


carry & b | (carry | b) & a
  • That's neat. So, there is no built-in operator (in C language, for that matter) that given 3 operands will yield true when at least 2 of the operands are true? – DumbButterly Feb 19 '17 at 18:33
  • @DumbButterly: No, in C, C++ and Java there is only one operator with three operands (a ? b : c) and it does coonditional assignment. – Frank Puffer Feb 19 '17 at 19:52
  • 2
    @DumbButterly C is pretty much a shorthand for assembly and doesn't have anything that you don't find on CPUs. If it's something you need frequently, write it as a function that can be inlined and any decent compiler will make sure it runs quickly. – Blrfl Feb 19 '17 at 20:00
  • @Blrfl: No, it's an HLL on top of assembler, as anyone who's actually programmed in assembler would readily tell you (I being one). Some of the many things C has that assembler doesn't: loops, functions, structures, types that aren't native-length float or int, type checking, arrays... and so on. And that's just C from circa 2000, which is the last time I used it day in a and day out. – Lawrence Dol Mar 2 '17 at 20:02
  • 1
    @LawrenceDol: You don't have to read far into the introduction of The C Programming Language (1978 edition) to know that (a) Kernighan and Ritchie disagree with your characterization of C as a high-level language and (b) it was designed to reflect the abilities of the processors available at the time. I'm not implying that C is a 1:1 mapping for assembly does, but rather a shorthand for a lot of the things that were being done by hand in assembly. If you want to start swinging years of experience around, I've written assembly for about a dozen CPUs since 1980 and learned C in 1987. – Blrfl Mar 2 '17 at 22:33

If I'm not mistaken, you can add bools in C. You could add the three bools together and then check if the value is greater than 1. I doubt this would be a good idea from a performance perspective. It might be worth considering if you had more than three boolean values and wanted to check if a certain number are set.

I realize this makes no sense for what you want to do specifically but it is a solution for the more general problem of given X bools check if Y (or at least Y) are set.


If you're counting by operations, and you're willing to count ?: as one operation, then you can improve on this answer with:

carry ? (a|b) : (a&b)

That is five operands and three operations. Or maybe 3.5 operations. But it's still better than the other answer with 4 operations.

If you're focused on the idea that the function is 'any two or more of the three', this I like this form because it says "If one is high, either of the other two, otherwise both of the other two."

  • (You can swap the operands any way you want because the function is symmetric, BTW -- this way takes the fewest characters) – ThePopMachine Mar 2 '17 at 16:14

Pseudo code for a generic full adder (what you are describing). Most languages will support this pseudo code.

Using a temporary field means that this will take five operations, two EXCLUSIVE OR, two AND, and one OR.

Inputs: a, b, Cin
Outputs: sum, Cout

temp = a XOR b
sum = temp XOR Cin
Cout = (a AND B) OR (temp AND Cin)

protected by gnat Mar 2 '17 at 18:11

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.