计算机组成原理

《深入理解计算机系统/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) 生成掩码,表示xy中哪些位相等 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>>310xFFFFFFFFx^(x>>31)即取反,(x>>31)&10x1

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=0x55555555mask = 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

思路同上一题,谜题5anyEvenBit

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&0x55555555b=(x>>1)&0x55555555x=a+b

计算f(1,2)+f(3,4)依次类推,a=x&0x33333333,b=(x>>2)&0x33333333x=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

类似谜题9bitCount,只有计算部分不同。采用二分的思想,若交换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的取值为0x000000000xFFFFFFFF。则答案为(x&y)|(~x&z)

x!=0时,将x=0xFFFFFFFFx = (!!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的二进制数相加,若在0n-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 + xx/4参考谜题21dividePower2

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

参考上一题,谜题24fitsShort

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

谜题26 - floatAbsVal

判断浮点数是否为NaN,是返回,否则,将最高位(符号位)置为0返回。

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

判断frac段是否全为0uf << 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,获取小数部分,并补上浮点数缺省的1frac_ = (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为特殊情况分开处理,考虑特殊情况,0x00x80000000,这两种情况直接返回00xcf000000

获取最高位的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变为0x&=(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<-127exp>128,分别返回00x7f800000

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

谜题33 - floatScale1d2

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

规格化小数*0.5若结果仍为规格化小数,这时候只需要指数-1,其他部分不变即可。(uf&0x807fffff)|(--exp_)<<23。规格化小数*0.5,可能结果变为非规格化。即exp==0exp==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_;。若为NaNINFif(exp_ == 255) return uf;,直接返回。若结果,即指数加一++exp_,为INF时,保证其不为NaN,即小数部分全为0if(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

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

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所在最高位,参考谜题38greatestBitPos

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位均不能为0x>>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,或者当xy符号相同时mark_ = ~((x^y)>>31),满足x+~y+1>0x!=y时,equl_ = !!(x^y)=1x+~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相同。修改xy的符号判断,以及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比较,即可以知道是否是镜像。逆序过程参考谜题15bitReverse

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^nx-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的思路,假设二进制数x1的最低位在第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时有两种情况,0xffffffff0xfffffffe,需要区别。

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

上一篇 下一篇

猜你喜欢

热点阅读