I Data Lab

萬事開頭難，尤其是和 0 與 1 打交道，和后面的實驗相比，這次只能算個熱身。但是喜歡運動的都知道，熱身很重要！

任務目標

我們先來看看 Datalab 需要我們做什么。主要是通過這次的作業來熟悉整型及浮點數的位表達形式，簡單來說，就是解開一些人工謎題。列表如下：

比特操作謎題整數運算謎題：

浮點數運算謎題：

上手指南

一共 13 個需要補充的函數，所有的工作都只需修改?bits.c?文件，測試的話有三種方式：btest,?dlc, 和?BDD checker。

一些小技巧：

在函數開始時聲明所有變量
}?應該在第一列
注意運算符號的優先級，使用括號確保順序的正確
關注 !, 0, TMin 等

任務指引還是比較清晰的，主要有以下一些說明：

整型的范圍是 0 到 255(0xFF)，不允許用更大
只能包含參數和局部變量
一元操作符?!?~
二元操作符?&?|?+?<<?>>

不允許的操作有：

使用任何條件控制語句
定義和使用宏
定義其他的函數
調用函數
使用其他的操作符
使用類型轉換
使用除 int 之外的類型（針對整型）
使用除 int, unsigned 之外的類型（針對浮點數）

可以認為機器：

使用 2’s complent，32位
執行算術右移
移動超過字長的位數會出問題

其他需要注意的事情有：

使用 dlc(data lab checker) 來檢測代碼的合法性（有沒有使用不給使用的符號語法等等）
每個函數都有操作數的上限值，注意?=?不算
使用 btest 來測試結果的正確與否
使用 BDD checker 來正規測試你的函數

題目及解法

thirdBits

題目要求：return word with every third bit (starting from the LSB) set to 1
允許操作：! ~ & ^ | + << >>
操作數限制：8
分值：1

我們返回的結果是：0100 1001 0010 0100 1001 0010 0100 1001，因為題目要求每個變量不可以超過 255，也就是最多?1111 1111，所以只能分步驟來進行組合，如下面代碼所示

Desired output: 0100 1001 0010 0100 1001 0010 0100 1001 
Step 1:         0000 0000 0000 0000 0000 0000 0100 1001  0x49
Step 2:         0000 0000 0000 0000 1001 0010 0000 0000  Shift << 9
Step 3:         0000 0000 0000 0000 1001 0010 0100 1001  Add 0x49
Step 4:         0100 1001 0010 0100 0000 0000 0000 0000  Shift << 18
Step 5:         0100 1001 0010 0100 1001 0010 0100 1001  Add result from step 3int thirdBits(void) {int a = 0x49;int b = (a << 9);int c = b + a;return (c << 18) + c; // Steps 4 and 5
}

可以看到第一個函數已經寫對的得到了一分，然后我們再來檢測一下有沒有用非法的操作符：./dlc -e bits.c

可以看到沒有顯示錯誤信息，-e?會輸出操作符的數量，這里也都沒有問題。接下來的題目都會用這種方式測試，但是就不會再貼圖了。

isTmin

題目要求：returns 1 if x is the minimum, two’s complement number, and 0 otherwise
允許操作：! ~ & ^ | +
操作數限制：10
分值：1

根據 2’s complement 的定義，Tmin 的值是?10000000 00000000 00000000 00000000，我們要怎么判斷一個數是不是 Tmin 呢，原則上來說，只需要把 x 和 Tmin 做?&?操作，判斷即可，但是題目要求不能左移，于是就要想其他的辦法了，觀察 Tmin 的值，發現如果左移一次，就變成全部為 0，但是全部為零的情況還有另外一種就是本身全部就是 0，所以只要排除第二種情況，就可以判斷是否是 Tmin 了，代碼如下：

// 前面一部分用于判斷左移一位后是否全部為0，后面一部分用來判斷 x 值是否為 0
int isTmin(int x) {return !(x+x)&!!(x);
}

isNotEqual

題目要求：return 0 if x == y, and 1 otherwise
- 例如: isNotEqual(5,5) = 0, isNotEqual(4,5) = 1
允許操作：! ~ & ^ | + << >>
操作數限制：6
分值：2

這題比較簡單，發現可以使用異或操作，那么只需要判斷兩個數異或后結果是否為 0 即可，這里同樣使用了 !! 來把 bit 轉換成 boolean 值

int isNotEqual(int x, int y)
{return(!!(x ^ y));
}

anyOddBit

題目要求：return 1 if any odd-numbered bit in word set to 1
- 例如： anyOddBit(0x5) = 0, anyOddBit(0x7) = 1
允許操作：! ~ & ^ | + << >>
操作數限制：12
分值：2

我們依舊不能超過 0xFF 的限制，所以需要把前面的 24 位都用?|?和?>>?運算符移動到最后八位中，再和?10101010?來做?&?操作，只要不為零，就說明在偶數位上有不為 0 位

int anyOddBit(int x) {return !!((x | (x >> 8) | (x >> 16) | (x >> 24)) & 0xaa);
}

