HW 03 - Bits and Bytes

Class: CSCE-312

Notes:

Question 1

Write a function is_little_endian that will return 1 when compiled and run on a little-endian machine, and will return 0 when compiled and run on a big-endian machine. This program should run on any machine, regardless of its word size.

Answer:

// Check if the machine is Little-endian or Big-endian based on first byte in memory
int check_machine() {
    // Cast the address of an int to an unsigned char*  
    int a = 1;
    pointer start = (pointer)&a;    // since &a is of type int*, we need a cast

    // Check the first byte in memory
    if (start[0] == 1) {
        return 1;   // Little-endian 
    }
    else {
        return 0;   // Big-endian
    }
}

Question 2

Write a C expression that will yield a word consisting of the least significant byte of x, and the remaining bytes of y. For operands x = 0x89ABCDEF and y = 0x76543210, this would give 0x765432EF.

Dealing with hexadecimal in C

In C, numbers starting with 0x are hex literals.

What are masks?

A mask is just a number where the binary pattern of 1s and 0s selects which bits you want to keep.

Example:

Value:  10101101
Mask:   00001111
Result: 00001101   (kept only the low 4 bits)
How to use a mask in C?

You apply a mask with the bitwise AND operator &.

int x = 0xABCD1234;
int lsb_only = x & 0xFF;   // keeps only the lowest 8 bits
How to "clear" the least significant byte?

You can invert (~) a mask.

Example:

int y = 0xAABBCCDD;
int cleared = y & ~0xFF;   // clears the lowest byte, keeps the others

Answer:

    // Perform bitwise AND (&) to apply lowest 8 bit mask
    int lsb_x = x & 0xFF;           // mask to keep only the lowest 8 bits
    int clear_lsb_y = y & ~0xFF;    // negated mask (clears lowest 8 bits)

    // OR (|) both masked hex ints to get the combination (lsb_x replaces 0s in y)
    int result = lsb_x | clear_lsb_y;

Question 3

Write a function with the following prototype:

/* Determine whether arguments can be subtracted without overflow */
int tsub_ok (int x, int y);

This function should return 1 if the computation x - y does not overflow, 0 otherwise.

What happens when you XOR the sign bits

Suppose we only look at the MSB (sign bit):

Now XOR truth table for MSB only:

MSB(x)   MSB(y)   MSB(x ^ y)
   0        0          0
   1        1          0
   0        1          1   <- different signs
   1        0          1   <- different signs

So:

Why the rest of the bits don’t matter

Sure, x ^ y also flips all the lower bits, but the sign of the XOR result is controlled only by its MSB. That’s why the check (x ^ y) < 0 is effectively “are the sign bits different?”

Note when overflow happens
// In (x - y) overflow can only happen when x and y have different signs (magnitude increases)
//      x = INT_MAX, y = -1     ->      x + (-(-y)) = x + y     OVERFLOW!
//      x = INT_MIN, y = 1      ->      (-x) + (-y) = (-x) - y  OVERFLOW! 
//      x = -1, y = INT_MAX     ->      (-x) + (-y) = (-x) - y  OVERFLOW!
//      x = 1, y = INT_MIN      ->      x + (-(-y)) = x + y     OVERFLOW!

// Additionally, for overflow to happen x and result need to have different signs since that would mean a signed "wrap around" happened

Answer:

/* Determine whether arguments can be subtracted without overflow (safe version)*/
int tsub_ok (int x, int y) {
    // Overflow if result < INT_MIN: x + (-y) < INT_MIN == x < INT_MIN + y
    if (y > 0 && x < INT_MIN + y) {
        return 0;
    }

    // Overflow if result > INT_MAX: x + (-y) > INT_MAX == x > INT_MAX + y
    else if (y < 0 == 1 && x > INT_MAX + y) {
        return 0;
    }

    // Operation (x - y) does not overflow
    return 1;
}

/* Determine whether arguments can be subtracted without overflow (unsafe version)*/
int tsub_ok_unsafe (int x, int y) {
    // Compute sign of the result (will "wrap around" if overflow happens)
    int r = x - y;              // Udefined behavior if this overflows

    // (x ^ y) < 0 == “sign bits of x and y are different.”
    // Overflow iff: (signs of x and y differ) AND (sign of result differs from x)
    int overflow = ((x ^ y) & (x ^ r)) < 0;     
    return !overflow;           // Returning 1 if not overflow, 0 otherwise.
}

Question 4

We are running programs on a machine where values of type int are 32 bits. They are represented in two's complement, and they are right shifted arithmetically. Values of type unsigned are also 32 bits.

We generate arbitrary values x and y, and convert them to unsigned values as follows:

/* Create some arbitrary values */
int x = random();
int y = random();
/* Convert to unsigned */
unsigned ux = (unsigned) x;
unsigned uy = (unsigned) y;

For each of the following C expressions, you are to indicate whether or not the expression always yields 1. If it always yields 1, describe the underlying mathematical principles. Otherwise, give an example of arguments that make it yield 0.

  1. (x < y) == (-x > -y)
  2. ((x + y) << 4) + y - x == 17y + 15x
  3. ~x + ~y + 1 == ~(x+y)
  4. (ux - uy) == -(unsigned) (y - x)
  5. ((x >> 2) << 2) <= x

A. (x < y) == (-x > -y)

Miloax38