Each bit is 0 or 1#

By encoding/interpreting sets of bits in various ways#

• Computers determine what to do (instructions)
• … and represent and manipulate numbers, sets, strings, etc…

Why bits? Electronic Implementation#

• Easy to store with bitsable elements
• Reliably transmitted on noisy and inaccurate wires
• Easy to indicate low level/high level

Representation#

We can use bits to determine whether an element belongs to a set. Say each bit have index, which corresponds to a number from zero. If a bit is set to 1, it means the corresponding index (i.e., the element) is in the set. Otherwise, its not.

In a more mathematical representation way:

• Width $w$ bit vector represents subsets subsets of $\{0,\ ...,\ w-1\}$
• $a_{j} =1$ if $j\in A$

Sets Operations#

• & is related to Intersection
• | is related to Union
• ~ is related to Complement
• ^ is related to Symmetric difference

Shift Operations#

• Left Shift: x << y

  • Shift bit-vector x left y positions
    • Throw away extra bits on left
  • Fill with 0’s on right

• Right Shift: x >> y

  • Shift bit-vector x right y positions
    • Throw away extra bits on right
  • Logical shift
    • Fill with 0’s on left
  • Arithmetic shift
    • Replicate most significant bit on left

Undefined Behaviour#

• Shift amount $<$ 0
• Shift amount $\geqslant$ word size
• Left shift a signed value

Unsigned#

$\displaystyle B2U( X) =\sum _{i=0}^{w-1} x_{i} \cdot 2^{i}$

Two’s Complement#

$\displaystyle B2T( X) =-x_{w-1} \cdot 2^{w-1} +\sum _{i=0}^{w-2} x_{i} \cdot 2^{i}$

Numeric Ranges#

• Unsigned Values

  • $\displaystyle UMin\ =\ 0$
  • $\displaystyle UMax\ =\ 2^{w} -1$

• Two’s Complement Values

  • $\displaystyle TMin = -2^{w-1}$
  • $\displaystyle TMax\ =\ 2^{w-1} -1$

TIP

In C, these ranges are declared in limits.h. e.g., ULONG_MAX, LONG_MAX, LONG_MIN. Values are platform specific.

Difference between Unsigned & Signed Numeric Values#

The difference between Unsigned & Signed Numeric Values is $2^{w}$.

For example, if you want convert a unsigned numeric value to its signed form, just use this value minus $2^{w}$, or if you want convert a signed numeric value to its unsigned form, you plus $2^{w}$.

Constants#

• By default are considered to be signed integers.
• Unsigned if have “U” as suffix

Casting#

• Explicit casting between signed & unsigned same as $U2T$ and $T2U$
• Implicit casting also occurs via assignments and procedure call (assignments will casting to lhs’s type)

Expression Evaluation#

• If there is a mix of unsigned and signed in single expression, signed values implicitly cast to unsigned
• Including comparison operations <, >, ==, <=, >

Sign Extension#

• Make $k$ copies of sign bit
• $\displaystyle X\prime =X_{w-1} ,...,X_{w-1} ,X_{w-1} ,X_{w-2} ,...,X_{0}$

WARNING

Converting from smaller to larger integer data type. C automatically performs sign extension.

Expanding (e.g., short int to int)#

• Unsigned: zeros added
• Signed: sign extension
• Both yield expected result

Truncating (e.g., unsigned to unsigned short)#

• Unsigned/signed: bits are truncated
• Result reinterpreted
• Unsigned: mod operation
• Signed: similar to mod
• For small numbers yields expected behavior

Unsigned Addition#

• Standard Addition Function
  • Ignore carry output
• Implements Modular Arithmetic
  • $\displaystyle UAdd_{w}( u,v) =( u+v)\bmod 2^{w}$

Visualizing (Mathematical) Integer Addition#

• Integer Addition
  • 4-bit integers $u,v$
  • Compute true sum $Add_{4}( u,v)$
  • Values increase linearly with $u$ and $v$
  • Forms planar surface

Visualizing Unsigned Addition#

• Wraps Around
  • If true sum $\geqslant 2^{w}$
  • At most once

Two’s Complement Addition#

• $TAdd$ and $UAdd$ have Identical Bit-level Behaviour

Signed vs. unsigned addition in C:

1
int s, t, u, v;
2

3
s = (int)((unsigned)u + (unsigned)v);
4
t = u + v;
5

6
// will give s == t

TAdd Overflow#

• Functionality
  • True sum requires $w+1$ bits
  • Drop off MSB
  • Treat remaining bits as two’s complement integer

Visualizing Two’s Complement Addition#

• Values

  • 4-bit two’s comp.
  • Range from $-8$ to $+7$

• Wraps Around

  • If sum $\geqslant 2^{w-1}$
    • Becomes negative
    • At most once
  • If sum $< -2^{w-1}$
    • Becomes positive
    • At most once

Multiplication#

• Goal: Computing Product of $w$-bit numbers $x,y$
  • Either signed or unsigned
