The Blog of Yu4n
0%

CSAPP DATAlab

发表于 更新于

bitXor(x,y)用‘&’和‘~’完成异或操作

在此之前，我们先了解一下这三个运算符的运算规则

设A=60，B=13；

则A = 0011 1100；B = 0000 1101。

1
2
3
4
5
“与”--‘&’：
0&0=0;   
0&1=0;    
1&0=0;     
1&1=1;A&B=0000 1100
1
2
3
“取反”--‘~’：
对形式取反
~A = 1100 0011 = -61。
1
2
3
4
5
6
“异或”--‘^’：
0^0=0;   
0^1=1;   
1^0=1;  
1^1=0;
(A ^ B) 将得到 49，即为 0011 0001

可以看到，&和^的区别在于，除两数同时为0时，结果相反。那么我们分而治之，设置两种情况，以上面的A,B为例。

第一种–只考虑不是两个0进行运算的时候：两数直接进行&运算然后取反，得1111 0011；

第二种–只考虑是两个0进行运算的时候：这次我们的目的是在其他数（即上面那个数从左往右的第3、4、5、6，8位）经过运算且发生变化后保持0和0进行运算后结果依然为0，才能让两个最终运算结果在最后&时得到与^相同的数。这里绕个弯，先将A,B各自取反，进行&运算后，再将结果取反。可以发现达到了开始时的目的

最后，将两情况的结果进行与运算，得到答案。

1
2
3
4
int bitXor(int x, int y)
{
    return ~(~x&~y)&~(x&y);
}

借用大佬的思路如下：（比我清晰很多，一语即中。）

所谓异或就是当参与运算的两个二进制数不同时结果才为1，其他情况为0。C 语言中的位操作对基本类型变量进行运算就是对类型中的每一位进行位操作。所以结果可以使用“非”和“与”计算不是同时为0情况和不是同时为1的情况进行位与，即~(~x&~y)&~(x&y) 。

tmin()最小二进制补码整数型

因为整数int型位32位（一般情况下，此处不讨论16位），而最小的补码只需要是第一位为1（1开头表示负数），后面的全是0即可，所以只需要将1左移31位即可（因为机器从0开始读。）

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

isTmax(x)判断当X为最大整型二进制数为真，否则为假

此处先说明一下最大二进制整数，其实是0x7fffffff(二进制整数首位是 0，其余都是1，f代表1111，32位)

F的二进制码为 1111
7的二进制码为 0111；0xffffffff为-1；但最小值是0x80000000

上文说了开头为1表示是负数，为0则为正数。

对最大整型数有以下特征：

Tmax+1 = Tmin=~Tmax

故代码需要让唯一情况为0x7fffffff,并排除0xffffffff。

0x7fffffff+1=0x80000000

1
2
3
4
int isTmax(int x)
{
	return !(x+(x+1))|!(x+1);
}

判断所有奇数位是否均为1

这需要用到0xAAAAAAAA来进行判断。

image-20220204145219988

先构造该数

1
2
3
4
5
6
int allOddBits(int x)
{
    int i=0xAA+(0xAA<<8);#左移8位，构造0xAAAA
    i += i<<16;#构造0xAAAAAAAA
    return !((i&x)^i);
}

不用-，求-x的值

这个很简单

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

判断是否是0~9的ASCII码值

首先确定范围是0x30~0x39。

从二进制原码上下手会比较好理解。0x30~0x39，只用考虑低四位。(9为0x1001)

但还有一个问题0x300x39的第58位为0011.

所以还得先判断第5~8位是否为0011，再来判断第四位。

1
2
3
4
5
int isAsciiiDigit(int x)
{
    int z=0xf,y=3,p=6;
    return !(((x>>4)^y)|(x&z)+p)>>4);
}

((x>>4)^y)用于判断第58位是否为0011，先将58位变为1~4位，再异或3，返回0则对。

(x&z)+p)>>4用于判断1~4位：首先我们知道，十六进制数位0123456789ABCDEF，以9来考虑，加上6后是有进位的，故上限可加6然后再左移看进位与否判断，下限自然不用了，毕竟开头的是0不是1就行。

使用位级运算实现C语言中的 x?y:z三目运算符。

首先了解一下何为三目运算符

1
2
3
4
int conditional(int x,int y,int z)
{
    return ((x>>31|((~x+1)>>31))&y)|(~x>>31|(~x+1)>>31))&z;
}

有一种特殊情况：当条件为假的时候，而当结果1为零时，返回结果2。

故总共有三种情况。

条件用(x>>31|((~x+1)>>31))判断。后续根据相应结果做最后运算。

使用位级运算符实现<=

1
2
3
4
int isLessOrEqual(int x,int y)
{
    return !!((x>>31)&(~y>>31))|(!!((x+(~y+1))>>31)&~((~x>>31)&y>>31))|!(x+(~y+1));
}

