CSAPP Data Lab

Timeline

Timeline

2025-03-07

Writing up to howManyBits

2025-03-07

Finished writing. I feel once again that this experiment is good.

This article introduces the problem-solving approach and implementation process of the CSAPP Data Lab experiment. The author set up the experimental environment in Win10 WSL2 and completed the function implementations in bits.c one by one. The article explains in detail the bitwise solutions for problems such as bitXor, tmin, isTmax, allOddBits, negate, isAsciiDigit, conditional, and isLessOrEqual, including techniques such as using equivalence laws from discrete mathematics to implement XOR, using two's complement properties to find the minimum integer, determining the maximum value via XOR, constructing masks to detect odd bits, using arithmetic right shift to extract the sign bit to determine the value range, and implementing the ternary operator through conditional expressions and addition operations. At the same time, the article emphasizes the restrictions on operators and constants in the experiment, and provides methods to avoid boundary ambiguity.

Recently, as a teaching assistant for Computer Systems, I need to evaluate this CSAPP experiment. I had done it during my undergraduate studies, but after so long I had basically forgotten it, so I did it again and documented it here.

Experiment Environment Setup

I did it in the Win10 WSL2 environment:

Experiment Environment

For details on how to set up the environment, refer to the link below. There is a script to set up the runtime environment with one click, which is very convenient:

CSAPPEnvironment setup

https://zhuanlan.zhihu.com/p/505497911

Introduction

Complete the function implementations in bits.c, but with certain restrictions on the code.

# Check whether the code meets the required specifications.
./dlc bits.c
# View Score
make clean 
make 
./btest

Experiment Content

bitXor

Problem:

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) { 
  return 2;
}

It is required to implement XOR using only ~ (bitwise NOT) and & (bitwise AND). You can use equivalence laws from discrete mathematics. XOR means ‘same is 0, different is 1’:

$$x \oplus y = \lnot (\lnot x \land \lnot y) \land \lnot ( x \land y)$$

int bitXor(int x, int y) { 
  return ( ~(~x & ~y)) & (~(x & y));
}

tmin

Problem:

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 2;
}

Return the smallest two’s complement integer. The definitions of sign-magnitude, ones’ complement, and two’s complement are as follows:

Representation Method	Definition
Sign-Magnitude	The highest bit is the sign bit (0 for positive, 1 for negative), and the remaining bits represent the absolute value of the number.
Ones’ Complement	The ones’ complement of a positive number is the same as its sign-magnitude; the ones’ complement of a negative number is obtained by keeping the sign bit unchanged and inverting the remaining bits.
Two’s Complement	The two’s complement of a positive number is the same as its sign-magnitude; the two’s complement of a negative number is its ones’ complement plus 1.

The encoding of two’s complement is asymmetric. Except for the smallest negative number, every other negative number has a corresponding positive number. In this experiment, int is 32 bits, and the range of two’s complement representation is:

• Minimum negative number: 0x80000000 (i.e., -2^31)
• Maximum positive number: 0x7FFFFFFF (i.e., 2^31 - 1)

int tmin(void) {
  return 1 << 31;
}

isTmax

Problem:

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  return 2;
}

• Return 1 if x is the maximum two’s complement value, otherwise return 0.
• The maximum value is 0x7FFFFFFF. Its characteristic is that the most significant bit is 0 and the rest are 1. After 0x7FFFFFFF + 0x1, it becomes 0x80000000, where the most significant bit is 1 and the rest are 0, exactly the opposite.
• Here we need to use the property of XOR. For example, x ^ target: x is XORed with target. Since XOR gives 1 for different bits and 0 for same bits, x ^ target is 0x0 only when x and target are exactly the same. Then adding the ! operator gives !(x ^ target), which is 1 when x and target are the same and 0 when they differ.
  For 0x7FFFFFFF, after adding 1 it becomes 0x80000000. Since the characteristics are exactly opposite, after bitwise complement it becomes 0x7FFFFFFF again. Therefore, we can use XOR to determine whether they are the same, i.e., !(~(x+1)^x).
