Bits, Overflow, and Signed Numbers

CS 301 Lecture, Dr. Lawlor

Arithmetic In Binary

We can do arithmetic in binary or hex by hand just like we do in decimal.  To add, line up the digits, add corresponding digits, and if the per-digit sum is greater than the base, carry to the next digit.  Easy, right?  To subtract, do the exact same thing, but "borrow" from the next digit if the per-digit difference is less than 0.

For example, in binary 01+01=10 because the first digit overflows, and the extra "1" is carried to the next digit.  Similarly, 1111+1=10000 because all the digits overflow in sequence.  In general, adding a "1" will cause carries to ripple up through ones, flipping them to zeros, until it finally reaches a zero, which it will flip to a one.

Addition in hex is exactly the same--it's a bit tricker to add the larger digits involved, but carries work exactly the same.  So  0x8+0x8=0x10, and 0xffff+0x1=0x10000.

Subtraction and Negative Numbers in Binary

Subtraction in binary seems really bizarre until you remember than 10-1=1 in binary--that is, "1" is the one-less-than-zero digit in binary; just like "9" is the corresponding one-below-zero digit in decimal.  So when you have to borrow, you just flip the zeros to ones until you hit a one. 

Subtraction actually shows you how to represent negative numbers in binary.  Consider -1==0-1: you just keep on flipping zeros to ones forever, "borrowing" against the future that never comes (just like the US banking system!).  So -1 is represented (in principle) by an infinite number of ones, just like +1 is represented (in principle) by an infinite number of zeros followed by a one.  In practice, we only store a finite number (usually 32 or 64) of bits, so on a 32-bit machine we define 32 ones as -1.  The highest bit, then, can be thought of as a "sign bit"--negative numbers have that bit set, positive numbers have that bit clear.  Suprisingly, it make sense to think of the sign bit in digit n as having value -2n, instead of value 2n for unsigned numbers.  What's weirder is that addition and subtraction are exactly the same for signed or unsigned numbers--try it!  (All other operations are different, though: comparison, multiplication, division, etc.)

Signed versus unsigned numbers are clearer if you draw them out for a 3-bit machine:
Bit Pattern
 Unsigned Value
 Signed Value
000
 0
 0
001
 1
 1
010
 2
 2
011
 3
 3
100
 4
 -4
101
 5
 -3
110
 6
 -2
111
 7
 -1

Note that languages other than Java support "signed" as well as "unsigned" integer types explicitly.  In C/C++/C#, typecasting to an unsigned value does nothing to the bits, and is hence a zero-clock operation.  One way to speed up a "zero to n" bounds test on a signed value is to turn it into an unsigned value and just compare against n--that is, "if ((x>=0)&&(x<n)) ..." is the same as "if (((unsigned int)x)<n) ..." do exactly the same thing, because negative signed x's will turn into really huge unsigned x's!

In hex, -1 (in binary, all ones) is written in hex as 0xFFffFFff (on a 32-bit machine).

Another way to think about -1 is that it's like "99999" on a car's odometer--if you drive one more mile, you'll be at "00000", so you're really at mile -1!

The "obvious" way to represent negative numbers, just using the sign bit to store the +/- sign, is called one's complement, and has the weird behavior with zero plus the sign bit set--you get negative zero!  For this reason, the approach above with a big negative sign bit, called two's complement, is the standard today.

Accessing the Bits of an Integer

If you'd like to stare at, or modify the sign bit inside your integer, you can use the bitwise operators to access them.  There's a common trick which is to use bitwise AND to pull out bits:
void poke_at_int(int v) {
	std::cout<<"For the int "<<v<<": ";

	if (v&(1<<31)) std::cout<<"The sign bit is set (1).";
	else	std::cout<<"The sign bit is clear (0).";

	std::cout<<"\n";
}

int foo() {
	poke_at_int(0);
	poke_at_int(+1);
	poke_at_int(-1);
	return 0;
}

(Try this in NetRun now!)

This prints:

For the int 0: The sign bit is clear (0).
For the int 1: The sign bit is clear (0).
For the int -1: The sign bit is set (1).
Program complete.  Return 0 (0x0)

You can also use bitwise OR to stick on new bits:
void poke_at_int(int v) {
	std::cout<<"For the int "<<v<<": ";

	v=v|(1<<2);
	std::cout<<"Setting bit 2 makes the value "<<v;

	std::cout<<"\n";
}

int foo() {
	poke_at_int(0);
	poke_at_int(+1);
	poke_at_int(+2);
	poke_at_int(+4);
	poke_at_int(-1);
	return 0;
}

(Try this in NetRun now!)

This prints:

For the int 0: Setting bit 2 makes the value 4
For the int 1: Setting bit 2 makes the value 5
For the int 2: Setting bit 2 makes the value 6
For the int 4: Setting bit 2 makes the value 4
For the int -1: Setting bit 2 makes the value -1
Program complete.  Return 0 (0x0)
Note that 1<<2 is 4.  Setting this bit on the value 4 (or 7, or 12, or...) does nothing, since that bit is already set.  Setting this bit on -1 does nothing, since -1 has all its bits set already.

Crazy Speed via Bitwise Operators

There are some incredible, and incredibly bizarre, tricks using bitwise operators.  Sean Anderson has an impressive collection of these tricks, but don't follow the link until you've read and digested everything we've said here so far!

A good simple beginner entry:
	int x, y;               // input values to compare signs
	bool f = ((x ^ y) < 0); // true iff x and y have opposite signs
This works using XOR (exclusive OR) on the sign bits of x and y.  If these bits have different values, then XOR returns 1 (look at the truth table for XOR), so x^y is negative.

They get a lot more complicated from there!

Examples from Lecture