CSAPP Data Lab

Timeline

Timeline

2025-03-07

Wrote up to howManyBits

2025-03-07

Finished writing, once again feeling that this experiment is quite good

This article introduces the process of completing the CSAPP Data Lab experiment in a WSL2 environment, discusses in detail the implementation ideas of several restricted bitwise operation functions such as bitXor, tmin, and isTmax, and summarizes methods for solving logical problems under code constraints using two's complement properties, discrete mathematics equivalence calculus, and bitwise operation techniques.

Recently, as a teaching assistant for the Computer Systems course, I had to review this CSAPP experiment. I did this experiment during my undergraduate studies, but after so long, I had basically forgotten it all, so I redid it and recorded it here.

Experiment Environment Setup

I did it in the win10 WSL2 environment:

Experiment Environment

For specific instructions 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 implementation in bits.c, but there are certain restrictions on the code

# Check if the code meets the required specifications
./dlc bits.c
# Check 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 calculus in 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 has the same sign bit, and the remaining bits are inverted
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 negative number has a corresponding positive number. In a 64-bit system, the range of integer two’s complement representation is:

• Smallest negative number: 0x8000000000000000 (i.e., -2^63).
• Largest positive number: 0x7FFFFFFFFFFFFFFF (i.e., 2^63 - 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 value of two’s complement, otherwise return 0.
• The maximum value is 0x7FFFFFFF, which is characterized by the most significant bit being 0 and the rest being 1. After adding 0x1 to 0x7FFFFFFF, it becomes 0x80000000, where the most significant bit is 1 and the rest are 0, which is exactly the opposite characteristic.
• Here we need to use the property of XOR, such as x^target. When the inverted x is XORed with target, since XOR yields 1 for different bits and 0 for the same bits, x^target will be 0x0 only when x is exactly the same as target. Then, by adding the ! operator, we get !(x^target), which is 1 when x is the same as target, and 0 when they are different.
  For 0x7FFFFFFF, after adding 1 it becomes 0x80000000. Since the characteristics are exactly opposite, inverting it turns it back into 0x7FFFFFFF. Therefore, we can use XOR to determine if they are the same, i.e., !(~(x+1)^x).
• Continuing to think, is 0x7FFFFFFF the only number that satisfies this property: adding 1 is equivalent to bitwise inversion? Obviously, 0xFFFFFFFF also satisfies this property because the most significant bit is discarded upon overflow, becoming 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, expression1 is 0.
• The method of exclusion must utilize the characteristic that 0x7FFFFFFF has but 0xFFFFFFFF does not, which is the difference between these two numbers. The simplest difference is that 0x7FFFFFFF + 0x1 becomes 0x80000000, a non-zero 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 is needed, so adding another ! operation will suffice, i.e.:

!( ~(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 rest don’t matter), otherwise it returns 0.
• We can remove the influence of all even-positioned bits and look at the odd-positioned bits. For example, by ANDing x with 0xAAAAAAAA, all even-positioned bits become 0, and then we check if it is the same as 0xAAAAAAAA (using the method described in isTmax to determine if two numbers are the same via bitwise AND). Alternatively, we can OR x with 0x55555555, making all even-positioned bits 1, and then check if it is the same as 0xFFFFFFFF. That is:

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

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

• However, due to the constraints of the experimental requirements, we cannot directly write 0xAAAAAAAA; we can only write 0xAA and obtain 0xAAAAAAAA through bitwise operations.

Note: According to the C specification, the precedence of shift operations is lower than addition and subtraction.

https://en.cppreference.com/w/c/language/operator_precedence

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 that:

x+(-x)=0

x+(~x)=-1

• Subtracting the two equations yields:

-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;
}

• Check if x is an ASCII digit, which simply means determining if x is between 0x30 and 0x39.
• In assembly, determining the size is done by setting flags through subtraction. Therefore, we can subtract x from 0x30 and 0x39 respectively and take the sign bit to see if the conditions are met: 0x30-x should be less than 0 with a sign bit of 1, and 0x39-x > 0 with a sign bit of 0. However, if x falls on the boundary, such as x==0x30, 0x30-x is 0 with a sign bit of 0, which also meets the requirement. Therefore, we can change <= to <:

0x30<= x <= 0x39

The above expression is equivalent to:

0x2F< x <= 0x39

Then, does the right side x<0x39 need an equivalent transformation? 0x39-x should be greater than or equal to 0, with a sign bit of 0; 0x39-x<0 has a sign bit of 1. After analysis, the boundary conditions are included, so no equivalent transformation is needed (the transformation would exclude the boundary conditions).
To make the sign bit of 0x2F-x 1 and the sign bit of 0x39-x 0, both conditions must be met simultaneously. First, let’s look at 0x2F < x. How to extract the sign bit after subtraction? We can use an arithmetic right shift by 31 bits, so the sign bit fills the entire 32 bits. That is, if 0x2F-x<0, then (0x2F+(~x+1))>>31 is 0xFFFFFFFF; if 0x2F-x>=0, then (0x2F+(~x+1))>>31 is 0;

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

Next, look at x <= 0x39. Using the same method, if 0x39-x<0, then (0x39+(~x+1))>>31 is 0xFFFFFFFF; if 0x39-x>=0, then (0x39+(~x+1))>>31 is 0. We can take the negation to satisfy the condition.

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

Both of the above conditions need to be satisfied simultaneously, therefore

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

Since the final return value is either 1 or 0, we can 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 expression for conditional is the same as x ? y : z
• To implement this kind of logic that returns y or z based on the value of x, it is very difficult using only bitwise operations. This is because, although it is easy to determine if x is 0, it is hard to associate x with both y and z simultaneously. So we leave our hopes to addition operations, assuming 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 to satisfy the requirement. However, this requirement is equally difficult to meet because a is related to both y and z, and a is determined by whether x is 0. Therefore, we consider splitting a:

b+c+y+z

When x is non-zero, let b=0, c=-z=~z+1; when x is 0, let b=-y=~y+1, c=0. This way, b is only related to y, and c is only related to z.
First, we need to determine if x is 0. This is not difficult; we can use the ! operation. When x is non-zero, it is 0; when x is 0, it is 1. We first focus on b: when !x==0, b should be 0; when !x!=0, b should be ~z+1. Obviously, the AND operation can satisfy this:

b = !x&(~y+1)

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

a = ~(!x)+1

When x is 0, !x1, ~(!x)0xFFFFFFFE, a0xFFFFFFFF; when x is non-zero, !x0, ~(!x)0xFFFFFFFF, a0. Therefore, the expression for b should be

b = a&(~y+1)

Now focusing on c, the situation for c is exactly the opposite of b, so we just need to add a ~ to a.

c = ~a&(~z+1)

There is no need to worry about addition overflow here.

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 then return 1, otherwise return 0.
• Comparing sizes uses subtraction. Let y-x: if y-x>=0, meaning the sign bit is 0, return 1; if y-x<0, meaning the sign bit is 1, return 0. y-x=y+~x+1, then shift right by 31 bits and take the sign bit. We need a negation operation to satisfy returning 1 when the sign bit is 0, and returning 0 when the sign bit is 1:

~((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, i.e., for !x, return 1 when x is 0, and return 0 when x is non-zero.
• The most intuitive difference between 0 and non-zero is that every bit of 0 is 0, while non-zero has at least one bit that is 1. But because we cannot use circular shift operations to determine this, we have to find another way.
• Another difference between 0 and non-zero is that the negative of 0 is still 0, i.e., ~0+1=0, while the negative of a non-zero number is not 0. We can use this point to see if the negative of x is the same as itself. Previously, we used a technique to determine if two numbers are the same through XOR: this expression returns 0 when x equals 0, and returns non-zero when x equals non-zero, but this is equivalent to doing nothing.

(~x+1)^x

We can use another point: the sign bit of a non-zero number and its negative are definitely opposite; one must be 1 and the other must be 0. However, the sign bit of the negative of 0 and the sign bit of 0 are both 0. Therefore, we just need to AND the two to get: when non-zero, the sign bit of this expression is 1; when 0, the sign bit of this expression is 0.

(~x+1)|x

Next is extracting the sign bit, and incidentally negating it, because we require returning 1 when it is 0, and returning 0 when it is 1. We have used this technique in the above problem: shift it arithmetically right by 31 bits and negate it, then AND it with 0x1 to get the least significant 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 required to represent x in two’s complement form, which is essentially looking at which position the highest bit 1 of this number is in, and then adding 1 sign bit. This problem is a bit difficult, mainly because it is a bit hard to think of. Below is someone else’s implementation method.
• The binary search method is used here:
  Consider positive numbers and 0 first.

1. Upper 16 bits: Check if there is a 1 in the upper 16 bits. If so, at least 16 bits are needed.
2. Upper 8 bits: In the remaining 16 bits, check if there is a 1 in the upper 8 bits.
3. Upper 4 bits: In the remaining 8 bits, check if there is a 1 in the upper 4 bits.
4. Upper 2 bits: In the remaining 4 bits, check if there is a 1 in the upper 2 bits.
5. Upper 1 bit: In the remaining 2 bits, check if there is a 1 in the upper 1 bit.
6. Lowest bit: The final remaining 1 bit.
   Finally, add up the number of bits of all parts, and add 1 (sign bit).

• Handling of negative numbers:
  flag is x >> 31, which is 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 non-negative (flag == 0), then x remains unchanged.
   In the two’s complement representation of a negative number, the sign bit and the magnitude part are mixed together. If the number of significant bits of a negative number is calculated directly, the sign bit will cause an incorrect result. For example:
   The two’s complement of -1 is 11111111 11111111 11111111 11111111. If the number of bits is calculated directly, it will yield 32 bits, but in reality, we only care about its significant bits.
   Through the inversion operation, the two’s complement representation of a negative number is converted to a positive number, and the number of significant bits in its binary representation is the same as the original negative number. For example:

• The two’s complement of -1 is 11111111 11111111 11111111 11111111. After inversion, it becomes 00000000 00000000 00000000 00000000, and the number of significant bits is 1.
• The two’s complement of -2 is 11111111 11111111 11111111 11111110. After inversion, it becomes 00000000 00000000 00000000 00000001, and the number of significant bits is 2.

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, it is bitwise inverted.
  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 function’s input and output 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 this input. Also, finally can use if while 😭😭😭

• Let’s first reviewIEEE 754Knowledge of 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 operations.

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

Determine based on the exponent whether this floating-point number is a normalized number, a denormalized number, or which of the special cases

unsigned floatScale2(unsigned uf) { 
  unsigned exp = (uf&0x7f800000)>>23;
  unsigned sign=uf>>31&0x1;
  unsigned frac=uf&0x7FFFFF;
  if(exp == 0){//Denormalized number, exponent is 0, simply multiply frac by 2
    frac <<= 1;
    return (sign << 31) | (exp << 23) | frac;
  }else if(exp==0xFF){//Special case, NaN (Not a Number)
    return uf;
  }else{
    exp++;//Multiplying by 2 is equivalent to E+1, which is equivalent to
    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 using int. If it exceeds the representation range, return 0x80000000u.
• If it is a denormalized number, return 0 directly; if it is a special case, return 0x80000000u directly
• If it is a normalized number, we first need to determine if it exceeds the int representation range. int has 32 bits in total, with 1 bit for the sign bit, a maximum of 2^31, and a minimum of -(2^31+1). Therefore, the exponent E cannot exceed 30 (when E is 31, left-shifting 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 return 0 directly; also:
• sign 1 bit
• exp 8 bits
• frac 23 bits

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

We can consider it as1frac(the 24th bit is 1, and bits 1~23 form frac) and at this point it is equivalent to being formed by1.frac(the integer part is 1, the fractional part is frac) left-shifted by 23 bits. At this point, the exponent is E, meaning we need to multiply by E 2’s, which is left-shifting by E bits. Therefore, when E is less than 23, we should right-shift by (23-E) bits to truncate the (23-E) bits after frac; when E is greater than 23, since it is already left-shifted by 23 bits, we only need to left-shift by (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 case
    return 0x80000000u;
  } else if (exp == 0) {  // Denormalized number
    return 0x0;
  } else {                   // Normalized number
    int E = exp - 127;  // Exponent, be careful not to set it as unsigned
    if (E >= 31) {           // Out of range
      return 0x80000000u;
    }else if(E<0){//If E < 0, it means the number is less than 1, return 0
      return 0;
    }
    frac = frac | (1 << 23);  // Fill in the 1 of frac
    if (E < 23) {
      frac = frac >> (23 - E);
    } else {
      frac = frac << (E - 23);
    }
    if (sign == 0) {//Return positive or negative based on 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;
}

• Calculate 2.0^x and return the unsigned representation under IEEE 754. If the result is too small to be represented even as a denormalized number, return 0. If the result is too large, return +INF. Obviously, this question 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 number: the 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, the range of E is -126 <= E <= 127; and for frac, the minimum value is 0, the maximum value is 1 - 2^(-23), therefore, without considering 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 number: exponent is all 0s

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

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 minimum non-zero value that can be represented is 2^(-23); 0~2^(-23) cannot be represented, and the maximum value is 1 - 2^(-23). Therefore, when frac is 0, the value is 0, but to calculate the minimum non-zero value represented, frac must be set to 2^(-23), without considering 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: exp bits are all 1s, frac is 0, S is 0
2. -infinity: exp bits are all 1s, frac is 0, S is 1
3. NaN: exp bits are all 1s, frac is not 0

Therefore, based on the above analysis:

• When x > 127, return +NaN
• 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 be represented, 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). Assuming the input x is -127, then frac needs to be 2^(-1), which means shifting 1 to the left by 22 bits.
  } else {//x < -149, too small, return 0
    return 0;
  }
}