• Think further: is 0x7FFFFFFF the only value that satisfies this property: after adding 1, it is equivalent to bitwise complement? Obviously 0xFFFFFFFF also satisfies this property, because when overflow occurs, the most significant bit is discarded and it becomes 0x0. Therefore, we also need to construct an expression to AND with !(~(x+1)^x), denoted as expression1, i.e., !(~(x+1)^x) & expression1. When x is 0x7FFFFFFF, expression1 is 1; when x is 0xFFFFFFFF, it is 0.
• The exclusion method must use the characteristic that 0x7FFFFFFF has but 0xFFFFFFFF does not, i.e., the difference between these two numbers. The simplest difference is that 0x7FFFFFFF + 0x1 becomes 0x80000000, a nonzero number, while 0xFFFFFFFF + 0x1 becomes 0. Therefore, !(x+1) is 0 when x is 0x7FFFFFFF and 1 when x is 0xFFFFFFFF. !(x+1) is exactly the opposite of what we need, so adding one more ! operation gives:

!( ~(x + 1) ^ x) & !!(x + 1)

int isTmax(int x) {
  return !( ~(x + 1) ^ x) & !!(x + 1);
}

allOddBits

Problem:

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  return 2;
}

• Return 1 if all odd-positioned bits are 1, otherwise return 0. That is, a number returns 1 as long as its 1st, 3rd, 5th, 7th, … bits are 1 (the remaining bits don’t matter), otherwise return 0.
• We can remove the influence of all even-positioned bits and look at the odd-positioned bits. For example, AND x with 0xAAAAAAAA, then all even-positioned bits become 0, and then check whether it is the same as 0xAAAAAAAA (using the method of determining whether two numbers are the same via XOR, as described in isTmax). Alternatively, OR x with 0x55555555, then all even-positioned bits become 1, and then check whether it is the same as 0xFFFFFFFF. That is:

!((x|0x55555555)^0xFFFFFFFF)

!((x&0xAAAAAAAA)^(0xAAAAAAAA))

• However, due to the constraints of the lab requirements, you cannot directly write something like 0xAAAAAAAA; you can only write 0xAA and obtain 0xAAAAAAAA through bit operations.

Note: According to the C standard, shift operations have lower precedence than addition and subtraction.

C language operator precedence table

int allOddBits(int x) {
  // return !((x|0x55555555)^0xFFFFFFFF);
  // return !((x&0xAAAAAAAA)^(0xAAAAAAAA));
  int a = 0xAA<<8;//0x00AA
  int b = a | 0xAA;//0xAAAA
  int c = b<<16 | b;//0xAAAAAAAA
  return !((x&c)^c);
}

negate

Problem:

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) { 
  return 2;
}

• Return the negative of x
• We know:

x+(-x)=0

x+(~x)=-1

• Subtracting the two expressions gives:

-x=~x+1

int negate(int x) { 
  return ~x+1;
}

isAsciiDigit

Problem:

/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  return 2;
}

• Detect whether x is an ASCII digit. Simply put, determine whether x is between 0x30 and 0x39.
• In assembly, comparing magnitudes is done by setting flags through subtraction. Therefore, we can determine this by subtracting x from the boundary value and then taking the sign bit. To determine0x30 <= x <= 0x39when, if we directly compute0x30 - xwhen x is exactly 0x30, the result is 0 and the sign bit is 0, which is inconsistent with the sign bit 1 when x > 0x30, making it inconvenient to handle. Therefore, tighten the left inequality to strict less than, and change<=to<：

0x30<= x <= 0x39

The above expression is equivalent to:

0x2F< x <= 0x39

