帖子说明：该贴仅用于交流学习。因本人在完成实验的过程中，缺乏参考资料和基础的位运算经验，在刚开始接触这个实验的时候非常痛苦。因此分享我的实验思路，用于帮助同样初接触位运算的学习者。

        很难的题在少数，希望广大学习者们先自行思考，再参考我的思路。毕竟练习才是进步的唯一路径。

1、bitAnd

/*
 * bitAnd - x&y using only ~ and |
 *   Example: bitAnd(6, 5) = 4
 *   Legal ops: ~ |
 *   Max ops: 8
 *   Rating: 1
 */
int bitAnd(int x, int y)
{
  return ~(~x | ~y);
}

每一位逻辑与：a&b=~~(a&b)=~(~a|~b)，对int x,y 进行相同的位运算等于对每一个位执行上述a、b的运算。实现位与。

2、getByte

/*
 * getByte - Extract byte n from word x
 *   Bytes numbered from 0 (LSB) to 3 (MSB)
 *   Examples: getByte(0x12345678,1) = 0x56
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 6
 *   Rating: 2
 */
int getByte(int x, int n)
{
  return (x >> (n << 3)) & 0xff;
}

从右到左，分别对应0、1、2、3。每组数字占8位。因此，得到相应的数字即为向右移动n*8位。然而这只去掉了右边的数字，左边的数字仍然保留。我们只需要将其对0b 1111 1111（即0xff）进行位与，即可只保留最右边两个整数。

3、logicalShift

/*
 * logicalShift - shift x to the right by n, using a logical shift
 *   Can assume that 0 <= n <= 31
 *   Examples: logicalShift(0x87654321,4) = 0x08765432
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 20
 *   Rating: 3
 */
int logicalShift(int x, int n)
{
  return (x >> n) & (~(((1 << 31) >> n) << 1));
}

算术右移和逻辑右移的区别就在于当对负数时，是补0还是补1. 因而我们只需要在算术右移后，保留右边的有效位，左边都变成0即可。和上一题一样，我们将它和左边0右边1的数位与就能实现。

在右移n位后，左边补充了n位，右边剩下32-n位。我们只需要将其与0b 0...0 1...1位与，其中有n个0，32-n个1. 那么这样的数该怎么创造呢。我们只需要将1左移31位到最左边，然后将其算术右移n-1位，即可实现0b 1...1 0...0，其中有n个1，32-n个0。将其取反即可得到。

4、bitCount

/*
 * bitCount - returns count of number of 1's in word
 *   Examples: bitCount(5) = 2, bitCount(7) = 3
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 40
 *   Rating: 4
 */
int bitCount(int x)
{
  int mask1 = 0x55 | (0x55 << 8);
  int mask2 = 0x33 | (0x33 << 8);
  int mask3 = 0x0F | (0x0F << 8);
  int mask4 = 0xFF | (0xFF << 16);
  int mask5 = 0xFF | (0xFF << 8);
  mask1 = mask1 | (mask1 << 16);
  mask2 = mask2 | (mask2 << 16);
  mask3 = mask3 | (mask3 << 16);

  x = (x & mask1) + ((x >> 1) & mask1);
  x = (x & mask2) + ((x >> 2) & mask2);
  x = (x & mask3) + ((x >> 4) & mask3);
  x = (x & mask4) + ((x >> 8) & mask4);
  x = (x & mask5) + ((x >> 16) & mask5);

  return x;
}

这道题难度较高，主要在怎么累加1的个数。我就想能不能把他们分成小块，进行分块的二进制加法，最后逐渐递归实现，思路如下。

首先将32位分成16块，每块为相邻的两位。然后我定义了mask1，它为0b 0101...01。用于取每块中后面的一位。将其与x位与，即可得到每块后面一位的1的位。同样，我们将x右移1位，与mask1位与。这样的好处不仅在于可以保留每块前面一位的1的位，还在于将前面一位移动到了后面一位。这意味着我们可以直接对刚刚位与得到的两个数进行累加。每个块中对应的两位二进制数即为这个块中1的数目。将其存储回x中。

同理，我们再把x分成8个块，每个新块包含先前相邻的两个块。同理，我们创造mask2，令他为0b 00110011....0011。先将其与x位与，得到块中后面两位二进制数。再将x右移2位，与mask2位与。从而得到了块中前面两位二进制数。再将上面的两个数进行累加，每个块中对应的四位二进制数即为这个块中1的数目。将其存储回x中。

以此类推，再将相邻的两个块进行合并，每个块中包含的新二进制数表示这个块中1的数目。最后，合并为至多16位的二进制数。这个数即统计了所有1的数目。

