[CS15-213] Bits, Bytes, and Integers

Posted on | In |

Boolean Algebra

  • A&B = 1 when A=1 and B=1
  • A|B = 1 when either A=1 or B=1
  • ~A=1 when A=0
  • A^B=1 when either A=1 or B=1, but not both

Example: Representing & Manipulating Sets

  • Representation
    • Width w bit vector represents subsets of {0, …, w-1}
    • 01101001 {0, 3, 5, 6}
    • 76543210
    • 01010101 {0,2,4,6}
  • Operations
    • &: 01000001 {0, 6}
    • |: 01111101 {0, 2, 3, 4, 5, 6}
    • ^: 00111100 {2, 3, 4, 5}
    • ~: 10101010 {1, 3, 5, 7}

Shift Operations

  • Left Shift: x << y Shift bit-vector x left y positions, throw away extra bits on left, fill with 0 on right
  • Right Shift: x >> y Shift bit-vector x right y positions
    • Logical shift: Fill with 0 on the left
    • Arithmetic shift: Replicate most significant bit on the left
  • Undefined behavior: Shift amount < 0 or >= word size

Numeric Ranges

  • Unsigned Values
    • UMin = 0
    • UMax = 2^w - 1
      1 1 1 1 1 -> 31
  • Complete Values
    • TMin = -2^(w-1)
      1 0 0 0 0 -> -16
    • TMax = 2^(w-1) - 1
      0 1 1 1 1 -> 15
  • Unsigned and Signed Numeric Values
    • Equivalence
      • Same encodings for nonnegative values
    • Uniqueness
      • Every bit pattern represents unique integer value
      • Each representable integer has unique bit encoding
    • Can Invert Mappings
      • U2B(X)

  • Conversion

  • Signed and Unsigned in C

    • Constants
      • By default are considered to be signed integers
      • Unsigned if have “U” as suffix: 0U, 42949U

    • Casting

      • Explicit casting between signed & unsigned same as U2T and T2U

        1
        2
        3
        4
        int tx, ty;
        unsigned ux, uy;
        tx = (int) ux;
        uy = (unsigned) ty;

      • Implicity cating also occurs via assignments and procedure calls

        1
        2
        tx = ux;
        uy = ty;

  • Casting Surprises

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

|TMax| = |TMin| - 1
UMax = 2TMax + 1

1
2
3
4
unsigned i;
for (i = n - 1; i >= 0; i--) {
    f(a[i]);
}

The above loop will enter an infinite loop

1
2
3
4
int i;
for (i = n - 1; i - sizeof(char) >= 0; i--) {
    f(a[i]);
}
  • Sign Extension
    • Task:
      • Given w-bit signed integer x
      • Convert it to w + k bit integer with same value
    • Rule:
      • Make k copies of sign bit:
    • Unsigned case: filling with trailing 0s