In this way, the left side0x2F - x < 0the sign bit is always 1 (no boundary ambiguity). The right sidex <= 0x39does not need an equivalent transformation, because when the boundary x=0x390x39 - x = 0The sign bit is 0, which exactly meets the requirement; converting would instead exclude the boundary.
Let0x2F - xthe sign bit is 1,0x39 - xthe sign bit is 0; both must be satisfied simultaneously. First look at0x2F < xAfter subtraction, how do we extract the sign bit? We can use arithmetic right shift by 31 bits to fill the entire 32 bits with the sign bit. That is, if0x2F - x < 0, then(0x2F + (~x + 1)) >> 31is0xFFFFFFFF, if0x2F - x >= 0, the result is 0:

(0x2F+(~x+1))>>31

Now considerx <= 0x39, using the same method, if0x39 - x < 0, then(0x39 + (~x + 1)) >> 31is0xFFFFFFFF, if0x39 - x >= 0, the result is 0; we can take the complement to satisfy the requirement:

~((0x39+(~x+1))>>31)

We need to satisfy both conditions above, so

(0x2F + (~x + 1)) >> 31 & ~((0x39 + (~x + 1)) >> 31)

Since we finally return 1 or 0, we just take the least significant bit:

(0x2F + (~x + 1)) >> 31 & ~((0x39 + (~x + 1)) >> 31) & 0x1

int isAsciiDigit(int x) {
  int low = (0x2F + (~x + 1)) >> 31;  // 0x2F - x < 0 => x > 0x2F (i.e., x >= 0x30)
  int high = ~((0x39 + (~x + 1)) >> 31);  // 0x39 - x >= 0 => x <= 0x39
  return low & high & 0x1;
}

conditional

Problem:

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  return 2;
}

• The conditional expression is the same as x ? y : z
• To implement this kind of decision based on the value of x to return y or z, using only bitwise operations is very difficult, because although it is easy to determine whether x is 0, it is hard to associate x with y and z at the same time. So we pin our hopes on addition. Suppose we return an expression like this:

a+y+z

When x != 0, let a = -z = ~z + 1; when x == 0, let a = -y = ~y + 1, and the requirement is satisfied. But this requirement is also hard to satisfy, because a is related to both y and z, and a is determined by whether x is 0. So we consider splitting a:

b+c+y+z

When x is nonzero, let b = 0, c = -z = ~z + 1; when x is 0, let b = -y = ~y + 1, c = 0. This way b is related only to y, and c only to z.
First we need to determine whether x is 0; this is not hard, just use the ! operation: when x is nonzero, !x is 0; when x is 0, !x is 1. Let’s focus on b first. When !x == 0, b should be 0; when !x != 0, b should be ~z + 1. Obviously an AND operation can satisfy this:

b = !x&(~y+1)

But when !x != 0, !x == 1, and bitwise ANDing it with ~z + 1 leaves only the least significant bit, which is not necessarily ~z + 1. Therefore we need to get 0xFFFFFFFF when x != 0 and 0 when x == 0, so we define a:

a = ~(!x)+1

When x is 0, !x == 1, ~(!x) == 0xFFFFFFFE, a == 0xFFFFFFFF; when x is nonzero, !x == 0, ~(!x) == 0xFFFFFFFF, a == 0. Therefore the expression for b should be

b = a&(~y+1)

Now consider c. c’s situation is exactly the opposite of b, so we just need to add another ~ to a.

c = ~a&(~z+1)

Here there is no need to worry about addition overflow.

int conditional(int x, int y, int z) {
  int a = ~(!x)+1;
  int b = a&(~y+1);
  int c = ~a&(~z+1);
  return b+y+c+z;
}

isLessOrEqual

Problem:

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
  return 2;
}

• If x <= y, return 1; otherwise return 0.
• To compare magnitudes, use subtraction. Let y-x. If y-x >= 0, i.e., the sign bit is 0, return 1; if y-x < 0, i.e., the sign bit is 1, return 0. y-x = y + ~x + 1. Then shift right by 31 bits to get the sign bit. We need a negation operation so that sign bit 0 returns 1 and sign bit 1 returns 0:

~((y+(~x+1))>>31) & 0x1

int isLessOrEqual(int x, int y) {
  return ~((y+(~x+1))>>31) &0x1;
}

logicalNeg

Problem:

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  return 2;
}

