计算机组成原理

《深入理解计算机系统/CSAPP》 Data Lab

2019-02-21  本文已影响1人  Coc0

原文地址(格式较好)

目标

填写bits.c源文件中的代码，并且满足题目要求(操作符的限制情况)
PS:若有错误和更好解法请告知

文件说明:

题目说明:

ID 名称 描述 难度 操作数目
1 absVal(int x) 计算x的绝对值 4 8
2 addOK(int x,int y) 判断x+y是否溢出 3 20
3 allEvenBits(int x) 判断二进制数偶数位是否全为1 2 12
4 allOddBits(int x) 判断二进制数奇数位是否全为1 2 12
5 anyEvenBits(int x) 判断二进制数任意偶数位是否为1 2 12
6 anyOddBits(int x) 判断二进制数任意奇数位是否为1 2 12
7 bang(int x) 不使用!计算!x 4 12
8 bitAnd(int x,int y) 使用~和<code>|</code>计算& 1 8
9 bitCount(int x) 计算二进制数1的个数 4 40
10 bitMask(int hightbit,int lowbit) 产生一个[l，h]区间内全为1的数 3 16
11 bitMatch(int x,int y) 生成掩码，表示x和y中哪些位相等 1 14
12 bitNor(int x,int y) 使用~和&实现<code>~(x|y)</code> 1 8
13 bitOr(int x,int y) 使用~和&实现<code>x|y</code> 1 8
14 bitParity(int x) 判断x是否有奇数个0 4 8
15 bitReverse(int x) 逆序32位比特数 4 45
16 bitXor(int x,int y) 使用~和&实现x^y 1 14
17 bitSwap(int x,int n,int m) 交换第n和第m字节 2 25
18 conditional(int x,int y,int z) 实现x?y:z 3 16
19 copyLSB(int x) 将二进制数所有位的数置为最低位数 2 5
20 distinctNegation(int x) 判断x != -x 2 5
21 dividePower2(int x,int n) 计算x/(2^n) 2 15
22 evenBits(void) 返回二进制数偶数位为1的数 1 8
23 ezThreeFourths(int x) 计算x*3/4 3 12
24 fitsBits(int x,int n) 判断x是否能用n位补码表示 2 15
25 fitsShort(int x) 判断x是否能用16位补码表示 1 8
26 floatAbsVal(unsigned uf) 返回浮点数f的绝对值 2 10
27 floatFloat2Int(unsigned uf) 浮点数转化为带符号整数 4 30
28 floatInt2Float(int x) 带符号整数转化为浮点数 4 30
29 floatIsEqual(unsigned uf,unsigned ug) 判断浮点数f==g 2 25
30 floatIsLess(unsigned uf,unsigned ug) 判断浮点数f<g 3 30
31 floatNegate(unsigned uf) 计算浮点数-f 2 10
32 floatPower2(int x) 计算浮点数2.0^x 4 30
33 floatScale1d2(unsigned uf) 计算浮点数0.5*f 4 30
34 floatScale2(unsigned uf) 计算浮点数2*f 4 30
35 floatScale64(unsigned uf) 计算浮点数64*f 4 35
36 floatUnsigned2Float(unsigned u) 无符号整数转化为浮点数 4 30
37 getByte(int x,int n) 获取x的第n字节 2 6
38 greatestBitPos(int x) 生成掩码，只保留二进制数x中为1的最高比特位 4 70
39 howManyBits(int x) 判断x需要多少位补码 4 90
40 implication(int x,int y) 判断命题逻辑x->y，即x蕴含y 2 5
41 intLog2(int x) 计算floor(log2(x)) 4 90
42 isAsciiDigit(int x) 判断x是否可以是表示数字的Ascii码 3 15
43 isEqual(int x,int y) 判断x==y 2 5
44 isGreater(int x,int y) 判断x>y 3 24
45 isLess(int x,int y) 判断x<y 3 24
46 isLessOrEqual(int x,int y) 判断x<=y 3 24
47 isNegative(int x) 判断x<0 2 6
48 isNonNegative(int x) 判断x>=0 2 6
49 isNonZero(int x) 不使用!判断x==0 4 10
50 isNotEqual(int x,int y) 判断x!=y 2 6
51 isPallindrome(int x) 判断二进制数x，比特串是否为镜像 4 45
52 isPositive(int x) 判断x>0 2 8
53 isPower2(int x) 判断x==(2^n) 4 20
54 isTmax(int x) 判断x==Tmax 1 10
55 isTmin(int x) 判断x==Tmin 1 10
56 isZero(int x) 判断x==0 1 2
57 leastBitPos(int x) 生成掩码，只保留二进制数x中为1的最低比特位 2 6
58 leftBitCount(int x) 返回二进制数从高位到低位，连续为1的个数 4 50
59 logicalNeg(int x) 不使用!计算!x 4 12
60 logicalShift(int x,int n) 计算x逻辑右移n位 3 20
61 minusOne(void) 返回-1 1 2
62 multFiveEighths(int x) 计算x*5/8 3 12
63 negate(int x) 计算-x 2 5
64 oddBits(void) 返回奇数位上为1的二进制数 2 8
65 remainderPower2(int x,int n) 计算x%(2^n) 3 20
66 replaceByte(int x,int n,int c) 用字节数c来代替n中的第x字节数 3 10
67 rotateLeft(int x,int n) 循环左移n位 3 25
68 rotateRight(int x,int n) 循环右移n位 3 25

