ICS-LAB1-Report

---

Bits.c

1. bitAnd–与

题目：

只用~和|实现&

样例：

bitAnd(6, 5) = 4

可使用操作： ~ |

最大操作数限制： 8

使用操作数： 4

int bitAnd(int x, int y) {
  return ~(~x | ~y); //De Morgan's laws
}

应用摩根律 ~(x | y) = ~x & ~y, 可得 x & y = ₍x | ~y)

---

2. getByte–获取字节

题目：

从x中提取字节n, n编号从0至3

样例：

getByte(0x12345678,1) = 0x56

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 6

使用操作数： 3

代码：

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

分析：

由于 1Byte = 8bits = 2^3bits， 所以 n Bytes = 2^3 * n bits

因而将n左移3位，即 n * 2^3, 再将x右移 n * 2^3 即可将所求字节放在低8位，将其与上0xff，即可取出字节。

---

3. logicalShift–逻辑右移

题目：

将x逻辑右移n位

样例：

logicalShift(0x87654321,4) = 0x08765432

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 20

使用操作数： 10

代码：

int logicalShift(int x, int n) {
  //flag equals to: if n == 0 return 0; else return 1;
  int flag = !!n;
  int mask = ~(flag << (32 + (~n + 1)));
  return (x >> n) & mask;
}

分析：

• 算数右移

算数右移即在右移后用原符号位数将高位补齐，保持右移后二进制数的符号保持不变。

• 逻辑右移

逻辑右移即在右移后用 0 将高位补齐，是“逻辑上”的右移。

在正常右移运算中使用的是算数右移，因而要解决的问题即对于负数如何将最高位补上0，而非符号位1。
我采取掩码的方式，先将x正常右移n位与上其高位的掩码，使其右移产生的高位变为0

• 掩码构造

掩码不能草率的构造为 ~(-1 << (32 - n)), 这种构造方式当n为0时会因-1被左移32位而导致异常，构造出来的mask仍为0

由于不能使用if，为判断n是否为0，我才用了一个flag = !n + ~0, 其有很好的性质。当n为0时，flag也为0，而当n不为零时，flag统一为-1，这样使用flag代替原先的-1, 从而避免上述情况。

这样我们可以使用 mask = ~(flag << (32 + (~n + 1)))，来构造掩码，当n为0时，flag为0，从而mask = -1，避免上述错误。

---

4. bitCount–比特计数

题目：

返回二进制数中1的个数

样例：

bitCount(5) = 2, bitCount(7) = 3

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 40

使用操作数： 36

代码：

int bitCount(int x) {
  int tmp, l1, l2, l4, l8, l16; //tmp is used to save ops
  tmp = (0x55 << 8) + 0x55;
  l1 = (tmp << 16) + tmp; //0x55555555
  tmp = (0x33 << 8) + 0x33;
  l2 = (tmp << 16) + tmp; //0x33333333
  tmp = (0x0f << 8) + 0x0f;
  l4 = (tmp << 16) + tmp; //0x0f0f0f0f
  l8 = (0xff << 16) + 0xff; //0x00ff00ff
  l16 = (0xff << 8) + 0xff; //0x0000ffff

  x = (x & l1) + ((x >> 1) & l1);
  x = (x & l2) + ((x >> 2) & l2);
  x = (x & l4) + ((x >> 4) & l4);
  x = (x & l8) + ((x >> 8) & l8);
  x = (x & l16) + ((x >> 16) & l16);
  return x;
}

分析：

• 分治思想

本题使用了一个简单的分治思想，对于一个二进制数，要对其中为1的位做计数， 对于1位二进制数来说，1的个数无非就是其本身所表示的1或0。利用这个特性，我们可以先将一个二进制数每一位独立分开为相间隔的两部分, 其每位表示的就是自身的二进制个数，再将两串二进制数对其相加，所得到的每两位分隔的二进制数就是表达这个位置的位为1的个数。