5、bang

/*
 * bang - Compute !x without using !
 *   Examples: bang(3) = 0, bang(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4
 */
int bang(int x)
{
  return (~((x | (~x + 1)) >> 31)) & 1;
}

这里先回顾非的性质。所有非零的非为0，0的非为1。因而，我们只需要对0进行特殊讨论即可。0的代数性质是它的相反数还是0。其他数的相反数都不为0，且一正一负。因而，我们就这一特征入手，先对x取相反数，然后将x和-x或。这时，我们分类讨论：

·若x为0，x和-x或运算结果一定为0b 00...0

·若x不为0，由于x和-x一正一负，最左位一定是0和1或运算，结果是1. 我们将其右移31位，可得到0b 11...1.

由于要取非运算，因而，我们把得到的二进制数取反，即可输入0，得到0b 11...1；输入非0，得到0b 11...1。

但是到这里还没结束，我们输入0，输出的十进制值是-1. 为解决这一问题，我们将得到的二进制数和1位与（只保留最低位的1，使它等于十进制1）即可。

6、tmin

/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void)
{
  return 1 << 31;
}

本题要得到最小的int。显然是0b 100...0。将1左移31位即可。

7、fitsBits

/*
 * fitsBits - return 1 if x can be represented as an
 *  n-bit, two's complement integer.
 *   1 <= n <= 32
 *   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int fitsBits(int x, int n)
{
  return !(((x << (32 + ~n + 1)) >> (32 + ~n + 1)) ^ x);
}

在做这道题以前，我们先回顾一下整数的表示。例如5的二进制表示为0b 00...0101，-4的表示为0b 11...100。其中，5至少需要4位表示，-4至少需要3位表示。我们不妨定义表示数字的至少需要的那几位称为有效位。为何定义为有效位，因为若我们左移若干位，但是没有损失有效位，再将其右移相同位数，数值与先前一致；若左移过多，有效位损失，右移后数值会与左移前不同。因而，这成了我们解题的关键。

我们继续观察发现，有效位左边的数值均相同，且等于有效位的最高位。若为32位整数，有效位和其余位的关系为：有效位+其余位=32。因而，我们先将x左移32-n位，再右移32-n位。

·若新数值与x相同，则说明x可以用n位表示，应返回1；

·若不同，则x不能用n位表示，应返回0.

如何在两数相同时返回1，两数不同时返回0呢？答案是 !(a^b)。对a和b的每一位异或，如果a==b，则a^b==0，否则不等于0. 我们对齐取非即可。

8、divpwr2

/*
 * divpwr2 - Compute x/(2^n), for 0 <= n <= 30
 *  Round toward zero
 *   Examples: divpwr2(15,1) = 7, divpwr2(-33,4) = -2
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 2
 */
int divpwr2(int x, int n)
{
  int bias = (x >> 31) & ((1 << n) + ~0);
  return (x + bias) >> n;
}

这道题很考验数学水平。我首先想到的是直接将x>>n即可。但是这对非负数成立，对负数可不行。例如，-5的二进制表示为0b 1011，如果我们令n=2，右移两位得到0b 1110，答案是-2，但是(-5)/(2^2)向0取整应该是-1。因为右移的过程相当于把原数变小了（损失了加的一些数）

为修正这一过程，我曾想到一种复杂的方法，对正数正常做，对负数判断，如果能整除就返回原值，如果不能整除就对它加1。但是它的逻辑式我用了16个逻辑符，超过了本题15个的限制，因此我最后咨询了ai。它给了我一个极其具有数学美感的解决方法。对x增加(2^n)-1。这样的效果是，当x非负是，它除以2^n对零取整的结果不变；而对负数，它实现了对零取整的效果。具体的数学原理就不在这里赘述了。大家初高中数学应该学过。

9、negate

/*
 * negate - return -x
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x)
{
  return ~x + 1;
}

这道题很简单，直接返回-x。还记得补码的性质吗。x + ~x + 1 = 0. 所以-x就等于 ~x + 1。

10、isPositive

/*
 * isPositive - return 1 if x > 0, return 0 otherwise
 *   Example: isPositive(-1) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 8
 *   Rating: 3
 */
int isPositive(int x)
{
  return !(x >> 31 | !x);
}

相信做了上面那么多题，这题也就不在话下了，我们直接对符号位特征进行分析即可。X>>31即可保留符号位，非负数为0b 00...0，负数为0b 11...1。本题要求我们正数返回1，非0或负数返回0. 因此我们把0的情况排除，取非即可。即我们应该让右移后0对应的情况得到0b 11...1，怎么实现呢，直接把它打个补丁，把x >> 31 或 !x 就行了。最后对它取非。