谜题1 - absVal

|x| = \begin{cases} -x（\thicksim x+1）,& x<0 \\ x, & x\geqslant0 \\ \end{cases}
对x处理可以分为两种情况，取反+1，不变+0。
众所周知，一个数取反可以异或1，不变可以异或0。
当x<0时，x>>31为0xFFFFFFFF，x^(x>>31)即取反，(x>>31)&1为0x1。

int absVal(int x) {
  return (x^(x>>31))+((x>>31)&1);
}

谜题2 - addOK

众所周知，正数与负数之和不会溢出。
符号相同两数之和，判断结果最高位位与任一数做高位是否相同即可。

int addOK(int x, int y) {
  return (((x^y)>>31)|~(((x+y)^x)>>31))&1;
}

谜题3 - allEvenBits

若一个二进制数偶数位为1，奇数位为0，则这个数为0x55555555。
先将x=x&0x55555555，将这个数奇数为变为0，之后x^0x55555555判断该数是否为0x55555555。
构造mask=0x55555555，mask = 0x55 | 0x55 << 8;mask = 0x5555 | 0x5555 << 16; 。

int allEvenBits(int x) {
  int mask = 0x55 | 0x55 << 8;
  mask = mask | mask << 16;
  x = x & mask;
  return !(mask^x);
}

谜题4 - allOddBits

与上一谜题相同，不过这次需要构造的数为0xAAAAAAAA。

int allOddBits(int x) {
  int mask = 0xAA | 0xAA << 8;
  mask = mask | mask << 16;
  x = x & mask;
  return !(mask^x);
}

谜题5 - anyEvenBit

判断偶数位是否含有1，只需要将所有偶数位与1相与，奇数位与0相与。若结果为0，则偶数位没有1，反之。

构造0x55555555与上题相同。

int anyEvenBit(int x) {
  int mask = 0x55 | 0x55 << 8;
  mask = mask | mask << 16;
  return !!(x&mask);
}

谜题6 - anyOddBit

思路同上一题，谜题5，anyEvenBit。

int anyOddBit(int x) {
  int mask = 0xAA | 0xAA << 8;
  mask = mask | mask << 16;
  return !!(x&mask);
}

谜题7 - bang

利用+0/-0最高位为0，而负数最高位为1，将正数转换为负数判断。

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

谜题8 - bitAnd

德·摩根律

A \land B = \lnot \lnot(A \land B) = \lnot(\lnot A \lor \lnot B)

int bitAnd(int x,int y) {
    return ~(~x|~y);
}

谜题9 - bitCount

从两位比特数入手，计算两位比特数中1的个数，就是高位与低位之和。
\begin{aligned} &00: 0+0=(00)_2=(0)_{10} \ \ \ \ &01: 0+1=(01)_2=(1)_{10} \\ &10: 1+0=(01)_2=(1)_{10} \ &11: 1+1=(10)_2=(2)_{10} \end{aligned}

$$
\begin {aligned}
& 令一个二进制数 B 为 b_{32}b_{31}b_{30}...b_{2}b_{1} \
& 令f(l,r)表示一个二进制数[l,r]区间内含有1的个数 \
\end {aligned}
\

f(l,r) = \begin {cases}
f(l,x) + f(x+1,r) & , l<=x<r \
b_{l} & , l =r
\end {cases}
\

\

\begin {aligned}
& 示例1(以下加法计算均用二进制表示): 设有8位二进制数B =10010101 \
& f(1,8) = f(1,4) + f(5,8) \
& f(1,4) = f(1,2) + f(3,4) \
& f(1,2) = f(1,1) + f(2,2) = b1 + b2 = 0 + 1 = 01 \
& f(3,4) = f(3,3) + f(4,4) = b3 + b4 = 0 + 1 = 01 \
& f(1,4) = f(1,2) + f(3,4) = 01 + 01 = 0010
\end {aligned}
$$

我们发现为了方便计算，应当每次都保证计算时两个数的位数相同。

每次将当前对半平分，以下过程为计算32位比特数步骤。
\begin {aligned} & f(1,32) = f(1,16) + f(17,32) \\ & f(1,16) = f(1,8) + f(9,16) \\ & f(1,8) = f(1,4) + f(5,8) \\ & f(1,4) = f(1,2) + f(3,4) \\ & f(1,2) = f(1,1) + f(2,2) \\ \end {aligned}
我们采用自底向上的类似与动态规划的思想，先计算f(1,1)+f(2,2)。

