This series of articles is mainly used to record my process and thoughts on completing the experiments of CS.
- Experiment Name: DataLab
- Start Date: 24/10/2023
- Keywords: Simple Logic, Two's Complement, Floating Point
- Experiment Content: Implement data processing as required using only a limited set of bitwise operators, with a total of 13 subproblems of varying scores and increasing difficulty.
01 bitXor#
//1
/*
* bitXor - x^y using only ~ and &
* Example: bitXor(4, 5) = 1
* Legal ops: ~ &
* Max ops: 14
* Rating: 1
*/
Requirement: Use only ~ and & operators to implement XOR.
Analysis: The logical expression for XOR is $F = \bar x \cdot y + x \cdot \bar y$. It can be transformed using De Morgan's theorem to a case that only uses ~ and &, but let's see what happens if we consider XOR as the negation of XNOR and then apply De Morgan's theorem:
We find that this saves one operator!
Solution:
int bitXor(int x, int y) {
return ~(x & y) & ~(~x & ~y);
}
02 tmin#
/*
* tmin - return minimum two's complement integer
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 4
* Rating: 1
*/
```
Requirement: Return the smallest two's complement representation.
Analysis: The two's complement expression is $$B2T_w(\vec x)=-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i$$
The minimum value is $-2^{w-1}$ when the sign bit is 1 and the rest are 0.
Solution:
```c
int tmin(void) {
return 0x1 << 31; // Shift 1 left by 31 bits to the sign bit
}
03 isTmax#
/*
* isTmax - returns 1 if x is the maximum, two's complement number,
* and 0 otherwise
* Legal ops: ! ~ & ^ | +
* Max ops: 10
* Rating: 1
*/
Requirement: Determine if the input x is the maximum two's complement representation.
Analysis: From the previous question, we know that the maximum two's complement number is 0x7FFFFFFF, which has all bits set to 1 except the first bit. We can find a way to turn x into all zeros and then use logical NOT (!) to check.
int i = x + 1; // 0111...111 -> 1000...000 (i)
x += i; // 0111...111 -> 1111...111 (x)
x = ~x; // 1111...111 -> 0000...000 (x)
However, we must consider that if x is -1 (0xFFFFFFFF), we can also get a result of all zeros. In this case, i would be all zeros. To eliminate this loophole, we can add a NOT to i.
i = !i; // x = Tmax -> !i = 0; x = -1 -> !i = 1
x += i;
Solution:
int isTmax(int x) {
int i = x + 1;
x += i;
x = ~x;
i = !i;
x += i;
return !x;
}
04 allOddBits#
/*
* 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
*/
Requirement: Determine if all odd bits are 1 (the least significant is bit 0).
Analysis: This is not difficult; we just need to set all even bits to 0 and then check if all odd bits are 1 and all even bits are 0 (1010...1010).
Solution:
int allOddBits(int x) {
int mask = (0xAA << 8) | 0xAA;
mask = (mask << 16) | mask; // Generate 1010...1010
return !((x & mask) ^ mask); // Use XOR to check for equality
}
05 negate#
/*
* negate - return -x
* Example: negate(1) = -1.
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 5
* Rating: 2
*/
Requirement: Return the opposite number.
Analysis: According to the definition of two's complement, we have $x + ~x = -1$, thus $-x = ~x + 1$.
Solution:
int negate(int x) {
return ~x + 1;
}
06 isAsciiDigit#
/*
* 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
*/
Requirement: Determine if it is an ASCII digit, i.e., $0x30 \leq x \leq 0x39$.
Analysis: I got stuck here for a long time and finally referred to a solution online, which is quite clever. Set two numbers LowerBound (negative) and UpperBound (positive).
- If $x \geq 0x30$, adding x to
LowerBoundcan change it from negative to positive; otherwise, it remains negative. - If $x \leq 0x39$, adding it to
UpperBoundwill turn it negative (overflow); otherwise, it will become negative.
We just need to check if both final numbers are positive.
Solution:
int isAsciiDigit(int x) {
int sign = 0x1 << 31;
int LowerBound = ~0x30;
int UpperBound = ~(sign | 0x39); // Think about why?
LowerBound = sign & (LowerBound + x + 1); // Adding 0x30 still negative, so add one
UpperBound = sign & (UpperBound + x);
return !(LowerBound | UpperBound);
}
07 conditional#
/*
* conditional - same as x ? y : z
* Example: conditional(2,4,5) = 4
* Legal ops: ! ~ & ^ | + << >>
* Max ops: 16
* Rating: 3
*/
Requirement: Implement the C language ternary operator x ? y : z.
Analysis: First, convert x to 0 or 1 using logical NOT twice. If x is 1, output y; otherwise, output z. This can be expressed as a logical expression.
Solution:
int conditional(int x, int y, int z) {
x = !!x;
x = ~x + 1;
return (x & y) | (~x & z);
}
08 isLessOrEqual#
/*
* isLessOrEqual - if x <= y then return 1, else return 0
* Example: isLessOrEqual(4,5) = 1.
* Legal ops: ! ~ & ^ | + << >> cannot use subtraction!
* Max ops: 24
* Rating: 3
*/
Requirement: Determine if x is less than or equal to y.
Analysis:
- If x and y have different signs, then x is definitely less than or equal to y when x is negative.
- If x and y have the same sign, then if $y - x$ is greater than 0, x is less than or equal to y.
Why can't we directly check $y - x$? We need to consider two cases because when y is greater than zero and x is less than zero, adding two positive numbers may overflow to a negative number.
Solution:
int isLessOrEqual(int x, int y) {
int negX = ~x + 1; // -x
int YminusX = negX + y; // y - x
int Sign = YminusX >> 31 & 1; // Sign of y - x
// Don't forget to &1 because right-shifting preserves the sign bit!
int Xsign = x >> 31 & 1; // x sign bit
int Ysign = y >> 31 & 1; // y sign bit
int bitXor = Xsign ^ Ysign; // Whether x and y have the same sign
return ((!bitXor) & (!Sign)) | ((bitXor) & (x >> 31));
}
09 LogicalNeg#
/*
* 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
*/
Requirement: Implement logical NOT (!).
Analysis: Directly using ~~!x (not) is not possible. After using so many logical NOTs, how can we implement it? I thought for a long time and couldn't figure it out, so I referred to a solution online. It can be observed that only 0 and Tmin's two's complement (negation plus one) are equal to themselves; all other numbers' two's complement are opposites. Thus, taking the sign bits of these two numbers and performing OR gives 1. Tmin also meets this condition, so we don't need to check separately.
Solution:
int logicalNeg(int x) {
return ((x | (~x + 1)) >> 31) + 1;
// This way, the program only checks the last bit of the output number's binary representation.
}
10 howManyBits#
/* 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
*/
Requirement: Calculate the minimum number of bits required to represent x in two's complement.
Analysis: I can think of taking the negation of negative numbers and finding the highest bit that is 1. After looking at the reference answer, I found this solution to be quite clever! First, check if there is a 1 in the highest 16 bits. If there is, at least 16 bits are needed because we need to keep the lower 16 bits. Then check the upper 8 bits, upper 4 bits, etc. (since Max ops is 90, a few more steps are fine).
Solution:
int howManyBits(int x) {
int b16, b8, b4, b2, b1, b0;
int sign = x >> 31;
x = (sign & ~x) | (~sign & x); // If negative, negate for easier finding of 1
// Continuously check for 1
b16 = !!(x >> 16) << 4; // If there is a 1 in the upper 16 bits, set b16 = 16
x = x >> b16; // If so, right shift the original number by 16 bits to check the upper 8 bits
b8 = !!(x >> 8) << 3; // And so on
x = x >> b8;
b4 = !!(x >> 4) << 2;
x = x >> b4;
b2 = !!(x >> 2) << 1;
x = x >> b2;
b1 = !!(x >> 1);
x = x >> b1;
b0 = x;
return b16 + b8 + b4 + b2 + b1 + b0 + 1; // +1 for the sign bit
}
11 floatScale2#
/*
* 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
*/
Requirement: Multiply a single-precision floating point number by 2.
Analysis: If it is denormalized, left shift by one while keeping the sign bit (using denormalization can smoothly transition to normalization); if NaN or infinity, output itself; if multiplying by 2 overflows, return infinity; otherwise, it is normalized and does not overflow, output the exponent incremented by 1.
Solution:
unsigned floatScale2(unsigned uf) {
int exp = (uf >> 23) & 0xff; // Get the exponent
int sign = uf & (1 << 31); // Get the sign
if (exp == 0) return uf << 1 | sign; // Denormalized
if (exp == 255) return uf; // NaN or infinity
exp++; // Increment exponent by one, which is equivalent to multiplying by 2
if (exp == 255) return 0xff << 23 | sign; // Overflow
return (exp << 23) | (uf & ~(0xff << 23)); // No overflow
}
12 floatFloat2Int#
/*
* 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
*/
Requirement: Convert a single-precision floating point number to int type.
Analysis: We need to write a type conversion! As long as we clarify the situation, it is actually not a problem. After careful consideration, we find that only normalized numbers with an exponent greater than or equal to 0 and less than or equal to 31 are meaningful. NaN and positive infinity are naturally not valid, denormalized numbers that are very small will convert to 0, and normalized numbers with an exponent less than 0 will be less than 1, outputting 0. Normalized numbers with an exponent greater than 31 will overflow when converted to int type because the size of the exponent is the number of left shifts, and int type only has 32 bits. Finally, we determine whether it overflows based on the sign.
Solution:
int floatFloat2Int(unsigned uf) {
int exp = ((uf & 0x7f800000) >> 23) - 127;
int frac = (uf & 0x007fffff) | (0x1 << 23); // Add 1 to the 24th bit, i.e., M = f + 1
int sign = uf >> 31;
if (exp > 31) return 0x80000000;
if (exp < 0) return 0; // Denormalized using this algorithm, exponent is -127, which meets this condition
if (exp > 23) frac <<= (exp - 23);
else frac >>= (23 - exp); // The fraction is already equivalent to being left-shifted by 23 bits
if (!((frac >> 31) ^ sign)) return frac; // If the sign hasn't changed, output directly
else if (!sign) return 0x80000000; // If it changes from positive to negative, it indicates overflow (but the test cases seem not to consider Tmin)
else return ~frac + 1; // If it changes from negative to positive, output the opposite number
}
13 floatPower2#
/*
* 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
*/
Requirement: Calculate 2^x in floating-point representation.
Analysis: Classify the discussion:
- If $x \leq -150$, it is too small to be represented as a denormalized value, output 0.
- If $-149 \leq x \leq -127$, it can be represented as a denormalized value.
- If $-126 \leq x \leq 127$, it can be represented as a normalized value.
- If $x \geq 128$, it is NaN or infinity, output INF.
Solution:
unsigned floatPower2(int x) {
int INF = 0xff << 23;
int exp = x + 127; // Add 127 for easier calculation
if (exp <= 23) return (exp << 23) | (1 << (23 - exp - 1));
if (exp <= 0) return 0;
if (exp >= 255) return INF;
return exp << 23;
}
Summary:#
Why is the first lab so difficult? Many clever operations I simply couldn't think of, requiring certain techniques. It is recommended to think for yourself first when doing it; if you really can't figure it out, you might as well look for answers online, as this can help us better understand the content about two's complement and floating-point numbers in the book. Also, it can be helpful to record your thought process for future review; I believe doing such experiments once is not enough.
Live in the moment!