11、isLessOrEqual

/*
 * isLessOrEqual - if x <= y  then return 1, else return 0
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y)
{
  return ((x >> 31) & ~(y >> 31) & 1) | ~((x >> 31) ^ (y >> 31)) & !((y + (~x + 1)) >> 31);
}

这道题看似很简单，我们y-x，判断符号是不是0就行了。但是还涉及到溢出的问题，就让它变得比较恶心。我们先来思考一下什么时候做差会溢出。当两数同号时，再怎么减也就那样了，绝对值肯定小于其中的一个数；当两数异号时，较小的负数减去较大的正数可能负溢出，较大的正数减去较小的负数可能正溢出。因而，我们需要单独考虑这两种情况。

·当y为正数，x为负数，显然y大于x，应返回1，为我们直接去符号位位与1即可。

·当y为负数，x为正数，显然y小于x，应返回0，我们不管就自动排除这种情况了。

最后，我们在额外给y-x添加限制条件，将它和y-x与起来即可发挥作用。要求x和y符号相同，这里我直接先异或后取反，(~((x >> 31) ^ (y >> 31))，就去掉同正和同负的冗长判断了。

然后我们用y + (~x + 1) 实现了y-x，但这不符合我们的要求，我们只需要它为正，即符号位为0就行。所以我们将它右移31位获得符号位。当y>=x，我们得到0b 00...0，但应当返回1；当y<x，我们得到0b 11...1，但应当返回0.解决方法很简单，我们直接取非即可。

12、ilog2

/*
 * ilog2 - return floor(log base 2 of x), where x > 0
 *   Example: ilog2(16) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 90
 *   Rating: 4
 */
int ilog2(int x)
{
  int result = 0;
  result = (!!(x >> 16)) << 4;
  result = result + ((!!(x >> (result + 8))) << 3);
  result = result + ((!!(x >> (result + 4))) << 2);
  result = result + ((!!(x >> (result + 2))) << 1);
  result = result + (!!(x >> (result + 1)));
  return result;
}

这道题要求我们对32位整数取2为底数x的对数，实际上就是问右移几次能把最高位的1移动到最右边。为了快速，我们选择二分查找。首先右移16位，如果移动后不为0，说明至少能右移16位，我们先把它累加起来。怎么累加呢，我们只需要取两次反，即可把非0的数变成1，然后左移4位就是16，此时result=16. 当然，如果右移16位只剩下0了（例如x=2，0b 010），这时取两次反还是0，不能起到累加效果，rusult依旧是0。

后面的操作同理，再二分，将x右移result+8位。为什么是result+8呢，因为如果rusult==16，说明它至少能右移16位；如果result==0，说明只能右移小于16位。因而我们对16进行二分。相同的方法，右移后再取两次反，但这次我们右移的位数是8，result也就需要累加8，我们将取两次反的结果左移3位即可。后面的操作同理。最终，result就是我们得到的结果。右移result次能把最高位的1移动到最右边。

---

下面我们进入了小数部分，小数部分的题比较复杂，所以也就放松了要求，可以使用条件和循环了。在进入小数部分以前，我们先回顾一些小数部分的知识，32位单精度浮点数从左到右分别为：1位符号位，8位exp位，23位frac位。下面我们开始：

13、float_neg

/*
 * float_neg - Return bit-level equivalent of expression -f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representations of
 *   single-precision floating point values.
 *   When argument is NaN, return argument.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 10
 *   Rating: 2
 */
unsigned float_neg(unsigned uf)
{
  unsigned exp = uf & 0xFF << 23;
  unsigned frac = uf & 0x007FFFFF;
  // Check if uf is NaN
  if (exp == 0xFF << 23 && frac != 0)
  {
    return uf;
  }
  // Flip the sign bit
  return uf + (1 << 31);
}

这道题要求我们取相反数，所以我们应该保留exp位和frac位不变，修改符号位即可。但是问题就在于可能出现NaN的问题。回顾一下IEEE的浮点数表示方法，当exp=0b 11...1, frac != 00...0时，表示NaN。因而我们提取出了exp和frac位进行判断，如果是NaN就返回原数；如果不是，就将其符号位+1后返回。由于当符号位为1是会溢出为0其效果等于对符号位取反。

对于提取exp的方法，我们将0xff，也就是0b 00...0 1111 1111左移23位，让它和exp位对应，进行位与，就可只保留exp部分，其他位都为0。同理，提取frac部分时，我们使用的是0x007FFFFF，它的二进制表示是后23位均为1，其余位均为0。这是用于保留最后23位。

