Unsigned Addition

Standard Addition Function

Ignores carry output.

Implements Modular Arithmetic

s=UAddw(u,v)=(u+v)mod2ws=UAdd_w(u, v)=(u+v)\bmod2^w

Two’s Complement Addition

overflow

negative overflow: Add two negative numbers will get positive.

positive overflow: Add two positive numbers will get negative.

Multiplication

In principle if take two W bit numbers and multiply them together, then may need a 2w bits to represent,

because you’re potentially squaring the largest number.

Unsigned Multiplication in C

Ignores high order w bits, just like unsigned addition, UMultw(u,v)=(uv)mod2wUMult_w(u, v)=(u\cdot v)\bmod 2^w

Signed Multiplication in C

Not only trunk throw away whatever high order bits, but whatever bit gets left in this position will determine whether it’s a positive or a negative result, completely irrespective of the signs of the original two operands.

Power-of-2 Multiply with Shift

shift operation.

Unsigned Power-of-2 Divide with Shift

Uses logical shift.

if the number can’t divisible by power-of-2, and it’s a negative number,

it should round toward zero, but actually it’s rounding toward minus infinity, it’s rounding toward a more negative number than the true number.

Before we divide by a power-of-2 do the shift, we should add a bias.

By the way, division is really really slow even on a modern computer, the shark machines it takes 30 plus Hawk cycles,

so anytime the compiler can avoid figure out a trick that does it with shifting and tweaking things around it will.

Negate a Number

Flip all the bits, and add 1 to that.

Why Should I Use Unsigned?

Do Use When Performing Modular Arithmetic

Multiprecision arithmetic

Do Use When Using Bits to Represent Sets

Logical right shift, no sign extension.

How Should I Use Unsigned?

A wrong way to Use unsigned as loop index

1
2
3
unsigned i;
for (i = cnt - 2; i >= 0; i--)
a[i] += a[i + 1];

Right way

1
2
3
unsigned i;
for (i = cnt - 2; i < cnt; i--)
a[i] += a[i + 1];

Byte-Oriented Memory Organization

Programs refer to data by address

Conceptually, envision it as a very large array of bytes(In reality, it’s not, but we can think of it that way)

An address is like an index into that array, and a pointer variable stores an address.

A trick to get an approximate value

210=10241032^{10}=1024\approx10^3, what it means is that 10 bits worth of number is about the same as three decimal digits.

so, 2301092^{30}\approx10^9, 240103+9=122^{40}\approx10^{3+9=12}, 247=140,737,488,355,32812810122^{47}=140,737,488,355,328\approx128*10^{12}

Machine Words

Any given computer has a “Word Size”

Nominal size of integer-valued data a,d of addresses.

Some machines used 32 bits (4 bytes) as word size, Limits addresses to 4GB.

Increasingly, machines have 64-bit word size.

Potentially, could have 18 PB(petabytes) of addressable memory

A feature

If we compile a program using GCC is the standard compiler, we can specify either we want it to be 64 bit code or 32 bit code as a flag, and it will actually generate two different kinds of object code as a result.

The hardware itself doesn’t necessarily define what the word size is, it’s a combination of the hardware and the compiler that determines.

Word-Oriented Memory Organization

The memory itself is a series of bytes, but we can group those into blocks of words of different word sizes, the way is usually by assuming that the address of the word is the lowest value address in it.

show_bytes Execution Example

1
2
3
int a = 15312;
printf("int a = 15213;\n");
show_bytes((pointer) &a, sizeof(int));

Result(Linux x86-64):

1
2
3
4
5
int a = 15213; 00003b6d
0x7fffb7f71dbc 6d
0x7fffb7f71dbd 3b
0x7fffb7f71dbe 00
0x7fffb7f71dbf 00

Representing Strings

Strings in C

Represented by array of characters, each character encoding in ASCII format.

Standard 7-bit encoding of character set

String should be null-terminated, final character = 0