negate

題目要求：return -x
- 例如：negate(1) = -1.
允許操作：! ~ & ^ | + << >>
操作數限制：5
分值：2

第一感覺就是用到取反?~?符號，但需要考慮三種情況：正，零，負

假設是?0010(2)，取反之后是?1101(-3)
假設是?1110(-2)，取反之后是?0001(1)
假設是?0000(0)，取反之后是?1111(-1)

可以發現一個規律，就是都差 1，為什么呢，就是因為 2’s complement 的定義中是加上了 1 的，所以只要再加一就好。

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

conditional

題目要求：same as x ? y : z
- 例如：conditional(2,4,5) = 4
允許操作：! ~ & ^ | + << >>
操作數限制：16
分值：3

這一題稍微有一些復雜，我們來看看怎么去想。因為不能用 if 來做流程判斷，所以我們返回的表達式例一定要包含 y 和 z，但是可以根據 x 的值來進行變換，所以大概的式子是?(y op expr) | (z op expr)(op 表示操作符， expr 是某個表達式)。

然后就簡單很多了，我們只要想辦法做一個 expr，要么為?0x00000000，要么為?0xffffffff?即可，于是表達式?~!x + 1?就可以滿足我們的需求，x 為 0 時，表達式為?0xffffffff，不等于 0 時也滿足條件，就等于有了答案

int conditional(int x, int y, int z) {/**if x!=0,mask=0x00000000,so y&~mask==y and z&mask==0*if x==0,mask=0xffffffff,so y&~mask = y&0 =0; z&mask=z*/int mask= ~!x+1; return (y & ~mask)|(z & mask);
}

subOK

題目要求：Determine if can compute x-y without overflow
- 例如：
- subOK(0x80000000,0x80000000) = 1
- subOK(0x80000000,0x70000000) = 0
允許操作：! ~ & ^ | + << >>
操作數限制：20
分值：3

這題也不算輕松，但是我們可以一步一步來搞定，首先，既然是計算 x-y，我們要能夠知道結果，由于不給使用減號，那就用倒數（之前的方法），所以 x-y 的結果為?~y+1+x。然后需要怎么判斷呢，觀察發現，只有在以下這兩種情況同時發生的時候，才是 overflow

x 和 y 符號不同
x-y 的符號和 x 不同

可能有點難以理解，overflow 指的是除符號位的最高位進位，也就是說符號會變化，所以需要 x 和 y 的符號不同（這樣 x-y 就等同于兩個同符號的加法），也就是第一個條件；符號到底有沒有變化呢，就要看 x-y 與 x 的符號是否相同，也就是第二個條件。所以代碼如下：

int subOK(int x, int y) {/** overflow of sub happens iff * 1) x and y have different signs* 2) res = x - y has different sign with x*/int res = x + (~y + 1);int sameSign = x ^ y;int resSign = res ^ x;return !((sameSign & resSign) >> 31);
}

isGreater

題目要求：if x > y then return 1, else return 0
- 例如：isGreater(4,5) = 0, isGreater(5,4) = 1
允許操作：! ~ & ^ | + << >>
操作數限制：24
分值：3

因為要考慮正負號，所以這個問題變成：

兩個數符號相同的情況
兩個數符號不同的情況

具體可以參見代碼

int isGreater(int x, int y)
{// Boolean value indicating sign of x// 1 = Negative// 0 = Non-Negativeint sign_x = x >> 31;// Boolean value indicating sign of y// 1 = Negative// 0 = Non-Negativeint sign_y = y >> 31;// if the signs are equal, then// if x is larger, sign bit of (~y + x) is 0// if y is larger or equal to x, sign bit of (~y + x) is 1// 感謝網友 劉鎮寬 & AlohaJack 的提醒int equal = !(sign_x ^ sign_y) & ((~y + x) >> 31);// if signs are not equal, these principles are reversed.int notEqual = sign_x & !sign_y;// this | returns 0 when it is x is greater, so you have to negate it.return !( equal | notEqual);
}

bitParity

題目要求：returns 1 if x contains an odd number of 0’s
- 例如：bitParity(5) = 0, bitParity(7) = 1
允許操作：! ~ & ^ | + << >>
操作數限制：20
分值：4

這道題要我們統計有有多少個零，這里我們需要利用一個特點，就是堆兩個數進行異或操作，不改變奇偶性，所以只需要一步一步來異或就可以了

int bitParity(int x) {/* XORing two numbers returns a number with same bit parity.Keep shifting half of our number until reduced to 1 bit simple case.*/x = ( x >> 16 ) ^ x;x = ( x >> 8 ) ^ x;x = ( x >> 4 ) ^ x;x = ( x >> 2 ) ^ x;x = ( x >> 1) ^ x;return (x & 1);
}

howManyBits

