Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Unsigned Arithmetic: Useful but Tricky

May 30, 2012

C++, like C, supports two distinctly different kinds of integers: signed and unsigned. Each kind comes in several sizes, but the kinds differ in ways that transcend size. If a signed integer overflows, the result is undefined. If an unsigned integer overflows, the result is defined modulo 2w, where w is the number of bits in that particular unsigned integer. By implication, an unsigned integer is never negative.

In general, arithmetic that combines signed and unsigned values yields an unsigned result. This property is particularly important for comparisons, in which a signed integer is converted to unsigned for comparison purposes. For example, the comparison n>=0u, where 0u represents an unsigned integer zero, is always true — even if n is signed — because n is converted to unsigned and the result of that conversion cannot be negative.

This aspect of how unsigned arithmetic behaves has some curious effects on programming technique. For example, suppose I have a vector named x, and I want to access its nth element. I do so by writing x[n], of course.

Suppose further that n has type int, and that I want to be sure before I try to access x[n] that n is in range. The obvious way of doing so is to write something like this:

 
     if (n < 0 || n >= x.size())
           throw an out-of-range exception;
     // Now it is safe to access x[n]
 

There is a subtle improvement possible in this code. The size member of the vector class returns an unsigned value. When we compare n to such a value, and n has a signed type, n will be converted to unsigned for the comparison. If n is negative, this conversion will wrap around and yield a large positive number. Only if x has more elements than this number will the test succeed. As a result, so long as x is not a huge negative number, we can omit the comparison n .

Omitting the test this way is slightly shaky, because it is possible that n might be such a large negative number as to wrap around and look like a large positive number. However, if we make n unsigned, then we can definitely omit the comparison of n to 0, because of course an unsigned variable will never be less than zero.

As so often happens, the code simplification that comes from making n unsigned can complicate other kinds of programs. Suppose, for example, that we want to visit the elements of x in reverse order. We cannot write

 
             for (auto n = x.size() - 1; n >= 0; --n)
                           // Do something with x[n]

because the comparison n >= 0 will always be true. The reason is that x.size() yields an unsigned value, so n will also be unsigned.

Instead, it is necessary to write something like this:

 
             auto n = x.size();
             while (n) {
                           --n;
                           // Do something with x[n]
             }

It is no coincidence that this technique is similar to the technique that one would use for iterators. In fact, there's an interesting story behind this similarity. I'll talk about that next week.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video