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