进一步相加为4位，8位其所代表的含义不变，最后合并至32位二进制数，其所表示的就是原二进制数中所含1的个数。

//以八位二进制数 10101110 为例//
按 1|0|1|0|1|1|1|0 分割， 为两串1|1|1|1和0|0|1|0，再将其合并，成为 01 | 01 | 10 | 01, 再将两串 01 | 10 和01 | 01合并得 0010 | 0011（这个很容易看出表示左四位有2个1，右四位有3个1），再次合并得 00000101, 得到总共有5个1。

//对于32位二进制数亦按此继续操作即可//

于是为完成分割取位的操作，我们需要采用掩码

• 0x55555555 0x33333333 0x0f0f0f0f 0x0000ffff

利用位运算分别构造，使用tmp可以节约ops, 之后按照分治思想进行操作即可。

---

5. bang–逻辑非

题目：

计算 !x 而不使用逻辑非!

样例：

bang(3) = 0, bang(0) = 1

可使用操作： ~ & ^ | + << >>

最大操作数限制： 12

使用操作数： 6

代码：

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

分析：

• 逻辑非

对于逻辑非运算，应该都很熟悉，!x 当且仅当x为0时其为1，其余时候都为0，可以用来区分零和非零数。

该问题的关键就是在于如何区分零和非零数，我们知道零的二补码仍然是零，而对于其余非零数，其符号位会有相应改变，利用这一性质，我们可以对零和非零数做出区分。

使用 ((x >> 31) | ((~x + 1) >> 31))，将二进制数x的符号位与其补码左移31位相与，如若是非零数，其中符号位至少有一个为1，所以经过31位的算数右移后，其中一项必为-1，一项为0，相与之后得到-1,。而对于0来说，结果始终为0。

最后只要将结果+1，就能得到逻辑非的效果。

---

6. tmin–最小数

题目：

返回二补码中最小的数

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 4

使用操作数： 1

代码：

int tmin(void) {
  return 1 << 31;
}

分析：

此题非常简单，我们知道计算机中负数是用其补码表示的，int所能表示的最小数为0x80000000(-2^31), 即符号位为1，其余皆为0，所以只要将1左移31位即可。

---

7. fitsBits–填充比特

题目：

返回1如果x可以表示为n位二补码，反之返回0 (1 <= n <= 32)

样例：

fitsBits(5,3) = 0, fitsBits(-4,3) = 1

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 15

使用操作数： 7

代码：

int fitsBits(int x, int n) {
  int k = x >> (n + ~0); // if can k = 0 or -1
  return !k | !(k + 1);
}

分析：

我们知道如若一个数能够被n位二进制数表示，则其第n位即最高位是符号位，那么将其右移n-1位后，根据算术右移，其得到的结果不是0，就是1。否则表示，其还有高于n位的位数， 即不能用n位表示。

所以用 k = x >> (n + ~0) 表示将其右移n-1位，再用 !k | !(k + 1) 判断k是否为0或-1

---

8. divpwr2–除以2的n次方

题目：

计算 x/(2^n), (0 <= n <= 30)

样例：

divpwr2(15,1) = 7, divpwr2(-33,4) = -2

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 15

使用操作数： 7

代码：

int divpwr2(int x, int n) {
    int sign = x >> 31;
    int bias = (1 << n) + ~0;
    x = x + (bias & sign);
    return x >> n;
}

分析：

本题的难点在于Round toward zero, 我们知道除以2的n次方即为将x右移n位。对于正数，尾数截断，因而自然向0舍入。而对于负数则不是如此，经试验在gcc上对于负数，其是向偶数舍入的，因而我们要对负数进行操作。

同时由于其向偶数舍入，我们不能简单地对负数进行+1操作，例如原本正确的 -7/4 = -1.25 = -1，但是经过+1操作后变为-6/4 = -1.5 Round toward even则变为了2。所以我们不应简单加一，而是加一个偏差值，其为2^n - 1，对于-7/4来说，就是3，加上bias之后得到(-7 + 3)/4即为-1。