• But, exact results can be bigger than $w$ bits
  • Unsigned: up to $2w$ bits
    • Result range: $0\leqslant x\cdot y\leqslant \left( 2^{w} -1\right)^{2} =2^{2w} -2^{w+1} +1$
  • Two’s complement min (negative): Up to $2w-1$ bits
    • Result range: $x\cdot y\geqslant \left( -2^{w-1}\right) \cdot \left( 2^{w-1} -1\right) =-2^{2w-2} +2^{w-1}$
  • Two’s complement max (positive): Up to $2w$ bits, but only for $( TMin_{w})^{2}$
    • Result range: $x\cdot y\leqslant \left( -2^{w-1}\right)^{2} =2^{2w-2}$
• So, maintaining exact results…
  • would need to keep expanding word size with each product computed (exhaust memory faster)
  • is done in software, if needed
    • e.g., by “arbitrary precision” arithmetic packages

Unsigned Multiplication in C#

• Standard Multiplication Function
  • Ignore high order $w$ bits
• Implements Modular Arithmetic
  • $\displaystyle UMult_{w}( u,v) =( u\cdot v)\bmod 2^{w}$

Signed Multiplication in C#

• Standard Multiplication Function
  • Ignore high order $w$ bits
  • Some of which are different for signed vs. unsigned multiplication
  • Lower bits are the same

Power-of-2 Multiply with Shift#

• Operation
  • u << k gives $u\cdot 2^{k}$ (basically increases each bits weight)
  • Both signed and unsigned

Unsigned Power-of-2 Divide with Shift#

• Quotient of Unsigned by Power of 2
  • u >> k gives $\left\lfloor u/2^{k}\right\rfloor$
  • Uses logical shift

Signed Power-of-2 Divide with Shift#

• Quotient of Signed by Power of 2
  • Uses arithmetic shift
  • Want $\lceil x/2^{k} \rceil$ (Round toward 0)
  • Compute as $\left\lfloor \left( x+2^{k} -1\right) /2^{k}\right\rfloor$
    • In C: (x + (1 << k) - 1) >> k
    • Biases dividend toward 0

Case 1: No rounding#

Case 2: Rounding#

Normalized Values#

When: $exp\neq 000\dotsc 0$ and $exp\neq 111\dotsc 1$

• Exponent coded as a biased value: $E=exp-bias$
  • $exp$ is unsigned value of exp field
  • $bias=2^{k-1} -1$, where $k$ is number of exponent bits
    • Single precision: $127$ ($exp\in [ 1,254]$, $E\in [ -126,127]$)
    • Double precision: $1023$ ($exp\in [ 1,2046]$, $E\in [ -1022,1023]$)
• Significand coded with implied leading $1$: $M=1.xxx\dotsc x_{2}$
  • $xxx\dotsc x$ is bits of frac field
  • Minimum when $frac=000\dotsc 0\ ( M=1.0)$
  • Maximum when $frac=111\dotsc 1\ ( M=2.0-\epsilon )$
  • Get extra leading bit for “free”

Normalized Encoding Example#

• Value: float F = 15213.0;

  • $15213_{10} =11101101101101_{2} =1.1101101101101\times 2^{13}$

• Significand

  • $M=( 1.) 1101101101101_{2}$
  • $frac=11011011011010000000000_{2}$

• Exponent

  • $E=13$
  • $bias=127$
  • $exp=140=10001100_{2}$

So the result would be:

1
# manually calculate
2
((-1)**0)*(1+1/2+1/4+1/16+1/32+1/128+1/256+1/1024+1/2048+1/8192)*(2**13) == 15213.0
3

4
# by struct package
5
import struct
6

7
bits = 0b01000110011011011011010000000000
8
f = struct.unpack("f", struct.pack("I", bits))[0]
9

10
print(f)

Denormalized Values#

• Condition: $exp=000\dotsc 0$
• Exponent value: $E=1-bias\ ( instead\ of\ E=0-bias)$
• Significand coded with implied leading $0$: $M=0.xxx\dotsc x_{2}$
  • $xxx\dotsc x$ is bits of frac field
• Cases
  • $exp=000\dotsc 0,frac=000\dotsc 0$
    • Represents zero value
    • Note distinct values: $+0$ and $-0$
  • $exp=000\dotsc 0,farc\neq 000\dotsc 0$
    • Numbers closet to $0.0$
    • Equispaced

Special Values#

• Condition: $exp=111\dotsc 1$

• Case: $exp=111\dotsc 1,frac=000\dotsc 0$

  • Represents value $\infty$
  • Operation that overflows
  • Both positive and negative
  • E.g., $1.0/0.0=-1.0/-0.0=+\infty ,1.0/-0.0=-\infty$

• Case: $exp=111\dotsc 1,frac\neq 000\dotsc 0$

  • Not-a-Number (NaN)
  • Represents case when no numeric value can be determined
  • E.g., $\sqrt{-1} ,\infty -\infty ,\infty \cdot 0$

Tiny Floating Point Example#

Think about this 8-bit Floating Point Representation below, it obeying the same general form as IEEE Format:

Dynamic Range (Positive Only)#

Distribution of Values#

Still think about our tiny example, notice how the distribution gets denser toward zero.

Here is a scaled close-up view:

Basic idea#

• First compute exact result
• Make it fit into desired precision
  • Possibly overflow if exponent too large
  • Possibly round to fit into frac

Closer Look at Round-To-Even#