Basics of signed and unsigned integers in C

Any competent C programmer understands how signed and unsigned integers are handled.  I understand the concepts, but realized I forgot some of the details, so I experimented with a simple program to refresh my memory.

basic_int.c

The C language standard does not specify how to handle negative numbers, but most modern HW platforms use two's complement.  In two's complement, -1 is represented as all 1's, which is the maximum unsigned integer.  Also, printf interprets the data using the format string, not the type of the variable.  For example:
Results in:
int: -1, unsigned int: 4294967295, hex: ffffffff

Casting from an int to an unsigned int does not change the value stored in memory:
Results in:
i: int: -1, unsigned int: 4294967295, hex: ffffffff
ui: int: -1, unsigned int: 4294967295, hex: ffffffff

In two's complement, the most negative number is represented with an MSB of 1, followed by all zeros:
Results in:
i: int: -2147483648, unsigned int: 2147483648, hex: 80000000
ui: int: -2147483648, unsigned int: 2147483648, hex: 80000000

Addition and subtraction is handled the same for signed and unsigned (for two's complement).  Subtraction is implemented by inverting, adding, and adding 1.  For example, i - 1 is implemented as i + 0xFFFFFFE + 1.
Results in:
i: int: 2147483647, unsigned int: 2147483647, hex: 7fffffff
ui: int: 2147483647, unsigned int: 2147483647, hex: 7fffffff

When an operation is performed where one operand is signed and the other is unsigned, if all values of the unsigned operand can be represented in the signed type, then the unsigned operand is promoted to the signed type.  If not, then the signed operand is cast to unsigned.  This leads to some interesting cases for relational operations.  Constants are implicitly signed.

For example, If i = -1, and ui = i (4,294,967,295), then i < 0 is true and and ui > 0 is true, which makes sense.  But, ui == i is true, which seems incorrect since i < 0 and ui > 0.  But, C casts i to the unsigned interpretation of 4,294,967,295, which equals ui.
Results in:
i: int: -1, unsigned int: 4294967295, hex: ffffffff
ui: int: -1, unsigned int: 4294967295, hex: ffffffff
i < 0? true
ui < 0? false
i == ui? true

Here's another odd case - compare -1 (implicitly signed) to 0 (unsigned).  -1 is implicitly cast to 0xFFFFFFFF unsigned, which is greater than 0.
Results in:
ui: int: 0, unsigned int: 0, hex: 0
-1 < ui? false

Casting an unsigned to a signed can also lead to an interesting result.  If ui = 0x80000000, and i = (ui - 1), then i < ui is true. But, if ui is cast to a signed int, then it's a negative number and i < ui is false.
Results in:
i: int: 2147483647, unsigned int: 2147483647, hex: 7fffffff
ui: int: -2147483648, unsigned int: 2147483648, hex: 80000000
i < ui ? true
i < (int) ui ? false

If ui is 1, and i = -1, then (ui < i) is true, which seems incorrect.  But i is implicitly cast to an unsigned int with a value of 0xFFFFFFFF, which is greater than 1.  However, if the signed operand can represent all values of the unsigned operand, then the unsigned operand is promoted to the type of the signed operand.  For example, if usi is an unsigned short = 1, and i = -1, then (usi < i) is false as expected, since i remains -1 as a signed int, and usi is promoted to 1 as a signed int.
Results in:
i: int: -1, unsigned int: 4294967295, hex: ffffffff
ui: int: 1, unsigned int: 1, hex: 1
usi: int: 1, unsigned int: 1, hex: 1
ui < i ? true
usi < i ? false

I'm sure you found this post really exciting!

Automation with Visual Basic

I'm doing some volunteer work for Oak Meadow Montessori School, helping with some computer work for after school programs,  We need to keep track of the programs being offered, which students are in which programs, what rooms the programs are in, and more.  A set of documents including a program guide, lists of students per program, program room assignments and more need to be produced and constantly updated.

One obvious approach is to produce and maintain a set of MS Word and Excel documents to keep track of everything and to produce the needed documents.  However, much of the information appears in multiple documents, making it time consuming and error prone to keep all the documents correct and up to date.

I decided to apply the "DRY" (don't repeat yourself) principle from software engineering.  In this case the goal is to maintain all data regarding programs, students, schedules, etc. in one place and process the source information to automatically produce the required documents.  At first, I wanted to use Ruby for the automation since we're using it for one of our projects at AMD.  However, I realized that no one at Oak Meadow would be able to maintain Ruby code so I decided to try Excel VBA macros instead.

I had no prior experience with VBA, but after just a few hours of internet searching and experimenting, I was able to produce an example document in .pdf format.  From there, I've been making incremental changes - re-organizing the data to eliminate redundancy and improve maintainability.  I've also been improving the code and creating additional reports in different formats.  I'm still a novice with VBA, but it has some nice properties:

• Easy to learn on your own (given some programming background)
• Quick to get something functional, even if it's not optimal
• Well suited for processing and producing information in typical business formats - MS Word, Excel, PowerPoint, and .pdf
• Mature language with an extensive developer community - simple internet searches quickly produce relevant code snippets and examples.

I'm continuing to experiment and learn, but so far, Excel and VBA are working well for this application.

Test Driven Development

Test Driven Development promises to improve software quality by pushing developers to think hard about requirements, interfaces and corner cases, create tests early in the development cycle, and provide a test framework that enables and encourages re-factoring.

I decided to give it a try myself while working on one of the labs from my son's Computer Science class at RPI. It was a very simple assignment - write a function that returns the maximum of three integers and test the function with some sample data.  Test Driven Development recommends the following:

1. Write a test.
2. Run the test and verify it fails.
3. Write some code.
4. Run the tests and fix the code until the tests pass.
5. Re-factor the code.
6. Repeat.

For some reason I can't yet explain, most software developers like writing functional code but don't like writing test code.  With test driven development, the test code is written in the same language as the functional code, so why is it that we enjoy writing functional code but not test code?  Isn't code code?

I found myself drawn towards the functional code, but forced myself to begin by writing:

int max3(int a, int b, int c) {

  return -1;

}

I then wrote a test harness with the sample data and ran the tests.  As expected, all of the tests failed except one case where -1 was the expected result.  Next, I updated the function to return the maximum value, re-ran the tests, and they all passed!  So far so good...

In class, the TA asked the students a teaser question - write the same function using only a single if statement. My original implementation had two if statements, so I decided to give it a try and I came up with this:

int max3 (int a, int b, int c) {

   int max = a;

   if ( (b>max) && (max=b) && (c>max)) max = c;

}

I ran the tests, and they all passed so I thought I was pretty smart.  Always curious and never satisfied, I decided to add a few more tests.  To my surprise (and disappointment), this test case failed:

a = -2, b = -2, c = -1, expect: -1

Guess I'm better at writing tests than code and I'm not as smart as I first thought.  Given a specific failing test case, it was pretty easy to find the flaw in the code so I updated the function to:

int max3 (int a, int b, int c) {

  int max = a;

  if ( ((b>max) && (max=b)) || ((c>max) && (max=c)));

  return max;

}

I re-ran the tests, and they all passed.  I'm sure a more skilled developer would have recognized the flaw in my first attempt at using a single if statement, but I'm also sure that even the best programmers make mistakes.

[Update 07-Nov-2010:  OK, this code doesn't work either (it has the same type of flaw as my first attempt) and the tests did *not* all pass.  When I ran the tests, I took a quick look at the tests that failed with my first attempt, and those cases passed.  The unit tests worked great - I just made the mistake of rushing and not checking all the results...]

When I started on this exercise, I thought it was too trivial to be of much interest and pursued it solely as a simple way to start exploring test driven development.  To my surprise, this simple example illustrated an important concept - don't write "clever code."

Attempting to be too clever obscures the purpose of the code, making it difficult to understand and maintain, and increases the odds of introducing subtle, hard to detect errors.  Imagine trying to debug the flawed max3 implementation if it was buried deep inside 1,000's of lines of code, with the flaw exposed by some complex system test.  System level tests would work correctly in many cases, but then fail for unexplained reasons in other cases, leading to a long and difficult debugging session.  With a simple failing unit test, it was quick and easy to find the flaw by inspection.

Although this example is far too simple to draw conclusions about the value of Test Driven Development for commercial software development projects, I do feel it's worth exploring the technique in more complex situations.

Back to School

My son started at RPI as a freshman majoring in Computer Engineering this past September.  Reflecting back on my time in school, I noticed that some things have changed dramatically while others are pretty much the same.  Dorms now have WiFi and cable TV, but they're still dorms, and students still sleep until noon (or later) on weekends.  One exciting difference is the use of the Internet for managing classes and course work.  All of my son's class materials are posted on-line, so I've been "going back to school," following along with some of the courses as time allows.

When I took my first computer science class at UCONN, we learned PL/I, typed programs on punch cards, and stood in line waiting to put our cards through a reader to run on some mysterious IBM mainframe that we never saw.  Some time later, a printout with your last name on it came rattling out of a line printer the size of three washing machines.  When the printer ran out of paper, the cover opened up automatically, sending any punch cards on top up in the air and fluttering to the floor completely out of order.  Many of us learned not to put our cards on top of the printer the hard way.

I'm following Computer Science I at RPI, reading all the lectures and doing the labs and homework.  The course is in C++ and students work on  laptops using either Visual C++, Cygwin, or native Linux.  I work on my laptop at home, download assignments from RPI's website, edit with emacs, compile with g++ and run on a virtual remote Linux desktop using an NX Client.  Sure beats the heck out of trudging across campus at night to the computer center to wait in lines, type punch cards, and debug programs reading one print out at a time.

So far, it's been a great way to refresh my programming skills and learn emacs, which I've wanted to do for years but have never found the time to do.  Best of all, there's no (extra) cost!

Engineers Must be Driven

My wife and I were discussing colleges with my son's Physics teacher, Robert Campolieto of Lawrence Academy.  Our son is interested in Engineering and Computer Science, and during the discussion, Mr. Campolieto said,

"Engineers must be driven ... it isn't good enough to just be smart or engage in discussion; engineers must be driven to produce results."

In the Guerrilla Guide to Interviewing (version 3.0), Joel Spolsky recommends hiring "smart people who get things done," and I feel "being driven" is a stronger way to summarize "get things done," since it implies that a person has an innate, internal motivation to accomplish things.  I now include "drive" as one of the key attributes I look for when assembling a team.  Driven individuals naturally inject energy into the team and create a sense of urgency that compels the rest of the team to move faster.

How driven are you?  What are you driven to accomplish?

Three Options and a Recommendation

During my tenure at HP in Chelmsford MA, I was technical lead for a memory system design where I had the good fortune to work with Milton Makris.  Milton was the engineering manager for the project and together, we led a 25 person ASIC team to develop and verify three custom chips for HP's commercial and workstation Unix systems.

Milton was an energetic, positive, and innovative manager and I learned a lot about managing and leadership from him.  When faced with a need to make a decision about a complex situation, Milton would always say, "three options and a recommendation."  A simple, yet powerful phrase that helps in many situations.

In the faced paced high tech world, we often feel a sense of urgency to make decisions quickly.  However it's easy to make suboptimal decisions, which ends up wasting more time than was saved by making hasty decisions.  Unstructured discussions tend to focus on one aspect of a decision at a time, without fully understanding impacts in other areas.  For example, if a "critical" project is falling behind schedule, the discussion may focus on pulling in the schedule for this project, without fully assessing other impacts such as delays to other projects, increased costs, and lower efficiency from resource thrashing.

"Three options and a recommendation" provides an excellent framework to increase discipline and objectivity to team decision making without adding excessive overhead.  Before coming to a decision, the team takes the following steps:

1. Identify at least three different options.  At this stage, it's important to encourage creative thinking to explore a range of possibilities.  "Crazy ideas" should be welcomed, not discouraged during this phase.
2. List pros and cons for each option.  Be as objective and quantitative as possible, gathering as much supporting data as practical.  For example, "it's more work" is too subjective.  "It will require 3 extra person weeks of work" is much better.
3. Write a summary of the options; define the schedule, scope (feature set), and resources for each option. Identify all dependencies and associated impacts.
4. Recommend one of the options and include an explanation.
   

With a rich set of information organized into "three options and a recommendation," the team is now well prepared to run a productive meeting to close on a high quality decision.

A Lesson in Teamwork

A number of years ago, I was coaching a soccer team of 5-6 year old boys and girls.  At our first practice, I told the kids we need to pick a team name and asked for ideas.  The boys starting blurting out names like Destroyers, Bombers, Blasters, and so on.  After the boys ran out of variations on destruction, one of the girls said, "how about the Strawberries?," which drew a loud round of boos from the boys.

I said OK, let's take a vote and started working down the proposed names one at a time, counting votes along the way.  Each of the boys voted for his own idea with an occasional supporting vote or two from the other boys.  When I got to the Strawberries, all of the girls raised there hands at once, and I said, "great, our team is the Strawberries!"

Surprisingly, the girls did not plan to work together; it was a wonderful example of spontaneous and implicit teamwork!