先构造一个只有低位f(1,1)的数a=x&0x1,和高位f(2,2)的数b=(x>>1)&0x1。

但我们发现可以同时计算f(3,3)+f(4,4)等数。

只需要将构造改为a=x&0x55555555，b=(x>>1)&0x55555555 ，x=a+b。

计算f(1,2)+f(3,4)依次类推，a=x&0x33333333,b=(x>>2)&0x33333333，x=a+b。

自底向上推到，不一一叙述。

int bitCount(int x) {
  int mask_1 = 0x55 << 8 | 0x55;
  int mask_2 = 0x33 << 8 | 0x33;
  int mask_4 = 0x0f << 8 | 0x0f;
  int mask_8 = 0xff << 16 | 0xff;
  int mask_16 = ~0 + (1 << 16);
  mask_1 |= mask_1 << 16;
  mask_2 |= mask_2 | mask_2 << 16;
  mask_4 |= mask_4 | mask_4 << 16;
  x = (x&mask_1) + ((x>>1)&mask_1);
  x = (x&mask_2) + ((x>>2)&mask_2);
  x = (x&mask_4) + ((x>>4)&mask_4);
  x = (x&mask_8) + ((x>>8)&mask_8);
  x = (x&mask_16) + ((x>>16)&mask_16);
  return x;
}

谜题10 - bitMask

将0xFFFFFFFF的高[highbit,32]位置为0，低[0,lowbit-1]位置为0即可。

构造低位为0的数(~0)<<lowbit，高位为0的数(~0)+(1<<(highbit+1))，改为(~0) + (1<<highbit<<1)防止highbit=32时出现undefined behavior。

int bitMask(int highbit, int lowbit) {
  return ((~0)<<lowbit)&((~0)+(1<<highbit<<1));
}

谜题11 - bitMatch

X Y bitMatch(X,Y)
1 1 1
0 0 1
1 0 0
0 1 0

根据真值表推导出表达式
ANS = (\lnot(a\land\lnot b))\land(\lnot(\lnot a \land b))

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

谜题12 - bitNor

\lnot(x \lor y) = \lnot x \land \lnot y

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

谜题13 - bitOr

x \lor y = \lnot \lnot (x \lor y) = \lnot (\lnot x \land \lnot y)

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

谜题14 - bitParity

偶数之差为偶数，偶数与奇数只差为奇数。所以32位二进制数中１和０的个数，奇偶性相同。

将32位二进制中所有数字进行异或计算。若有偶数个1则异或结果为0，反之。

使用如下公式，答案放在低位。每次可计算一半数字。
令二进制数B = b_{32}b_{31}b_{30}...b_{2}b_{1} \\ ANS = b_{32}\oplus b_{31}\oplus b_{30}...b_{2}\oplus b_{1} \\ ANS = (b_{16} \oplus b_{32}) \oplus (b_{17} \oplus b_{31})...(b_{2}\oplus b_{18}) \oplus (b_{1} \oplus b_{17}) \\ ANS = ((b_{16} \oplus b_{32}) \oplus (b_{17} \oplus b_{31}))...((b_{2}\oplus b_{18}) \oplus (b_{1} \oplus b_{17})) \\

int bitParity(int x) {
  x^=x>>16;
  x^=x>>8;
  x^=x>>4;
  x^=x>>2;
  x^=x>>1;
  return x&1;
}

谜题15 - bitReverse

类似谜题9，bitCount，只有计算部分不同。采用二分的思想，若交换32位数，则假定高16位和低16位已经逆序。此时只需要将高低16位交换即可。((x>>16)&mask1)|((x<<16)&mask2)，掩码保证这个数高16位必须为0，低16位为1。则两掩码的关系为mask2 = mask1 << 16. mask1 = 0x0000FFFF。

如何保证高16位和低16位已经是逆序，同样处理方法，需要16位数中高8位和低8位已经逆序。自底向上依次求解。

