Addition as binary operations

Question

I'm adding a pair of unsigned 32bit binary integers (including overflow). The addition is expressive rather than actually computed, so there's no need for an efficient algorithm, but since each component is manually specified in terms of individual bits, I need one with a compact representation. Any suggestions?

Edit: In terms of boolean operators. So I'm thinking that carry = a & b; sum = a ^ b; for the first bit, but the other 31?

Oh, and subtraction!

Answer 1

You can not perform addition with simple boolean operators, you need an adder. (Of course the adder can be built using some more complex boolean operators.) The adder adds two bits plus carry, and passes carry out to next bit.

Pseudocode:

carry = 0
for i = 31 to 0
  sum = a[i] + b[i] + carry
  result[i] = sum & 1
  carry = sum >> 1
next i

Here is an implementation using the macro language of VEDIT text editor. The two numbers to be added are given as ASCII strings, one on each line. The results are inserted on the third line.

Reg_Empty(10)                       // result as ASCII string
#0 = 0                              // carry bit
for (#9=31; #9>=0; #9--) {
    #1 = CC(#9)-'0'                 // a bit from first number
    #2 = CC(#9+34)-'0'              // a bit from second number
    #3 = #0+#1+#2                   // add with carry
    #4 = #3 & 1                     // resulting bit
    #0 = #3 >> 1                    // new carry
    Num_Str(#4, 11, LEFT)           // convert bit to ASCII
    Reg_Set(10, @11, INSERT)        // insert bit to start of string
}
Line(2)
Reg_Ins(10) IN
Return

Example input and output:

00010011011111110101000111100001
00110110111010101100101101110111
01001010011010100001110101011000

Edit:
Here is pseudocode where the adder has been implemented with boolean operations:

carry = 0
for i = 31 to 0
  sum[i] = a[i] ^ b[i] ^ carry
  carry = (a[i] & b[i]) | (a[i] & carry) | (b[i] & carry)
next i

Answer 2

Perhaps you can begin by stating addition for two 1-bit numbers, with overflow (=carry):

A | B | SUM | CARRY
===================
0   0    0      0
0   1    1      0
1   0    1      0
1   1    0      1

To generalize this further, you need a "full adder" which also takes a carry as an input, from the preceding stage. Then you can express the 32-bit addition as a chain of 32 such full adders (with the first stage's carry input tied to 0).

Answer 3

• Regarding data structure part to represent these numbers. There are 4 ways

1) Bit Array
A bit array is an array data structure that compactly stores individual bits.
They are also known as bitmap, bitset or bitstring.

2) Bit Field
A bit field is a common idiom used in computer programming to compactly store multiple logical values as a short series of bits where each of the single bits can be addressed separately.

3) Bit Plane
A bit plane of a digital discrete signal (such as image or sound) is a set of bits corresponding to a given bit position in each of the binary numbers representing the signal.

4) Bit Board
A bitboard or bit field is a format that stuffs a whole group of related boolean variables into the same integer, typically representing positions on a board game.

• Regarding implementation, you can check that at each step, we have following
  S = a xor b xor c

S is result of sum of current bits a an b
c is input carry

Cout - output carry is (a & b) xor (c & (a xor b))