所以我们构造bias = (1 << n) + ~0 (由于不能用减号，-1用+~0表示)，然后我们要记得将sign取出，在x进行加操作时先检查一下x是否是负数，再进行操作。最后只要方向的将x右移n位即可。

---

9. negate–取负

题目：

返回-x

样例：

negate(1) = -1.

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 5

使用操作数： 2

代码：

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

分析：

很简单，对于有符号二进制数取负就是取其补码，而补码等于其取反加一，返回取反加一即可。

---

10. isPositive–是正数

题目：

返回1如果x大于0，反之返回0

样例：

isPositive(-1) = 0.

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 8

使用操作数： 5

代码：

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

分析：

这题关键在于把0剔除了，区分正负数就是区分其符号位，将x右移31位，负数得-1，正数为0，用一个逻辑非使正数为1，负数为0，然后再和!!x与一下就能剔除0

• !!x 当 x == 0 时返回 0，不为 0 时返回 1

---

11. isLessOrEqual–小于等于

题目：

如果x小于等于y返回1，反之返回0

样例：

isLessOrEqual(4,5) = 1.

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 24

使用操作数： 14

代码：

int isLessOrEqual(int x, int y) {
  int res = y + (~x + 1); // y - x
  int xSign = x >> 31;
  int ySign = y >> 31;
  int dif = ~xSign + ySign;
  return (~(dif + 1 >> 31) & !(res >> 31)) | !dif;
}

分析：

我在这里采取了作差的方法 res = y + (~x + 1)，即计算一下y-x，判断其是否非负，同时也要考虑溢出问题，即 x 为负数，y为正数，y-x后溢出为负。

我将x,y右移31位代表其符号，若负则为-1，若正为0。我同时构造了一个 dif 以表示x,y符号之间的关系。

dif = ~xSign + ySign

1. 当 x < 0 && y < 0 时，dif = -1
2. 当 x < 0 && y > 0 时，dif = 0
3. 当 x > 0 && y < 0 时，dif = -2
4. 当 x > 0 && y < 0 时，dif = -1

将 x,y 符号之间的关系表达出来，把 dif 加一我们可以观察到当 x,y 同号时，dif为0，所以将其取反和 !(res >> 31) 相与，就可以表示同号不溢出的情况，而当 x < 0, y > 0 的情况发生时，我们注意到 dif 就是 0 ，所以我们直接或上 !dif 即可表达这种情况。

---

12. ilog2–以2为底的对数

题目：

返回x取以2为底的对数并向下取整，输入的 x > 0

样例：

ilog2(16) = 4

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 90

使用操作数： 48

代码：

