datalab

实验

---

isTmax (int x)

/* 返回最大的二进制补码数(32位数) */ 
int isTmax(int x) { return ~x>>31; }

为什么不对?

答：未考虑==符号右移==

1. 在二进制补码表示中，最大的整数是 0x7FFFFFFF（十进制 2147483647），其二进制为 01111111 11111111 11111111 11111111（最高位为0，其余位全为1）。
2. 当我们对最大整数 Tmax 取反（~x），得到 10000000 00000000 00000000 00000000，这是最小整数 Tmin。
3. 当我们将 Tmin 右移31位（~x>>31），所有位都会被符号位（最高位的1）填充，结果是 -1（全1）而不是 1。

以下是一个正确的实现：

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

/*
1. 如果 x 是 Tmax，那么 x+1 是 Tmin
2. x ^ (x+1) 应该是全1（-1）
3. (x^(x+1)) = *1
4. 还需要排除 x = -1 的情况，因为 -1 也符合上述条件
5. 通过 !!(x+1) 来确保 x+1 不为0，即 x 不为-1
*/

• 注意表达式中的&是按位运算而非逻辑运算&&
• 双感叹号”!!” 是一种将值转换为布尔值(boolean)的操作（因为实验要求不能用逻辑运算如&&）。它的工作原理是：
  1. 第一个感叹号”!”将值转换为布尔值并取反（求逻辑非）
  2. 第二个感叹号”!”再次对结果取反，从而得到原始值对应的布尔值

对于”!!(x+1)”这个表达式：

• 首先计算(x+1)的值
• 然后通过双感叹号将结果转换为布尔值
  非零数值会转换为true，而0会转换为false

allOddBits (int x)

---

这个函数要求检查一个32位的int型整数 x , 若其从0~31位的所有奇数位上都是1, 则返回1；

第一想法是：用一个32位数0xAAAAAAAA来充当 “掩码” , 令x&0xAAAAAAAA若仍等于0xAAAAAAAA则返回1；

但是题目明确要求不能使用大于0xff的常量, 怎么办？

可以采取 移位 的方法, “创造”出大常量：

int allOddBits(int x) {

  int mask = 0xAA;             // 10101010 in binary (奇数位为1的8位掩码)

  mask = mask | (mask << 8);   // 扩展到16位: 10101010 10101010

  mask = mask | (mask << 16);  // 扩展到32位: 10101010 10101010 10101010 10101010 (即0xAAAAAAAA)

  // 检查x的奇数位是否都为1，方法是与掩码进行按位与

  // 若结果等于掩码本身，说明所有奇数位都是1

  return !((x & mask) ^ mask); // 如果(x & mask) == mask，则返回1，否则返回0

}

negate (int x)

---

需要注意, 实验明确说明了参数 x 是32位整型, 所以符号位是第31位；通常容易认为最高“1”所在位就是符号位，比如误认为5=101的符号位是1， 但其实应该补上前面的0， 即==0==000 0000 0000 0000 0000 0000 0000 0101， 符号位是0。

继续拿$(5)_{10}=(101)_2$为例，-5的补码表示为1111 1111 1111 1111 1111 1111 1111 1011，即 按位取反后在最低位加1，这就是==二进制补码数 取负数 的方法==，故得到：

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

isAsciiDigit (int x)

---

目的是判断一个数是否在0x30~0x3a之间
如果用数学计算，可以很简单的用如下形式表示：
\(0x30<=x<=0x3a\)
但是要求不能这么写，那么就争取把这个式子用位运算表示出来：
重点是：<=怎么表示？
如果用数学式表达，0x30<=x可以被转换成：\(x-0x30>=0\)
我们把问题分解一下：

1. -运算的实现？
   题目要求不能用-，但是可以用+，而我们刚刚实现了negate取负函数，那么x-0x30自然就可以用x+(-0x30)来代替：

   x+(~0x30+1)  // -0x30=(~0x30+1)
   

2. 怎么表示>=0？
   我们知道二进制补码形式下，最高位也就是第31位，如果x-0x30得到的二进制补码数的第31位是1，就说明相减的结果为负，是0则说明为非负，那么就可以写成：
   \(!(x+(~0x30+1))>>31\)

其中!的作用是把(x-0x30)>>31的结果转化成一个bool型，并取非 ，所以如果 x>0x30，则(x-0x30)>>31=0，再取!就得到1，符合
”0x30<=x<=0x39“时返回1” 的要求。

x<=0x30也可以用同样的道理实现，不再赘述。