我们并不知道两个数正负，所以先对正负，也就是符号位进行判断（四种情况）：都为正或负，一正一负。

那么挨个实现即可，难度不大。(>>31是为了对符号位进行比较。)

(一个小技巧：!!x可以把非零数变为1，0变为0。)

计算!x却不用!符号

！：称为逻辑非运算符。用来逆转操作数的逻辑状态。如果条件为真则逻辑非运算符将使其为假。

简而言之，使结果呈相反状态。

1
2
3
4
int logicalNeg(int x)
{
    return ~(x>>31)&(((~x+1)>>31)+1);
}

可以从符号位上下手，布尔代数只有0和1。符号位也是只有0和1。

将其本身的符号位与上其相反数的符号位加1（若ｘ为0，则加1后为0反之为1.）最后取反。

计算一个数用补码表示最少需要几位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int howManyBits(int x)
{
    int b16,b8,b4,b2,b1,b0;
    int sign=x>>31,ret=0;
    x = (sign&~x)|(~sign&x);
    ret=1+!!x;
    b16=!!(x>>16)<<4;
    x=x>>16;
    b8=!!(x>>8)<<3;
    x=x>>b8;
    b4=!!(x>>4)<<2;
    x=x>>b4;
    b2=!!(x>>2)<<1;
    x=x>>2;
    b1=!!(x>>1);
    return b16+b8+b4+b2+b1+ret;
}

这个题就像一排座位，判断上面有多少是坐了人的。（但是不能直接看见）

所以先将整体一分为二，拆为高低16位，先判断高16位的值是否为0，不是的话将高16位提取出，再一分为二，高8位，低8位。同样的方法判断；若高16位为0，则采用如上相同方法判断。

当然，还得先看符号位是啥，前面说过，!!x可以将非零数变为1，0变为0。

求浮点数(u)f*2

1
2
3
4
5
6
7
8
9
10
unsigned floatScale2(unsigned uf) {
    if((uf>=0x7f800000 && uf<=0x7fffffff)||(uf>=0xff800000 && uf<=0xffffffff) || uf==0 || uf==0x80000000)
        return uf;  //当uf=NAN或无穷或0的时候，返回它本身
    else if(uf>0x80000000 && uf<=0x807fffff)
        return ((uf<<1)+0x80000000);  // uf为负的非规格化数  
    else if(uf>0 && uf<=0x007fffff)
        return uf<<1;  //uf为正的非规格化数
    else
        return (uf+(1<<23));  // uf为规格化数
}

关于浮点数，有必要知道阶阶码,规格化

还是得先排除NaN，无穷大/小，0这些情况。所以当浮点数为无穷，0或NAN时，返回本身，阶码全为1

再就是规格化数：阶码加一和非规格化数（非规格化数有正负之分，且阶码全为0：正数左移一位，负数补最高位一个1）。

将浮点型转换为整型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}

首先考虑特殊情况：如果原浮点值为0则返回0；如果真实指数大于31（frac部分是大于等于1的，1<<31位会覆盖符号位），返回规定的溢出值0x80000000u**；如果 [公式] （1右移x位,x>0，结果为0）则返回0。剩下的情况：首先把小数部分（23位）转化为整数（和23比较），然后判断是否溢出：如果和原符号相同则直接返回，否则如果结果为负（原来为正）则溢出返回越界指定值0x80000000u**，否则原来为负，结果为正，则需要返回其补码（相反数)。

求2的x次方

1
2
3
4
5
6
7
8
9
10
11
12
13
unsigned floatPower2(int x) {
      if(x>=0x80000000 && x<0xffffff6a)
          return 0;            //  表示的数小于32位float表示的最小值
      else if(x>=0xffffff6a && x<=0xffffff81)
          return 1<<(149+x);   //  表示的数是非规格化数
      else if(x>=0x00000080 && x<0x80000000)
          return 0x7f800000;   //  表示的数大于32位浮点数表示的最大值
      else
      {   //  规格化情况
          unsigned y=x+127;
          return y<<23;
      }
}

首先分析什么时候返回0，也就是当小于float最小表示的数的时候返回0。因为2^x必然是大于0的，float表达的最小数就是0x1，此时为2的-126次方乘以2的-23次方，等于2的-149次方，所以第一种情况就是x大于-149，则返回0。
  然后再分析什么时候返回正无穷，float表示的最大值是0x7f7fffff，即当x大于等于128（阶码全为1）的时候表示无穷，返回正无穷。
  然后分析，2^x能表示当float阶码为0，尾数只有一位为1的情况和阶码为0x1，尾数为0的情况即-149<=x<=-126。这个时候的float的表示应该是除了尾数有一位为1，其他位都是0。可以计算出尾数为1的那一位距离尾数最低位的位数m，然后将1<<m即可。这里的m应该用“23-（-x-126）”即m=149+x。所以是1<<(149+x)。
  然后就是规格化数的一种情况，这种情况最简单，就是阶码位加一就可以了。