• Implement the ! operator: for !x, return 1 when x is 0, and return 0 when x is nonzero.
• The most intuitive difference between 0 and nonzero is that every bit of 0 is 0, while a nonzero number has at least one bit that is 1. But since we cannot use circular shift operations to check this, we have to find another way.
• Another difference between 0 and nonzero numbers is that the negative of 0 is still 0, i.e., ~0 + 1 = 0, while the negative of a nonzero number is not 0. We can use this: check whether x’s negative is the same as x itself. Earlier we used a trick with XOR to determine whether two numbers are the same: this expression returns 0 when x equals 0, and returns nonzero when x is nonzero, but that is as good as doing nothing.

(~x+1)^x

We can use another point: the sign bit of a nonzero number’s negative is definitely opposite to that of the original number; one must be 1 and the other must be 0. For 0, the sign bit of its negative and the sign bit of 0 are both 0. Therefore we only need to AND the two together: when nonzero, the sign bit of this expression is 1; when 0, the sign bit of this expression is 0.

(~x+1)|x

Next, extract the sign bit and also invert it, because we need to return 1 when it is 0 and return 0 when it is 1. We used this trick in the previous problem: arithmetic right shift by 31 bits, then invert, then AND with 0x1 to get the lowest bit:

~(((~x+1)|x)>>31) & 0x1

int logicalNeg(int x) { 
   return ~(((~x+1)|x)>>31) & 0x1;
}

howManyBits

Problem:

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  return 0;
}

• Return the number of bits needed to represent x in two’s complement form. Essentially, find the position of the highest 1 bit in the number, then add 1 for the sign bit. This problem is somewhat difficult, mainly because it is hard to think of. Below is someone else’s implementation.
• Here we use a binary search approach:
  First consider positive numbers and 0.

1. High 16 bits: check whether the high 16 bits contain a 1. If so, at least 16 bits are needed.
2. High 8 bits: within the remaining 16 bits, check whether the high 8 bits contain a 1.
3. High 4 bits: within the remaining 8 bits, check whether the high 4 bits contain a 1.
4. High 2 bits: within the remaining 4 bits, check whether the high 2 bits contain a 1.
5. High 1 bit: within the remaining 2 bits, check whether the high 1 bit contains a 1.
6. Lowest bit: the final remaining 1 bit.
   Finally, add up the bit counts of all parts, and add 1 (the sign bit).

• Handling negative numbers:
  flag is x >> 31, i.e., the sign bit. If x is negative, flag is 1; otherwise it is 0.

1. If x is negative (flag == 1), then x is inverted: x = ~x.
2. If x is nonnegative (flag == 0), x remains unchanged.
   In the two’s complement representation of a negative number, the sign bit and the magnitude part are mixed together. If you directly compute the number of significant bits of a negative number, the sign bit will cause an incorrect result. For example:
   The two’s complement of -1 is 11111111 11111111 11111111 11111111. If you directly compute the number of bits, you would get 32 bits, but in fact we only care about its significant bits.
   Through the bitwise NOT operation, the two’s complement representation of a negative number is converted into a positive number, and the number of significant bits in its binary representation is the same as that of the original negative number. For example:

• The two’s complement of -1 is 11111111 11111111 11111111 11111111; after bitwise NOT it becomes 00000000 00000000 00000000 00000000, with 1 significant bit.
• The two’s complement of -2 is 11111111 11111111 11111111 11111110; after bitwise NOT it becomes 00000000 00000000 00000000 00000001, with 2 significant bits.

howManyBits

https://zhuanlan.zhihu.com/p/559005736

int howManyBits(int x) {
  int b16, b8, b4, b2, b1, b0;
  int flag = x >> 31;
  x = (flag & ~x) | (~flag & x);  // If the sign bit of x is 0, it remains unchanged; if the sign bit of x is 1, take the bitwise NOT.
  b16 = !!(x >> 16) << 4; 
  x >>= b16;  
  b8 = !!(x >> 8) << 3;
  x >>= b8;
  b4 = !!(x >> 4) << 2;
  x >>= b4;
  b2 = !!(x >> 2) << 1;
  x >>= b2;
  b1 = !!(x >> 1);
  x >>= b1;
  b0 = x;
  return b0 + b1 + b2 + b4 + b8 + b16 + 1;
}

