Datalab做題筆記

0x1 bitXor

隻用

和

表示

分析：（橫着的是a，豎着的是b）

XOR

1
1	1
1

令 ~A = a&~b

1
1
1

~B = ~a&b

1
1	1

則A&B有

1
1	1
1

再對A&B取~得到XOR

即XOR = ((a&(~b) ) & ((a) & b) )

0x2 tmin

輸出int的最小值

解析：補碼Tmin最高位為1，其他位為0。int有32bit,則Tmin = 1 <<31

0x3 istmax

*	 isTmax - returns 1 if x is the maximum,   
 *	 two's complement number,
 *   and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1

解析：Tmax除了最高位是0，剩下的31bit全為1

操作符可以用 ! 那麼想辦法把Tmax湊成0就可以了

則

(Tmax + 1) = (10000.....)
Tmax + Tmin = -1
~(-1) = 0
也就是當x = Tmax, ~ ((x + 1) + x) = 0
主要到對于0xffffffff也成立，特判即可

整理得到

ans = !((~((x + 1) + (x))) | (!(x + 1)))

0x4 allOddBits

Legal ops: ! ~ & ^ | + << >>

題意：判斷奇數比特是否是1

例如 (大端機器)A = 1010(從左向右) 奇數位全是1，題目要求最多12個操作符。是以不能一個個判斷。

假如我們已經有了Book = 0xAAAAAAAA
那麼y = x&Book,奇數位是1，偶數位全是0。
~Book + y 如果奇數位全是1，那麼此時32個比特上全是1。再取反，符合條件的全是0
得出ans = !(Book + x & Book)

0x5 negate

用位運算計算-x

解析： -x = ~x + 1

0x6 isAsciiDigit

判斷是否為ASCII數字

解析：在前一個小問，已經可以做出減法。隻要判斷是否在0和9之間即可。注意邊界處理

還有一個要注意的點就是，如果用第一個bit判斷正負，0的第一位和正數第一位都是0，需要先減去1，這樣就可以區分開了。

int isAsciiDigit(int x)
	{
  		int minusX = (~x) + 1;
  		int m = (minusX + 0x30 -1 ) >> 31; // -
  		int n = (0x39 + minusX ) >> 31;//+
  		return (m)&(!n);
	}

0x7 conditional

return x ? y : z

思路：如果x非0，那麼傳回y，否則傳回z。

先j = y ^ z, 再XOR得到結果

考慮cnt = !x - 1

x	真	假	操作
cnt	0xffffffff
y	1(需要XOR)
z	1

int conditional(int x, int y, int z)
	{
  		int cnt = !x - 1;
  		return (y ^ z) ^ (y & (~cnt)) ^ (z & (cnt));
	}

0x8 isLessOrEqual

判斷是否x小于等于y?

return x <=y

x <= y

y - x >=0

但是int加減可能造成溢出。

進行優化：

如果符号相同，那麼正數大于負數。

如果符号相反，那麼判斷內插補點。

int isLessOrEqual(int x,int y) 
{
    int signX = x >> 31, signY = y >> 31;
    int conditionOne = (signX & 1) & (!(signY | 0)); 
    int minusX = (~x) + 1;
    int conditionTwo = (y + minusX) >> 31;
    return conditionOne | ( (!((!(signX|0))&(signY&1)))&(!conditionOne) &(!conditionTwo));
}

貌似寫的很醜陋，符号用的太多了

0x9 logicalNeg

使用位運算計算x。

解析:也就是符号為全是0，傳回值為1。否則為0。注意到負數的首個bit一定為1，正數的相反數首個bit也是1(補碼原理)。那麼0呢？0再怎麼取相反數，首位都是0。嘻嘻

注意，就是int範圍并不是對稱的，-2147483648取反溢出等于-1

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

0xA howManyBits

題意：判斷一個數字至少用多少bit的補碼。

分析：比如-5，因為$-5 = -2^3 + 2 + 1$可以用補碼$(2)1011$一共四位表示。而$9 = 2 ^ 3 + 1$不難發現規律是向下取幂。對于正數，是找最高位的1，對于負數，是找最高位的10再上一位。取反就是01再上一位。

x = x(負數) ? (-x) : x

前面寫過三目運算符了。

x = (~x&(x >> 31) ) | (x&(~(x>>31)))

這樣x如果是負數就被取反了。現在我們需要找到最高位的1在哪個地方。

x = x | (x >>2);
  x = x | (x >>4);
  x = x | (x >>8);
  x = x | (x >>16);

因為這樣最高位的1一定能夠填充右邊的所有bit，是以再統計有多少個1。最後cnt+1就行辣。

這道題最多可以用90個操作符，我們當然可以一個個bit統計，但是這樣太豬鼻了。

讓我們想想，如果前16位有至少一個1，那麼至少有16個1;

if（前16位有1）
		f(統計前16位1的個數)
	else
		f（統計後16位1的個數）

!!(x>>16 & (-1))

如果結果是1，則前16位為1。

x = x >> (16 & -flag)

表示右移選擇

舉個例子，當最後還剩2位時，隻有11，10，00這三種情況。

前兩種右移1位，得到1，後一種不用右移，還是0。是以最後還要加右移完的x。

int howManyBits(int x)
{
  x = (~x&(x >> 31) ) | (x&(~(x>>31)));
  int cnt16,cnt8,cnt4,cnt2,cnt1;
  cnt16 = (!!((x>>16)&(-1))) << 4;
  x = x >> cnt16;//remain 16bit
  cnt8 = (!!((x>>8)&(-1))) << 3;
  x = x >> cnt8;
  cnt4 = (!!((x>>4)&(-1))) << 2;
  x = x >> cnt4;//remain 4bit
  cnt2 = (!!((x>>2)&(-1))) << 1;
  x = x >> cnt2;//remain2bit
  cnt1 = (!!((x>>1)&(-1)));
  x = x >> cnt1;
  x = cnt16+cnt8+cnt4+cnt2+cnt1 + x + 1;
  return x;
}

0xB floatScale2

輸出一個小數的2倍，這個小數以unsigned int的bit來表示

unsigned floatScale2(unsigned uf)
{
  unsigned sign = uf >> 31;
  unsigned exp  = (uf >> 23 )& 0xff;
  unsigned f = uf & 0x007fffff;
  if(exp  == (1 << 8) -1 ) 
  {
    return uf;
  }
  if(!exp) 
  {
    return (sign<<31 )|(exp<<23)|(f<<1);
  }
  else 
    return (sign<<31 )|((exp+1)<<23)|(f);

  return 2;
}

0xC floatFloat2Int

0xD floatPower2

題意：參數x, 傳回2.0^x

分析：

非規格化，exp為0，偏碼後為-126,frac為$2(-23)*1$,最小為$2(-149)$,是以當$x<-149$， return 0
當frac為2(-1)*，乘以*2(-126),是以非規格化最多表示$2^(-127)$ 當$-149<=x<=-127$ ,比如x = -139 的時候，前面已經乘以2(-126)*，後面再乘以*2(-13)就好了，也就是$frac = 2^(x + 126)$第$x + 126 + 24$位（從右向左）是1， return 1<<(x + 126 + 24 -1) 也即 return 1<<(x + 149)
考慮規格化數字 $1<=exp<=254$,此時減去偏碼127，得到$2^(-126~127)$,是以當$-126<=x<=127$ 傳回 $(127 + x) << 23$
考慮特殊值，當x >= 255,exp需要全為1，傳回inf就可以了

總結

終于把datalab做完了，頭疼。

Datalab做題筆記Datalab做題筆記