Associated Topics || Dr. Math Home || Search Dr. Math

### Compute 16-bit One's Complement Sum

```
Date: 03/20/2002 at 13:54:13
From: John
Subject: How to compute 16-bit one's complement sum

I would like to know how to compute one's complement sum. In my TCP/IP
book it says, "to compute the IP checksum for outgoing datagram, the
value of checksum field is set to zero, then the 16-bit one's
complement sum of the header is calculated (i.e. the entire header is
considered a sequence of 16-bit words)" - but I do not know how to
```

```
Date: 03/21/2002 at 01:27:19
From: Doctor Twe
Subject: Re: How to compute 16-bit one's complement sum

Hi John - thanks for writing to Dr. Math.

What that means is:

1. Add the 16-bit values up. Each time a carry-out (17th bit) is
produced, swing that bit around and add it back into the LSb (one's
digit). This is somewhat erroneously referred to as "one's complement

2. Once all the values are added in this manner, invert all the bits
in the result. A binary value that has all the bits of another binary
value inverted is called its "one's complement," or simply its
"complement."

For example, suppose our header has the following data. I separate the
data into groups of 4 bits only for readability. (I know that headers
are really longer than 8 bytes, but this will demonstrate the
process):

1000 0110 0101 1110
1010 1100 0110 0000
0111 0001 0010 1010
1000 0001 1011 0101

First, we add the 16-bit values 2 at a time:

1000 0110 0101 1110   First 16-bit value
+   1010 1100 0110 0000   Second 16-bit value
---------------------
1 0011 0010 1011 1110   Produced a carry-out, which gets added
+  \----------------> 1   back into LBb
---------------------
0011 0010 1011 1111
+   0111 0001 0010 1010   Third 16-bit value
---------------------
0 1010 0011 1110 1001   No carry to swing around (**)
+   1000 0001 1011 0101   Fourth 16-bit value
---------------------
1 0010 0101 1001 1110   Produced a carry-out, which gets added
+  \----------------> 1   back into LBb
---------------------
0010 0101 1001 1111   Our "one's complement sum"

(**) Note that we could "swing around" the carry-out of 0, but adding
0 back into the LSb has no affect on the sum. (But technically, that's
what the checksum generator does.)

Of course, we'd continue to add the rest of the header data in 16-bit
segments until all data were included.

Then we have to take the one's complement of the sum. We do this by
simply inverting all the bits in the final result from above:

0010 0101 1001 1111   Our "one's complement sum"

1101 1010 0110 0000   The "one's complement"

So the checksum stored in the header would be 1101 1010 0110 0000.

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 08/16/2002 at 08:51:24
From: Arthur Sheiman
Subject: How to compute 16-bit one's complement sum

Hi Dr. Math,

This article on computing the IP header checksum using the complement
of the "one's complement addition" is very good and 100% technically
correct, but I think it would be improved with another paragraph at
the end, as follows.

In practice, the efficiency of computing the IP header checksum is
very important. When computing the checksum in software on a 32-bit
processor, e.g., Intel 386 and above, it is more efficient to first
add up all the numbers using 32-bit arithmetic, and then add the
overflow at the end. This may result in another 16-bit overflow, so
this last step needs to be done twice. Three times is not necessary,
as it cannot overflow again (FFFF + FFFF = 1FFFE; FFFE + 0001 = FFFF).

Another important practical issue is the endian (byte order) of the
machine. Suggested reading is RFC1071, available free from
www.ietf.org, especially section 3, which demonstrates computation on
both the world's most popular microprocessor, Intel, and less popular
machines, e.g., big endian.
```
Associated Topics:
High School Calculators, Computers

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search