floatScale2

Problem:

/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  return 2;
}

• Multiply a single-precision floating-point number (float) by 2, and return the binary representation of the result. The input and output of the function are both of type unsigned int, but they actually represent the binary bit pattern of a single-precision floating-point number. When the input is NaN, just return the input. Also, finally we can use if and while 😭😭😭

• Let’s review first.IEEE 754Knowledge about floating-point numbers:

IEEE 754 representation format

Single-precision float, double-precision double

For floating-point numbers represented by IEEE 754, there are three categories in total.

Category 1: Normalized numbers

Denormalized numbers are used to represent extremely small values close to zero, preventing floating-point underflow and ensuring the continuity of floating-point arithmetic.

Category 2: Denormalized numbers

Category 3: Special values

IEEE 754 representation range

First, we extract the sign bit sign, the mantissa frac, and the exponent exp:

sign=uf>>31&0x1

frac=uf&0x7FFFFF

exp = (uf&0x7f800000)>>23

Based on the exponent, determine whether this floating-point number is a normalized number, a denormalized number, or which kind of special case it is.

unsigned floatScale2(unsigned uf) { 
  unsigned exp = (uf&0x7f800000)>>23;
  unsigned sign=uf>>31&0x1;
  unsigned frac=uf&0x7FFFFF;
  if(exp == 0){//For a denormalized number, the exponent is 0; just multiply frac by 2.
    frac <<= 1;
    return (sign << 31) | (exp << 23) | frac;
  }else if(exp==0xFF){//Special case: NaN
    return uf;
  }else{
    exp++;//Multiplying by 2 is equivalent to E+1.
    return (sign << 31) | (exp << 23) | frac;
  }
}

floatFloat2Int

Problem:

/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  return 2;
}

• Represent the input IEEE 754 floating-point number as an int; if it exceeds the representable range, return 0x80000000u.
• If it is a denormalized number, directly return 0; if it is a special case, directly return 0x80000000u.
• If it is a normalized number, we first need to determine whether it exceeds the int representable range. int has 32 bits in total, one bit is the sign bit, the maximum is 2^31-1, and the minimum is -2^31. Therefore, the exponent E cannot exceed 30 (when E is 31, shifting left by E bits will overwrite the sign bit); when the exponent E is less than 0, it means the number is less than 1, so directly return 0; also:
• sign 1 bit
• exp 8 bits
• frac 23 bits

$$V = (-1)^{sign} \times 2^{exp - 127} \times (1 + frac)$$

We can view it as 1frac(the 24th bit is 1, bits 1~23 form frac), and at this time it is equivalent to being 1.frac(integer part is 1, fractional part is frac) left-shifted by 23 bits. At this time the exponent is E, meaning it should be multiplied by 2^E, i.e., left-shifted by E bits. Therefore, when E is less than 23, it should be right-shifted by (23-E) bits to truncate the (23-E) bits after frac; when E is greater than 23, since it is equivalent to having already been left-shifted by 23 bits, it only needs to be left-shifted by another (E-23) bits.

int floatFloat2Int(unsigned uf) {
 unsigned exp = (uf & 0x7f800000) >> 23;
  unsigned sign = uf >> 31 & 0x1;
  unsigned frac = uf & 0x7FFFFF;
  if (exp == 0xFF) {  // Special cases
    return 0x80000000u;
  } else if (exp == 0) {  // Denormalized numbers
    return 0x0;
  } else {                   // Normalized numbers
    int E = exp - 127;  // Exponent; note that it should not be set to unsigned
    if (E >= 31) {           // Out of range
      return 0x80000000u;
    }else if(E<0){//If E<0, it means it is a number less than 1, return 0.
      return 0;
    }
    frac = frac | (1 << 23);  // Fill in the leading 1 of frac
    if (E < 23) {
      frac = frac >> (23 - E);
    } else {
      frac = frac << (E - 23);
    }
    if (sign == 0) {//Return positive or negative according to the sign bit.
      return frac;
    } else {
      return -frac;
    }
  }
}