題目要求：return the minimum number of bits required to represent x in two’s complement
- 例如：
- howManyBits(12) = 5
- howManyBits(298) = 10
- howManyBits(-5) = 4
- howManyBits(0) = 1
- howManyBits(-1) = 1
- howManyBits(0x80000000) = 32
允許操作：! ~ & ^ | + << >>
操作數限制：90
分值：4

這題從操作數限制的數目來看就知道比較復雜，但是代碼還是比較清晰的，可以直接查看代碼中的注釋

int howManyBits(int x) {int temp=x^(x>>31);//get positive of x;int isZero=!temp;//notZeroMask is 0xffffffffint notZeroMask=(!(!temp)<<31)>>31;int bit_16,bit_8,bit_4,bit_2,bit_1;bit_16=!(!(temp>>16))<<4;//see if the high 16bits have value,if have,then we need at least 16 bits//if the highest 16 bits have value,then rightshift 16 to see the exact place of  //if not means they are all zero,right shift nothing and we should only consider the low 16 bitstemp=temp>>bit_16;bit_8=!(!(temp>>8))<<3;temp=temp>>bit_8;bit_4=!(!(temp>>4))<<2;temp=temp>>bit_4;bit_2=!(!(temp>>2))<<1;temp=temp>>bit_2;bit_1=!(!(temp>>1));temp=bit_16+bit_8+bit_4+bit_2+bit_1+2;//at least we need one bit for 1 to tmax,//and we need another bit for signreturn isZero|(temp&notZeroMask);
}

float_half

題目要求：Return bit-level equivalent of expression (float) x. Result is returned as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point values.
允許操作：Any integer/unsigned operations incl. ||, &&. also if, while
操作數限制：30
分值：4

這個就是考察基本的對于 IEEE 浮點數格式的轉換了，思路也比較清晰，就是根據不同的部分來求出對應的值

unsigned float_half(unsigned uf) {int round, S, E, maskE, maskM, maskS,maskEM, maskSM, tmp;round = !((uf&3)^3);maskS = 0x80000000;maskE = 0x7F800000;maskM = 0x007FFFFF;maskEM= 0x7FFFFFFF;maskSM= 0x807FFFFF;E = uf&maskE;S = uf&maskS;//Nan or Infinityif (E==0x7F800000) return uf;//E=1 - specialcaseif (E==0x00800000){return S | (round + ((uf & maskEM)>>1)) ;}//E=0 - denormalizedif (E==0x00000000) {tmp = (uf&maskM)>>1;return S | (tmp + round);}//normalized casereturn (((E>>23)-1)<<23) | (uf & maskSM);
}

float_i2f

題目要求：Return bit-level equivalent of expression (float) x. Result is returned as unsigned int, but it is to be interpreted as the bit-level representation of a single-precision floating point values.
允許操作：Any integer/unsigned operations incl. ||, &&. also if, while
操作數限制：30
分值：4

和上題一樣，這個就是考察基本的對于 IEEE 浮點數格式的轉換了，思路也比較清晰，就是根據不同的部分來求出對應的值

unsigned float_i2f(int x) {/*int exponent=0;return ((sign<<31)|(exponent<<23)|fraction)+flag;*/int sign=x>>31&1;int i;int exponent; int fraction; int delta;int fraction_mask;if(x==0)//||x==0x8000000)return x;else if(x==0x80000000)exponent=158;else{if (sign)//turn negtive to positivex = -x;i = 30;while ( !(x >> i) )//see how many bits do x have(rightshift until 0) i--;//printf("%x %d\n",x,i);exponent = i + 127;x = x << (31 - i);//clean all those zeroes of high bitsfraction_mask = 0x7fffff;//(1 << 23) - 1;fraction = fraction_mask & (x >> 8);//right shift 8 bits to become the fraction,sign and exp have 8 bits totalx = x & 0xff;delta = x > 128 || ((x == 128) && (fraction & 1));//if lowest 8 bits of x is larger than a half,or is 1.5,round up 1fraction += delta;if(fraction >> 23) {//if after rounding fraction is larger than 23bitsfraction &= fraction_mask;exponent += 1;}}return (sign<<31)|(exponent<<23)|fraction;
}

float_f2i

題目要求：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.
允許操作：Any integer/unsigned operations incl. ||, &&. also if, while
操作數限制：30
分值：4

和上題一樣，這個就是考察基本的對于 IEEE 浮點數格式的轉換了，思路也比較清晰，就是根據不同的部分來求出對應的值

int float_f2i(unsigned uf) {int exp = (uf >> 23) & 0xFF;int frac = uf & 0x007FFFFF;int sign = uf & 0x80000000;int bias = exp - 127;if (exp == 255 || bias > 30) {// exponent is 255 (NaN), or number is too large for an intreturn 0x80000000u;} else if (!exp || bias < 0) {// number is very small, round down to 0return 0;}// append a 1 to the front to normalizefrac = frac | 1 << 23;// float based on the biasif (bias > 23) {frac = frac << (bias - 23);} else {frac = frac >> (23 - bias);}if (sign) {// original number was negative, make the new number negativefrac = ~(frac) + 1;}return frac;
}