14、float_i2f

/*
 * 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.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_i2f(int x)
{
  unsigned mask = 1 << 31;
  unsigned sign = x & mask; // Extract the sign bit
  int shift = 0;
  unsigned exp = 0;
  unsigned frac;
  if (x == 0)
    return 0; // Special case for zero

  if (sign)
    x = -x; // Make x positive if it is negative

  while (!(x & mask))
  {
    x <<= 1;
    shift++;
  }
  exp = 158 - shift;            // 127 (bias) + 31 - shift
  frac = (x & 0x7FFFFFFF) >> 8; // Extract the fraction bits
  // Round to the nearest even
  if (x & 0x80 && ((x & 0x7F) > 0 || (frac & 1)))
  {
    frac++;
    if (frac >> 23)
    { // Handle carry
      frac &= 0x007FFFFF;
      exp++;
    }
  }

  return sign | (exp << 23) | frac;
}

这道题比较麻烦，下面我们一点一点分析。由于int可以是正数、0或负数。因此多种情况会让我们的过程非常复杂。因此我们思考能不能把这一过程简化一下。我们想到，如果x==0，分数二进制表示也全是0，我们直接返回0即可；如果x为负数，在分数表示时只有符号位和正浮点数不同。因此，我们可以先行对0和负数的情况进行判断。当x==0时，直接返回0；当x为负数时，我们直接把x变为正数。其中，去们用sign取x的符号位（x的最高位，0非负，1为负）

接下来，我们只需要处理正数的情况了。正数时，我们为将其表示向IEEE靠拢，应该先变成科学计数法表示，只要最高位为0（x & mask==0b 00...0），就将x左移，保留移动后的x和移动的位数。然后，我们就可以计算exp和frac值了。

exp的值为bias+实际的2的指数。由于是单精度浮点数，exp8位，所以bias=2^(8-1)-1=127，而变成科学计数法后，实际的指数E应该为最多右移几位可以让最后一个1到最低位。我们刚刚累积了把1左移至最高位所需的次数shift。简单分析不难得到，E和shift存在定量关系，E+shift=31。因此，E=31-shift。我们因而可以计算exp=127 + 31 -shift = 158 - shift。

然后再来计算frac。由于x的最高位是符号位，因此我们只提取x的后31位（位与0x7fffffff，对应0b 011...1）。由于frac只有23位，因此我们将它右移8位。

当然，到这里还没完，我们在int转float的过程中，若需要，应当向偶数取整。如果最低位（第23位）是1，并且后面的所有位（第23位后）不全为0或者分数的最低位是1，则需要向偶数取整，将frac累加1。如果这导致分数溢出（即超过23位），则分数部分清零并指数exp加1。

最后，再通过位或组成分数即可。

15、float_twice

/*
 * float_twice - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned float_twice(unsigned uf)
{
  unsigned sign = uf & 0x80000000; // Extract the sign bit
  unsigned exp = uf & 0x7F800000;  // Extract the exponent bits
  unsigned frac = uf & 0x007FFFFF; // Extract the fraction bits

  // Check if uf is NaN or infinity
  if (exp == 0x7F800000)
  {
    return uf;
  }

  // If uf is a denormalized number
  if (exp == 0)
  {
    frac <<= 1;
    // Handle the case where shifting the fraction makes it normalized
    if (frac & 0x00800000)
    {
      exp = 0x00800000;
      frac &= 0x007FFFFF;
    }
  }
  else
  {
    // If uf is a normalized number
    exp += 0x00800000;
    // Handle the case where incrementing the exponent causes it to overflow to infinity
    if (exp == 0x7F800000)
    {
      frac = 0;
    }
  }

  return sign | exp | frac;
}

这道题让我们让我们将浮点数×2。我们还是按照之前的方法，先把浮点数的符号位、指数位和小数位分别通过位或提取出来。然后我们判断是否是NaN或无穷，若是，我们直接返回原数。随后我们需要针对它是否是规格化数进行讨论。

若他是非规格化数，则exp是0. 我们只需要将frac左移一位即可。如果不幸左移一位后，frac最高位变成1了，则它变成规格化数了，则需要把exp的设为1，把frac的最高位1去掉。

若他是规格化数，则exp不是0. 我们只需要将exp+=1即可。如果不幸左移一位后，exp直接变成全1了，直接溢出成无穷，则需要把frac设置为0，代表无穷。

最后把各部分拼装成浮点数即可。

DATALAB实验到此结束，希望各位学习者能在我的解答中有所收获。祝各位一切顺利。