int ilog2(int x) {
  int tmp, l1, l2, l4, l8, l16;
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  
  tmp = (0x55 << 8) + 0x55;
  l1 = (tmp << 16) + tmp;
  tmp = (0x33 << 8) + 0x33;
  l2 = (tmp << 16) + tmp;
  tmp = (0x0f << 8) + 0x0f;
  l4 = (tmp << 16) + tmp;
  l8 = (0xff << 16) + 0xff;
  l16 = (0xff << 8) + 0xff;

  x = (x & l1) + ((x >> 1) & l1);
  x = (x & l2) + ((x >> 2) & l2);
  x = (x & l4) + ((x >> 4) & l4);
  x = (x & l8) + ((x >> 8) & l8);
  x = (x & l16) + ((x >> 16) & l16);
  return x + ~0;

分析：

我们知道二进制数每位有其位权，所以对 x 取以2为底的对数就是指其为1的最高位的位权。为了获得最高位的位置，其实我们可以将其最高位往下全部变为1，再类似bitsCount数其中1的个数就行了。

我把 x 移位相与，保证最高位往下所有数字为1，再使用bitsCount就得到答案。

最后不要忘记减一

---

13. float_neg–浮点数的负数

题目：

返回-f，当NaN时，返回参数f

可使用操作： 所有的整型操作，包括 ||, &&. 以及 if, while

最大操作数限制： 10

使用操作数： 5

代码：

unsigned float_neg(unsigned uf) {
  unsigned exp = uf & 0x7f800000;
  unsigned frac = uf & 0x007fffff;
  if(exp == 0x7f800000 && frac)
    return uf;
  return uf ^= 0x80000000;
}

分析：

• IEEE-float

我们知道IEEE单精度浮点数，最高位为符号位，其后8位为阶码exp，后23位为尾数frac。其牺牲了精度来扩大了表达范围。

而当 exp 全 1 时，如若frac非全零，则表示NaN。若全零，则表示无穷大/小。

这里我们只要将原数和符号位0x80000000异或一下，即可取负。不要忘记排除NaN的情况。

---

14. float_i2f–int转float

题目：

把int类型的数转换为float表示(比特形式)

可使用操作： 所有的整型操作，包括 ||, &&. 以及 if, while

最大操作数限制： 30

使用操作数： 30

代码：

unsigned float_i2f(int x) {
  unsigned frac, mask1, mask2, mask3, mask4, d;
  int high = 0x80000000;
  unsigned sign = x & 0x80000000;
  unsigned exp = 127;
  int count = 32, i;
  if(sign)
    x = ~x + 1;
  else if(!x)
    return x;
  
  frac = x;

  for(;high; high >>= 1)
  {
    --count;
    if(high & x)
      break;
  }
  i = count - 23;
  mask1 = ~(1 << count); // the highest 1
  mask2 = 1 << i; //the lowest of remain frac;
  mask3 = mask2 >> 1; // the highest of deserted bits 
  mask4 = mask2 - 1; // the deserted bits
  exp += count;

  frac &= mask1;
  
  if(i > 0)
  {
    d = frac & mask4; // deserted bits
    if(d > mask3 | (d == mask3 && frac & mask2))
    {
      frac += mask2;
      if(frac > 0x3fffffff)
      {
        frac = 0;
        exp++;
      }
    }
    frac >>= i;
  }
  else
    frac <<= -i;

  return sign | exp << 23 | frac;
}

分析：

我认为这题比较难，我做了很久很久…它难在浮点数向偶数舍入以及其操作数的限制。

我们知道由于浮点数表示范围比整型大，我们可以将整型转换为浮点数，但是相应的会有一些精度的丢失，因为尾数frac只有23位，而int有31位可用。

所以其关键在于int的位数，一开始先把该取出来的都用掩码取出来，把负数和零处理一下。之后我利用了一个循环先找出int的最高位在哪，利用count计数。

后面我采取了四个掩码，分别代表最高位的1，留下的尾数中的最低位，要舍去的位数的最高位，以及舍弃的位数的掩码。利用这四个掩码我们可以达到存frac时，将其向偶数舍入。

具体操作是，先取出丢弃的尾数，将其存放在d中，看其有没有超过0.5 (即 d 是否大于 mask3) 如果大于，直接frac++就行。而如果等于的话，还要看frac是否是奇数 (即frac & mask2是否为1) 如果是，则要向偶数舍入,frac++。

加完frac之后还要注意溢出问题，如果溢出了，要将frac置0，然后把阶码 exp++，再按照之前输出来的尾数移动，将尾数对齐即可 （位数最高默认为1不存，因而把最高位隐去）。

最后把符号位，阶码位和尾数位拼接，得到最后的结果。

---

15. float_twice–float * 2

题目：

返回float * 2, 当参数是NaN时，返回参数

可使用操作： 所有的整型操作，包括 ||, &&. 以及 if, while

最大操作数限制： 30

使用操作数： 20

代码：

unsigned float_twice(unsigned uf) {
  unsigned sign = uf & 0x80000000;
  unsigned exp = uf & 0x7f800000;
  unsigned frac = uf & 0x007fffff;
  if(exp == 0x7f800000) //NaN & inf
    return uf;
  if(!exp && !frac) // 0
    return uf;
  if(!exp && frac <= 0x3fffff)  // low
    frac *= 2;
  else if(!exp && frac > 0x3fffff) // high
  {
    exp += 0x00800000;
    frac = (frac * 2) & 0x7fffff;
  }
  else // normal
    exp += 0x00800000;
  return sign + exp + frac;
}

分析：

主要要分析的地方，在于当阶码exp为0时，是否在乘2之后进位。所以要考虑尾数是否大于0x3fffff，如果小于等于之，则直接尾数乘2就行，不会溢出，否则则exp要进位，同时尾数乘2之后要与上0x7fffff保证不溢出。

其他正常情况直接exp++就行，注意一下特殊情况;

本题中测试集中有一个inf，也要直接返回参数uf

---

Bits_honor.c

1. bitReverse–比特翻转

题目：

把32比特int的比特位翻转

样例：

bitReverse(0x80000004) = 0x20000001
bitReverse(0x7FFFFFFF) = 0xFFFFFFFE

最大操作数限制： 40

使用操作数： 40

代码：

int bitReverse(int x)
{
   int tmp,l1, l2, l4, l8, l16;

   tmp = (0x55 << 8) + 0x55;
   l1 = (tmp << 16) + tmp;
   tmp = (0x33 << 8) + 0x33;
   l2 = (tmp << 16) + tmp;
   tmp = (0x0f << 8) + 0x0f;
   l4 = (tmp << 16) + tmp;
   l8 = (0xff << 16) + 0xff;
   l16 = (0xff << 8) + 0xff;

   x = ((x >> 16) & l16) | (x << 16);
   x = ((x >> 8) & l8) | ((x & l8) << 8);
   x = ((x >> 4) & l4) | ((x & l4) << 4);
   x = ((x >> 2) & l2) | ((x & l2) << 2);
   x = ((x >> 1) & l1) | ((x & l1) << 1);
   return x;
}

分析：

这题和 bitsCount 有异曲同工之妙，也是一个分治法，将32位二进制数一分为二，交换，再将内部各自再一分为二，交换，直至最底层2位二进制数互换位置，最后完成了将所有位数翻转的工作。

但值得注意的是，给出的是有符号的int，所以在右移交换位置时，会发生因为负数算术右移导致高位全是1的情况，致使在与的过程中高位全部变为1。这边只要将其移动后在和掩码相与就能解决这一问题。而对于低位，先与掩码相与再移动，可以省去取反得到高位掩码的操作数。再用tmp省一下操作数。

最后操作数正好卡在40

---

2. mod3–取模3

题目：

计算 x 取模 3，而不用%

样例：

mod3(100) = 1
mod3(-100) = -1

可使用操作： ! ~ & ^ | + << >>

最大操作数限制： 90

使用操作数： 24

代码：

int mod3(int x)
{
   int mask = (0xff << 8) + 0xff;

   x = (x >> 16) + (x & mask); // sum base 4^8 digits (a <= 0x1FFFE)
   x = (x >> 8) + (x & 0xff); // sum base 4^4 digits (a <= 0x2FD)
   x = (x >> 4) + (x & 0xf); // sum base 4^2 digits (a <= 0x3C)
   x = (x >> 2) + (x & 0x3); // sum base 4^1 digits (a <= 0x1D)
   x = (x >> 2) + (x & 0x3); // sum base 4^1 digits (a <= 0x9)
   x = (x >> 2) + (x & 0x3); // sum base 4^1 digits (a <= 0x4)

   x = (((x + 1) >> 2) + x) & 0x3;
   return x;
}

分析：

这题难度算是比较大的，我参考了一些资料最后才写出这个代码。其实这题也与bitsCount有着一定的联系。

对于解这题有一个根本的公式即

a % m = ((b % m)(a/b) + (a % b)) % m
其中b是进制数

我们知道，如果想要知道一个十进制的数能否被三整除，只要看它所有数位之和是否能被三整除就行了。其实这就是上述公式的特殊情况，由于10 mod 3 == 1 所以其就退化为

a mod m = (a/b + a % b) % m
递归下来就是所有数位之和

而对于二进制的情况，我们可以将进制位b选为4，这样正好是两位二进制数，同时4 % 3 == 1，这样一来，对于二进制数中我们只需要统计所有两两数位(四进制)的和能否被三整除就行了。

而考虑到我们每做一次 a/b + a % b 统计数位和都减小了数的规模，这样只要做有限次就能够将数控制在<=3的范围内。

对于a % 4，这是一个经典的trivial情况，我们只需要做 a & 3，就能够轻松得到a % 4的值。而对于a/4，只需要做a >> 2即可。

对于二进制数我们不仅可以按两位两位的四进制数位和来数，也可以直接数其倍数(4^{i)，从最大4}8开始统计，一步步减小x的值，最后将x做到<= 3的范围

最后要判断x是否为3，如果为3的话则要置为0，我利用3数位全为1的特点，将其+1进位后，右移2位。如果为3，则得到的是1。将其再加上x，如若x是1或2，则还是不变，但如果是3，它又会进位到4，那么我们只要再与上0x3，则会得到0，即为想要的结果。

---

3. float_f2i–float转int

题目：

输入一个按二进制位储存的float（以unsigned表示），将其转为int输出。(NaN,inf，溢出直接返回参数)

可使用操作： 所有的整型操作，包括 ||, &&. 以及 if, while

最大操作数限制： 30

使用操作数： 17

代码：

int float_f2i(unsigned uf)
{
   int sign, exp, frac, res;
   unsigned int tmp;

   if(!uf)
      return 0;
   sign = uf & 0x80000000;
   exp = uf & 0x7f800000;
   frac = (uf & 0x007fffff) | 0x00800000;

   if(exp == 0x7f800000) //NaN and inf
      return 0x80000000u;

   exp >>= 23;

   if(exp < 127)
      return 0;
   else if(exp > 158)
      return 0x80000000u;
   else if(exp > 150)
      tmp = frac << (exp - 150);
   else
      tmp = frac >> (150 - exp);

      
   if(sign)
      res = ~tmp + 1;
   else
      res = tmp;
   
   return res | sign;
}

分析：

这题特殊情况比较多，把NaN和inf处理一下，然后注意一下溢出情况，即取出来的exp - bias > 31，肯定超过2^31整型储存的最大值，直接返回0x80000000u，然后对于exp小于127的，其指数是负数，直接返回int值为0。对于在exp - bias 在 0 到 31 之间的，由于frac只有23位，所以要将注意一下讨论23的情况。

最后把取出来的符号位对一下，如果负数取反加一，正数直接等，最后再或上符号位，返回答案。

参考

---

https://baike.baidu.com/item/算术右移/3711081?fr=aladdin
https://blog.csdn.net/jiahonghao2002/article/details/108223366
https://leetcode-cn.com/problems/reverse-bits/solution/dian-dao-er-jin-zhi-wei-by-leetcode/
http://homepage.cs.uiowa.edu/~jones/bcd/mod.shtml#exmod3
https://blog.csdn.net/xindaxinda123/article/details/95617758
https://www.runoob.com/w3cnote/32-float-storage.html

最后

以上就是有魅力棒球为你收集整理的【ICS计算机系统】位运算Lab1ICS-LAB1-Report的全部内容，希望文章能够帮你解决【ICS计算机系统】位运算Lab1ICS-LAB1-Report所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。