int bitReverse(int x) {
    int bitReverse(int x) {
    int mask_1 = 0x55 << 8 | 0x55; 
    int mask_2 = 0x33 << 8 | 0x33; 
    int mask_4 = 0x0f << 8 | 0x0f; 
    int mask_16 = 0xff << 8 | 0xff;
    int mask_8 = mask_16 << 8 ^ mask_16;
    mask_1 |= mask_1 << 16;
    mask_2 |= mask_2 | mask_2 << 16;
    mask_4 |= mask_4 | mask_4 << 16;
    x = ((x&mask_1)<<1)|((x>>1)&mask_1);
    x = ((x&mask_2)<<2)|((x>>2)&mask_2);
    x = ((x&mask_4)<<4)|((x>>4)&mask_4);
    x = ((x&mask_8)<<8)|((x>>8)&mask_8);
    x = ((x&mask_16)<<16)|((x>>16)&mask_16);
    return x;
}

谜题16 - bitXor

x \oplus y = \lnot (\lnot(a\land\lnot b))\land(\lnot(\lnot a \land b))

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

谜题17 - byteSwap

创建掩码分别获取第m，n字节的数字。mask = 0xff << (n<<3)，m = ((mask & x) >> (n<<3))&0xff

int byteSwap(int x, int n, int m) {
  int m_n = 0xff << (n<<3);
  int m_m = 0xff << (m<<3);
  int _n = ((x&m_n)>>(n<<3))&0xff;
  int _m = ((x&m_m)>>(m<<3))&0xff;
  return (x&~m_m&~m_n)|(_n<<(m<<3))|(_m<<(n<<3));
}

谜题18 - conditional

若x的取值为0x00000000或0xFFFFFFFF。则答案为(x&y)|(~x&z)。

若x！=0时，将x=0xFFFFFFFF。x = (!!x)<<31>>31。

int conditional(int x, int y, int z) {
  x = (!!x)<<31>>31;
  return (y&x)|(z&~x);
}

谜题19 - copyLSB

使用算数右移来拓展最低位。需将最低位放在最高位x<<31。

int copyLSB(int x) {
  return x<<31>>31;
}

谜题20 - distinctNegation

判断~x+1 != x，若两数相等异或值为0

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

谜题21 - dividePower2

对于正数，x/(2^n) = x >> n。接下来推导负数的除法。
令二进制数 B = b_{31}b_{30}...b_{1}b_{0} \\ (B)_{10} = -b_{31}2^{31}+b_{30}2^{30} + ... + b_{1}2^1 + b_{0}2^0 \\ (\frac{B}{2^n})_{10} = -b_{31}2^{31}+b_{31}2^{30} + ... + b_{n+1}2^{1}+b_{n}2^0 + (b_{n-1}2^{-1}+...+b_{0}2^{-n})
右移最高位补齐与b31相同，若小数部分大于0则需要在bn位加一修正。

使用n位1的二进制数相加，若在0到n-1的任意位上有1将会产生进位。

构造[0,n-1]区间全为1的数(1<<n)+0，当x<0会加上这个修正值。

int dividePower2(int x, int n) {
  return (x+(x>>31&((1<<n)+~0)))>>n;
}

谜题22 - evenBits

0x55555555 = 0x5555 << 16 | 0x5555，依次类推。

int evenBits(void) {
  int a = 0x55 << 8 | 0x55;
  return a << 16 | a;
}

谜题23 - ezThreeFourths

x*3 = x*2 + x = x >> 1 + x，x/4参考谜题21，dividePower2。

int ezThreeFourths(int x) {
  x = x + (x << 1);
  return (x+(x>>31&3))>>2;
}

谜题24 - fitsBits

判断其[n+1,3]区间上的数是否全为1，或0即可。x = x >> (b+~1+1)。

int fitsBits(int x, int n) {
  x = x >> (n+~1+1);
  return !~x|!x;
}

谜题25 - fitsShort

参考上一题，谜题24，fitsShort。

int fitsShort(int x) {
  x = x >> 0xf;
  return !~x|!x;
}

谜题26 - floatAbsVal

判断浮点数是否为NaN，是返回，否则，将最高位（符号位）置为0返回。

判断exp段是否全为1，(uf&0x7f800000) >> 23 == 0xff。

判断frac段是否全为0，uf << 9 != 0。

unsigned floatAbsVal(unsigned uf) {
  if((uf&0x7f800000)>>23 == 255 && uf<<9) return uf;
  return uf & 0x7fffffff;
}

谜题27 - floatFloat2Int

先将浮点数分成三段，符号部分s_ = uf>>31，指数大小exp_ = ((uf&0x7f800000)>>23)-127，获取小数部分，并补上浮点数缺省的1，frac_ = (uf&0x007fffff)|0x00800000。

处理特殊情况全为0是返回0，若指数大于31，整数无法表示溢出返回0x80000000。若指数小于0，该数0<x<1返回0。

若指数部分大于23则将小数部分向左移动frac_ <<= (exp_ - 23) ，exp_代表指数大小。

若指数部分小于23则将小数部分向右移动frac_ >>= (23 - exp_) ，exp_代表指数大小。

考虑最后符号，正数转换为负数不会产生溢出。若frac_为正数，则根据s_调整正负输出即可。

若frac_为负数，唯一正确情况为0x80000000。

int floatFloat2Int(unsigned uf) {
  int s_    = uf>>31;
  int exp_  = ((uf&0x7f800000)>>23)-127;
  int frac_ = (uf&0x007fffff)|0x00800000; 
  if(!(uf&0x7fffffff)) return 0;
  
  if(exp_ > 31) return 0x80000000;
  if(exp_ < 0) return 0;
  
  if(exp_ > 23) frac_ <<= (exp_-23);
  else frac_ >>= (23-exp_);

  if(!((frac_>>31)^s_)) return frac_;
  else if(frac_>>31) return 0x80000000;
  else return ~frac_+1;
}

谜题28 - floatInt2Float

与上一题相同，分三部分处理，获取符号位s_ = x&0x80000000，若为负数-x，变为正数，则0x80000000为特殊情况分开处理，考虑特殊情况，0x0和0x80000000，这两种情况直接返回0和0xcf000000。

获取最高位的1所在位置，while(!(x&(1<<n_))) n_--;。

若n_ <= 23这个数需要向左移动到小数部分起始位置（将1放在第23位上），if(n_<=23) x<<=(23-n_);。

若n_ > 23这个数需要向右移动到小数部分起始位置（将1放在第23位上），这时候需要考虑移出部分的舍入问题，若移出部分大于0.5则向上舍入，若小于0.5则向下舍去，若等于0.5则向偶数舍入。

先将>=0.5情况等同考虑，向上舍入x+=(1<<(n_-24))。若==0.5时，舍入情况若为奇数，我们需要-1操作变为偶数，即将最低位的1变为0，x&=(0xffffffff<<(n_-22))，若向上舍入时最高位产生了进位，还需要加上进位if(x&(1<<n_)) ;else n_++;。之后拼接浮点数即可。

unsigned floatInt2Float(int x) {
  int s_ = x&0x80000000;
  int n_ = 30;
  if(!x) return 0;
  if(x==0x80000000) return 0xcf000000;
  if(s_) x = ~x+1;
  while(!(x&(1<<n_))) n_--;
  if(n_<=23) x<<=(23-n_);
  else{
    x+=(1<<(n_-24));
    if(x<<(55-n_)) ;else x&=(0xffffffff<<(n_-22));
    if(x&(1<<n_))  ;else n_++;
    x >>= (n_-23);
  }
  x=x&0x007fffff;
  n_=(n_+127)<<23;
  return x|n_|s_;
}

谜题29 - floatIsEqual

直接使用uf == ug判断即可，但需要注意+0/-0还有NaN这两种特殊情况。

判断NaN时，指数段为0xff，小数段不全为0，(uf&0x7fffffff) > 0x7f800000。

int floatIsEqual(unsigned uf, unsigned ug) {
  if(!(uf&0x7fffffff) && !(ug&0x7fffffff)) return 1;
  if((uf&0x7fffffff) > 0x7f800000) return 0;
  if((ug&0x7fffffff) > 0x7f800000) return 0;
  return uf == ug;
}

谜题30 - floatIsLess

获取浮点数的三部分，符号位0x1&(uf>>31)，指数部分0xff&(uf>>23)，小数部分uf&0x7fffff。

和上题29，谜题floatIsEqual相同，若为特殊情况+0/-0/NaN，返回0。依次比较符号位，指数位，小数位，即可。结果与符号位相异或可以取反，即根据正负判断条件相反。

int floatIsLess(unsigned uf, unsigned ug) {
  int uf_s = (uf>>31)&0x1 , ug_s = (ug>>31)&0x1;
  int uf_exp = (uf>>23)&0xff , ug_exp = (ug>>23)&0xff;
  int uf_frac = uf&0x007fffff, ug_frac = ug&0x007fffff;
  if(!(uf&0x7fffffff) && !(ug&0x7fffffff)) return 0;
  if((ug_exp==0xff&&ug_frac) || (uf_exp==0xff&&uf_frac)) return 0;
  if(uf_s^ug_s) return uf_s > ug_s;
  if(uf_exp^ug_exp) return (uf_exp<ug_exp)^(uf_s);
  if(uf_frac^ug_frac) return (uf_frac<ug_frac)^(uf_s);
  return 0;
}

谜题31 - floatNegate

考虑特殊情况NaN，和谜题29相同。使用异或，将最高符号位取反。

unsigned floatNegate(unsigned uf) {
  if((uf&0x7fffffff) > 0x7f800000) return uf;
 return uf ^ 0x80000000;
}

谜题32 - floatPower2

考虑特殊情况，指数exp<-127和 exp>128，分别返回0和0x7f800000。

unsigned floatPower2(int x) {
  if(x<-127) return 0;
  if(x>128) return 0x7f800000;
  x += 127;
  x = x << 23;
  return x;
}

谜题33 - floatScale1d2

考虑NaN和INF的特殊情况，即指数exp==255，if((uf&0x7fffffff) >= 0x7f800000)，返回参数。考虑为+0/-0的情况，if(!(uf&0x7fffffff))，返回0。

规格化小数*0.5若结果仍为规格化小数，这时候只需要指数-1，其他部分不变即可。(uf&0x807fffff)|(--exp_)<<23。规格化小数*0.5，可能结果变为非规格化。即exp==0或exp==1时的情况，这时候只处理小数部分，因为非规格化小数其指数部分为0，右移一位表示*0.5，考虑小数舍入，与谜题28相同，不过此时，只需要考虑最低两位数，舍入判断if((uf&0x3) == 0x3) uf = uf + 0x2;。只有当最低两位数为11时才需要向偶数进位舍入。

unsigned floatScale1d2(unsigned uf) {
  int exp_ = (uf&0x7f800000) >> 23;
  int s_ = uf&0x80000000;
  if((uf&0x7fffffff) >= 0x7f800000) return uf;
  if(exp_ > 1) return (uf&0x807fffff)|(--exp_)<<23;
  if((uf&0x3) == 0x3) uf = uf + 0x2;
  return ((uf>>1)&0x007fffff)|s_;
}

谜题34 - floatScale2

考虑原数为非规格化小数或0时，处理小数部分if(exp_ == 0) return (uf<<1)|s_;。若为NaN或INF时if(exp_ == 255) return uf;，直接返回。若结果，即指数加一++exp_,为INF时，保证其不为NaN，即小数部分全为0，if(exp_ == 255) return 0x7f800000|s_;。

unsigned floatScale2(unsigned uf) {
  int exp_ = (uf&0x7f800000)>>23;
  int s_ = uf&0x80000000;
  if(exp_ == 0) return (uf<<1)|s_;
  if(exp_ == 255) return uf;
  ++exp_;
  if(exp_ == 255) return 0x7f800000|s_;
  return (uf&0x807fffff)|(exp_<<23);
}

谜题35 - floatScale64

与上一谜题floatScale2相同，不过对于非规格化小数处理不同，若直接左移6位，还需要处理其指数部分。非规格化小数时，若第[22,17]全为0，即uf&0x007e0000 == 0，最终结果仍然为非规格化小数。反之，结果为规格化小数，需要重新计算指数。步骤如下：取得[22,17]中1所在最高位cnt_，即while(!(uf&(1<<cnt_))) cnt_--;，最终结果为左移uf <<= (23-cnt_)位，指数为exp_ = 7-(23-n)。

unsigned floatScale64(unsigned uf) {
  int exp_ = (uf&0x7f800000)>>23;
  int s_ = uf&0x80000000;
  int cnt_ = 22;
  if(exp_ == 0) {
    if(!(uf&0x007e0000)) return (uf<<6)|s_;
    while(!(uf&(1<<cnt_))) cnt_--;
    uf <<= (23-cnt_);
    return s_ | (uf&0x807fffff) | ((cnt_-16)<<23);
  }
  if(exp_ == 255) return uf;
  exp_+=6;
  if(exp_ >= 255) return 0x7f800000|s_;
  return (uf&0x807fffff)|(exp_<<23);
}

谜题36 - floatUnsigned2Float

参考谜题28，floatInt2FLoat。将符号位的处理修改即可。

unsigned floatUnsigned2Float(unsigned u) {
  int n_ = 31;
  if(!u) return 0;
  while(!(u&(1<<n_))) n_--;
  if(n_<=23) u<<=(23-n_);
  else{
    u+=(1<<(n_-24));
    if(u<<(55-n_)) ;else u&=(0xffffffff<<(n_-22));
    if(u&(1<<n_))  ;else n_++;
    u >>= (n_-23);
  }
  u=u&0x007fffff;
  n_=(n_+127)<<23;
  return u|n_;
}

谜题37 - getByte

1byte=8bit，直接右移n*8,n<<3位取字节n&0xff。

int getByte(int x, int n) {
  return (x>>(n<<3))&0xff;
}

谜题38 - greatestBitPos

转化问题为获取二进制数x，为1的最高比特位为n。
令二进制数B = b_{31}b_{30}...b_{2}b_{1}b_{0} \\ 令函数g(x) = \begin{cases} 1,& 若[b_{x}...b_{31}]\not=0 \\ 0,& 若[b_{x}...b_{31}]=0 \end{cases} \\ 二进制数x,第a位是为1的最高比特位\\ 满足g(a)=1并且g(a+1)=0 \\ 若g(a)=1,g(a+b)=0,则最高位f,a \le f < a+b。 \\ 采二分得到答案 \\ 令n=0\\ 若g(n+16)=1,n=16，否则n=0\\ 若g(n+8)=1,n=n+8,否则n=n \\ 依次类推
判断g(n+x)是否为1，使用&操作，!!(x&((~0)<<(n+16))。最后若结果为0时，使用&操作再处理一次。

int greatestBitPos(int x) {
  int n = 0;
  n += ((!!(x&((~0)<<(n+16)))) << 4);
  n += ((!!(x&((~0)<<(n+8)))) << 3);
  n += ((!!(x&((~0)<<(n+4)))) << 2);
  n += ((!!(x&((~0)<<(n+2)))) << 1);
  n += (!!(x&((~0)<<(n+1))));
  return (1<<n)&x;
}

谜题39 - howManyBits

令二进制数B = b_{31}b_{30}...b_{2}b_{1}b_{0} \\ 若能用x位补码表示，则b_{x}=b_{x+1}=...=b_{31}\not=b_{x-1} \\ 若30\ge y\ge x,b_{y}\oplus b_{y+1}=0,b_{x} \oplus b_{x-1}=1

所以我们只需要异或相邻的数x^=(x<<1)，找出为1的最高位在哪一位就可以了。参考上一谜题greatestBitPos。

int howManyBits(int x) {
  int n = 0;
  x ^= (x<<1);
  n += ((!!(x&((~0)<<(n+16)))) << 4);
  n += ((!!(x&((~0)<<(n+8)))) << 3);
  n += ((!!(x&((~0)<<(n+4)))) << 2);
  n += ((!!(x&((~0)<<(n+2)))) << 1);
  n += (!!(x&((~0)<<(n+1))));
  return n+1;
}

谜题40 - implication

x \to y = \lnot x \or y

int implication(int x, int y) {
  return (!x)|y;
}

谜题41 - intLog2

令二进制数 B = b_{31}b_{30}...b_{1}b_{0}(B>0,b_{31}=0) \\ (B)_{10} = b_{30}2^{30} + ... + b_{1}2^1 + b_{0}2^0 \\ floor(log_{2}(B))=a,b_{a}=1且b_{a+1}=...=b_{30}=0 \\

问题转化为寻找1所在最高位,参考谜题38 ，greatestBitPos。

int intLog2(int x) {
  int n = 0;
  n += ((!!(x&((~0)<<(n+16)))) << 4);
  n += ((!!(x&((~0)<<(n+8)))) << 3);
  n += ((!!(x&((~0)<<(n+4)))) << 2);
  n += ((!!(x&((~0)<<(n+2)))) << 1);
  n += (!!(x&((~0)<<(n+1))));
  return n;
}

谜题42 - isAsciiDigit

判断是否为0x30，!!((x>>4)^3)。判断低位是否为0x0000~0x1001，即当第3位出现1时，第1,2位均不能为0。x>>3&x>>1 | x>>3&x>>2。

int isAsciiDigit(int x) {
  return !(((!!((x>>4)^3))|(x>>3&x>>1)|(x>>3&x>>2))&1);
}

谜题43 - isEqual

判断相等使用异或。

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

谜题44 - isGreater

以下情况会返回1。当x>0,y<0，或者当x和y符号相同时mark_ = ~((x^y)>>31)，满足x+~y+1>0，x!=y时，equl_ = !!(x^y)=1，x+~y+1>=0时，(~(x+~y+1))>>31 = 0xffffffff

int isGreater(int x, int y) {
  int sign_ = ((~x&y)>>31)&1;
  int mark_ = ~((x^y)>>31);
  int equl_ = !!(x^y);
  return sign_ | ((mark_)&(~(x+~y+1))>>31&equl_);
}

谜题45 - isLess

思路与上一谜题isGreater相同。修改x和y的符号判断，以及x+~y+1的符号判断条件即可。小于0的数最高位只能为1，不用判断是否相等。

int isLess(int x, int y) {
  int sign_ = ((x&~y)>>31)&1;
  int mark_ = ~((x^y)>>31);
  return sign_ | (((mark_)&((x+~y+1))>>31)&1);
}

谜题46 - isLessOrEqual

思路与上一谜题isLess相同。综合谜题isGreater修改相等判断条件即可。

int isLessOrEqual(int x, int y) {
  int sign_ = ((x&~y)>>31)&1;
  int mark_ = ~((x^y)>>31);
  int equl_ = !(x^y);
  return sign_ | ((((mark_)&((x+~y+1))>>31)|equl_)&1);
}

谜题47 - isNegative

判断最高位。若为1返回1，反之。

int isNegative(int x) {
  return ((x>>31)&1);
}

谜题48 - isNonNegative

思路同上谜题isNegative。

int isNonNegative(int x) {
  return (~(x>>31)&1);
}

谜题49 - isNonZero

谜题7解法相同，bang，取反即可。

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

谜题50 - isNotEqual

谜题43解法相同，取反即可。

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

谜题51 - isPallindrome

先通过逆序低16位，再与高16比较，即可以知道是否是镜像。逆序过程参考谜题15，bitReverse。

int isPallindrome(int x) {
  int mask_1 = 0x55 << 8 | 0x55; 
  int mask_2 = 0x33 << 8 | 0x33; 
  int mask_4 = 0x0f << 8 | 0x0f; 
  int mask_8 = 0xff;
  int mask_16 = 0xff << 8 | 0xff;
  int tmp_=x;
  
  tmp_ = ((tmp_&mask_1)<<1)|((tmp_>>1)&mask_1);
  tmp_ = ((tmp_&mask_2)<<2)|((tmp_>>2)&mask_2);
  tmp_ = ((tmp_&mask_4)<<4)|((tmp_>>4)&mask_4);
  tmp_ = ((tmp_&mask_8)<<8)|((tmp_>>8)&mask_8);
  tmp_&=mask_16;
  x=(x>>16)&mask_16;
  return !(tmp_^x); 
}

谜题52 - isPositive

判断最高位即可，对于0需要特殊处理，使用!!x得到，若x=0这该值为0，否则为1。

int isPositive(int x) {
  return (((~x)>>31)&(!!x));
}

谜题53 - isPower2

问题转化为，二进制数x中只能出现一个比特位为1的数。还要排除负数与正数。我们发现若x==2^n则x-1的特征为[n-1,0]位均为1，所以x&(x-1)=0，利用这个性质，再排除特殊情况，便可以获得答案。

int isPower2(int x) {
  int ret = ((!(x&(x+~0))) & ((~(x>>31)&(!!x))));
  return ret;
}

谜题54 - isTmax

判断相等使用异或操作。Tmax满足tmax == ~(tmax+1)，排除同样满足条件的0xffffffff。

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

谜题55 - isTmin

判断相等使用异或操作。Tmin满足tmin == ~tmin+1，排除同样满足条件的0x00000000。

int isTmin(int x) {
  return !((x^(~x+1))|(!x));
}

谜题56 - isZero

int isZero(int x) {
  return !x;
}

谜题57 - leastBitPos

使用谜题53的思路，假设二进制数x为1的最低位在第n位，将x-1时，则[n-1,0]变为全1，[n+1,31]位不变，这部分做异或操作就可变为0，即x^(x-1)，这时候[n,0]会全部变为1，所以做与操作。

int leastBitPos(int x) {
  return (((x+~0)^x)&x);
}

谜题58 - leftBitCount

若二进制数x>>n，为0xffffffff，那么可以说明其[n,31]位上的数为全1，只要找出这个最大的数n，本题答案即为31-n=31+~n+1，运用类似于题目41的技巧来找出这位，若n=0时有两种情况，0xffffffff和0xfffffffe，需要区别。

int leftBitCount(int x) {
  int cnt = 0;
  int off = 1&(!(~x));
  cnt += (!!(~(x>>16)))<<4;
  cnt += (!!(~(x>>(cnt+8))))<<3;
  cnt += (!!(~(x>>(cnt+4))))<<2;
  cnt += (!!(~(x>>(cnt+2))))<<1;
  cnt += (!!(~(x>>(cnt+1))));
  return 32+~cnt+off;
}

谜题59 - logicalNeg

与谜题7重复。

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

谜题60 - logicalShift

默认右移为算数右移，x>>n，后只需要将高[31-n+1,31]位变为0即可，构造掩码。~0+(1<<(32+~n)<<1)，将31-n分开计算避免溢出，出现未定义行为。

int logicalShift(int x, int n) {
  int mask_ = (~0)+(1<<(32+~n)<<1);
  return (x>>n)&mask_;
}

谜题61 - minusOne

返回0xffffffff，即~0。

int minusOne(void) {
  return ~0;
}

谜题62 - multFiveEighths

与谜题23为相同问题。

int multFiveEighths(int x) {
  x = x + (x<<2);
  return (x+(x>>31&7))>>3;
}

谜题63 - negate

利用补码-x = ~x+1。

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

谜题64 - oddBits

即返回0xaaaaaaaa，利用0xaa移位以及或运算。

int oddBits(void) {
  int x = 0xaa;
  x |= x<<8;
  x |= x<<16;
  return x;
}

谜题65 - remainderPower2

保留这个数的第[0,n-1]位即可，负数转化为正数处理，最后再将结果转换回来。使用如下方法转化正负，x = ((~s_)&x)|(s_&(~x+1));，若s_==0即为正数，反之。

int remainderPower2(int x, int n) {
  int s_ = x>>31;
  x = ((~s_)&x)|(s_&(~x+1));
  x &= (~0+(1<<n));
  return ((~s_)&x)|(s_&(~x+1)); 
}

谜题66 - replaceByte

首先去除x的第n字节数，与~(0xff<<(n*8))相与，然后与c<<(n*8)相或。

int replaceByte(int x, int n, int c) {
  int mask_ = 0xff << (n<<3);
  c <<= (n<<3);
  return (x&(~mask_))|c;
}

谜题67 - rotateLeft

谜题68 - rotateRight

上一篇 下一篇

猜你喜欢

热点阅读