15-213 Class 03. Integers
*** P2. 2^n = (2^{n-1} + ... + 2^0) + 1
E.g., 16 + 8 + 4 + 2 + 1 = 31
*** UNSIGNED. B2U(X) = SUM{i=0,w-1} x_i * 2^i
w=3. 000 to 111 gives [0,7]
*** TWOCOMP. B2T(X) = -x_{w-1} * 2^i + SUM{i=0,w-2} x_i * 2^i
w=3. 000 to 011 gives [0,3]. 100 to 111 gives [-4,-1].
* ASYMMETRIC: TMIN has no positive counterpart
w=3. 100 (-4)
** U2T, T2U unsigned <--> two's complement. Don't change bits
w=3. 000 to 011 gives [0,3] in both cases. T2U(x) = x
100 to 111 gives [-4,-1] or [4,7]. T2U(x) = 8+x = 2^{w}+x
Derive from formulas. B2U(X) - B2T(x) = 2^{w-1} - (-2^{w-1})
Gives surprising results due to casting. In C, operands implicitly
cast to be same type. Signed --> Unsigned.
Examples for w=32
Type Relation
0 0U u =
-1 0 s <
-1 0U u >
2147483647 -2147483648 s >
2147483647U -2147483648 u <
-1 -2 s >
(unsigned) -1 -2 u >
2147483647 2147483648U u <
2147483647 (int) 2147483648U u >
Classic programming mistake
unsigned i;
(OK)
for (i = 1; i < cnt; i++)
a[i] += a[i-1];
(Not OK)
for (i = cnt-2; i >= 0; i--)
a[i] += a[i+1];
(More subtle: malloc returns size_t, which is unsigned long)
#define BUF 2048
int i;
for (i = BUF; i-sizeof(int) >= 0; i -= sizeof(int))
...
** SIZE CHANGES: Shorter: truncate. Longer: zero or sign extend
Example w=3 --> w=4
Unsigned. Just add 0.
Signed. 100 (-4) --> 1100 (-8+4) 111 (-4+2+1) --> 1111 (-8+4+2+1)
See that sign bit doubles weight, but compensate with bit w-2
Question:
char x = (char) 0xFF
Compare:
(unsigned) (int) x [4294967295 sign extend]
to
(unsigned) (unsigned char) x [255 zero extend]
What should be effect of:
unsigned u = (unsigned) x; [4294967295]
Rule: first change size, then change type]
** Arithmetic: Just drop higher bits.
Unsigned == Modular arithmetic:
* Addition
e.g., w=3: 4+4 = 8 --> 0 3+3 = 6 3 + 7 = 10 --> 2
Two's complement. Same idea, but weird results
e.g., w=3: -4+-4 = -8 --> 0 3+3 = 6 --> -2 3 + -1 = 2
Note that bit patterns same for above two examples. Isomorphic algebras.
--> Two's complement arithmetic is a group.
What are possible cases:
0 + anything: No overflow
Pos + Neg: No overflow
Pos + Pos: Can overflow to negative (get true sum - 2^w)
Neg + Neg: Can overflow to positive (get true sum + 2^w)
True Sum
Pos Over --> Neg
Pos --> Pos
Neg --> Neg
Neg Over --> Pos
* Multiplication: Same idea, but messier. True product could require 2w bits
Overall: Both unsigned & two's complement for RINGS
**Puzzles:
Assume 32-bit word size, two's complement.
int x = foo();
int y = bar();
unsigned ux = x;
unsigned uy = y;
Are following always true? Why / give counterexample
x < 0 ==> ((x*2) < 0)
False: TMin
ux >= 0
True
x & 7 == 7 ==> (x<<30) < 0
True. Must have lower 3 bits = 111. Shift gives upper 2 bits = 11
ux > -1
False. Only holds for (unsigned) -1 == UMax
x > y ==> -x < -y
False. -1, TMin
x * x >= 0
False. 50000
x > 0 && y > 0 ==> x + y > 0
False. TMax + TMax
x >= 0 ==> -x <= 0
True
x <= 0 ==> -x >= 0
False TMin