floatPower2

Problem:

/* 
 * floatPower2 - Return bit-level equivalent of the expression 2.0^x
 *   (2.0 raised to the power x) for any 32-bit integer x.
 *
 *   The unsigned value that is returned should have the identical bit
 *   representation as the single-precision floating-point number 2.0^x.
 *   If the result is too small to be represented as a denorm, return
 *   0. If too large, return +INF.
 * 
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
 *   Max ops: 30 
 *   Rating: 4
 */
unsigned floatPower2(int x) {
    return 2;
}

• Compute 2.0^x, and return the unsigned representation under IEEE 754. If the result is too small, so small that even a denormalized number cannot represent it, return 0; if the result is too large, return +INF. Clearly, this problem mainly tests the representation range of IEEE 754.

ForSingle-precision float

• Sign bit: 1 bit
• Exponent exp: 8 bits
• Mantissa frac: 23 bits

Representation range

• Normalized numbers: exponent exp is neither all 0s nor all 1s,

$$V = (-1)^S \times 2^E \times M = (-1)^{sign} \times 2^{exp - bias} \times (1 + frac)$$

exp ranges from 1 to 254, E=Exp-Bias=Exp-127, so E is in the range -126≤E≤127; and for frac, the minimum value is 0 and the maximum value is 1-2^{-23}. Therefore, ignoring S:

$$V_{max} = (-1)^S \times 2^{127} \times (2-2^{-23}) = (-1)^S \times 2^{127} \times (2-2^{-23})$$

$$V_{min} = (-1)^S \times 2^{-126} \times (1+0) = (-1)^S \times 2^{-126}$$

• Denormalized numbers: exponent is all 0s

$$V = (-1)^S \times 2^E \times M = (-1)^{sign} \times 2^{1-Bias} \times (0 + frac)$$

The exponent exp is all 0s, E=1-Bias=1-127=-126, therefore:

$$V = (-1)^{sign} \times 2^{- 126} \times (0 + frac)$$

For frac, the minimum value is 0, but the smallest nonzero value that can be represented is 2^(-23); values between 0 and 2^(-23) cannot be represented. The maximum value is 1-2^(-23). Therefore, when frac is 0, the value is 0, but to compute the smallest nonzero representable value, set frac=2^(-23), ignoring S.

$$V_{max} = (-1)^S \times 2^{-126} \times (0+1-2^{-23}) = (-1)^S \times 2^{-126} \times (1-2^{-23})$$

$$V_{min} = (-1)^S \times 2^{-126} \times (0+2^{-23}) = (-1)^S \times 2^{-149}$$

• Special values

1. +infinity: all bits of exp are 1, frac is 0, S is 0.
2. -infinity: exp all bits are 1, frac is 0, S is 1
3. NaN: exp all bits are 1, frac is not 0

Therefore, based on the above analysis:

• When x > 127, return +INF
• When -126 <= x <= 127, it is a normalized number
• When -149 <= x < -126, it is a denormalized number
• When x < -149, it is too small to represent, return 0

unsigned floatPower2(int x) {
  if (x > 127) {  // Return +infinity, S=0, exp=0xFF, frac=0;
    return 0xFF << 23;
  } else if (-126 <= x && x <= 127) {  // Normalized number, exp = E + Bias = E + 127
    return (x + 127) << 23;
  } else if (-149 <= x && x < -126) {  // Denormalized number, exp=0, E=1-Bias=-126, 2^(-126)*frac
    return 1<<(23-(-x-126));//E already has 2^(-126). When frac is 0x1, it represents 2^(-23). Suppose input x is -127, then frac should be 2^(-1), i.e., 1 shifted left by 22 bits.
  } else {//x < -149, too small, return 0
    return 0;
  }
}