前言
文章一
文章二
文章三
相比于上面这些参考文章，我增加了更多的个人理解在其中，可以互为参考。
函数分析
bitXor函数
函数要求：
| 函数名 | bitXor |
|---|---|
| 参数 | int , int |
| 功能实现 | x^y |
| 要求 | 只能使用 ~ 和 | 运算符，将结果返回。 |
实现分析：
异或的最初形态是 x ⊕ y = ( x ∧ ! y ) ∨ ( ! x ∧ y ) x\oplus y=(x\land !y)\lor(!x\land y) x⊕y=(x∧!y)∨(!x∧y)，因为只允许使用或，所以使用Demorgan定律将与转化为非和或。
函数实现：文章来源地址https://www.toymoban.com/news/detail-723567.html
int bitXor(int x, int y) {
// 代码实现
return ~(~(~x & y) & ~(x & ~y));
}
getByte函数
实现分析：
因为要将x逐字节位移，所以要通过(n<<3)实现将一次位移放大到一字节的宽度。最后用0xff做低8位（1Byte）掩码。
函数实现：
int getByte(int x, int n) {
return (x>>(n<<3))&0xff;
}
logicalShift函数
实现分析：
对于int型这种有符号数，右移是算术右移。
要实现逻辑右移，可以在算数右移的基础上，增加一个掩码，比如右移n位，那就是n个0以及32-n个1
具体的构造方法，是先把1左移31位，变成0x80000000，然后取反变成0x7fffffff，对这个数右移n位，前面总共会有n+1个0，此时再左移1位，前面变成n个0，最后一位变为0，所以使用或运算将最后一位变成1.
其实我还用过另一个思路：mask=((~(1<<31)<<1)|1)>>n;
这个思路失败了，由此可以得出，C语言中常数是以补码形式存在的，进行算术右移。
函数实现：
int logicalShift(int x, int n) {
int mask;
x>>=n;
mask=(((~(1<<31))>>n)<<1)|1;
return x&mask;
}
bitCount函数
实现分析：
本题采取二分法进行加和，具体思路如下：
从最开始，构造32位的0x55555555掩码：
mask_1=0x55|(0x55<<8);
mask_1=mask_1|(mask_1<<16);//构造32位mask
此掩码经过x=(x&mask_1)+((x>>1)&mask_1);的操作，可以将2bit中的1的个数变成2bit形式的二进制数字。
上一步是从1到2，同理，还可以从2到4，使用0011为一个单位，构造0x33333333掩码，同样经过 x=(x&mask_2)+((x>>2)&mask_2);的操作，就可以实现将4bit中的1的个数转化为4bit的二进制数字。
由此递推，4到8，8到16，16到32，都是如此。
需要指出的是，从4到8开始，就不需要分开进行掩码操作了，因为随着二进制位的增加，其可以表达的数字已经远超出二进制位的总和，即高位已经不可能是1了，所以掩码不会影响到数字。
函数实现：
int bitCount(int x) {
int mask_1,mask_2,mask_4,mask_8,mask_16;
mask_1=0x55|(0x55<<8);
mask_1=mask_1|(mask_1<<16);//构造32位mask
mask_2=0x33|(0x33<<8);
mask_2=mask_2|(mask_2<<16);
mask_4=0x0f|(0x0f<<8);
mask_4=mask_4|(mask_4<<16);
mask_8=0xff|(0xff<<16);
mask_16=0xff|(0xff<<8);//不需要进行额外的移位了
x=(x&mask_1)+((x>>1)&mask_1);
x=(x&mask_2)+((x>>2)&mask_2);
//到这里不可能超出了，所以直接相加就好
x=(x+(x>>4))&mask_4;
x=(x+(x>>8))&mask_8;
x=(x+(x>>16))&mask_16;
return x;
}
conditional函数
实现分析：
实现选择，需要构造一个全是0或者全是1的掩码，然后通过按位异或操作来进行选取。
构造时，先使用二连！！，将一个数字转换成32位的bool格式，左移31位右移31位，如果是非零，那就全是1，0就全是0.
函数实现：
int conditional(int x, int y, int z) {
int mask=((!!x)<<31)>>31;//~(!!x)+1;
return (mask&y)|(~mask&z);
}
tmin函数
实现分析：
在补码的世界中，最小的补码是-1：0xffffffff，随着绝对值逐渐增大，后面代表数字的部分逐渐递减，绝对值最大的负数（最小的负数）就是除符号位以外全是0的数。
给出最低补码，即构造0x80000000；
函数实现：
int tmin(void) {
return 1<<31;
}
- fitBits函数
实现分析：
代码很直观，就是先确定移位数量，然后左移再右移，比较前后是否发生变化。关键在于，为什么左移32-n右移32-n后如果两个32位数不相等就说明不可以呢？
原因在于，超出以后会发生两种异常：符号位是否能保留，以及高位有效位是否能保留。
先说符号位保留问题：正数符号位为0，比如n=3，正数3在补码中的低3位就是011，2就是010，1就是001，0就是000，有没有符号位一定是0，一旦超出上限，比如变成4，就会变成0100的形式，符号位被破坏，那么移位32-n后就会导致高位补1，完全就不一样了。
那继续增加呢？符号位是会回来，但是你的高位有效位没了。
5就是0101，6就是0110，7就是0111，8就是01000，对于8来说，左移32-n就会变成0，右移回来第三位虽然是0，但是但是已经丢失了高位信息了。又比如10是01010，最后低4位会变成0010，不再是原来的32位数了。
总的来说，从32位角度来看，如果想表示的数超出了低n位表示的能力，左移32-n位后再右移回来，无非两个结果：高位全变成1或者丢失超出的部分。
函数实现：
int fitsBits(int x, int n) {
int shift_number=32+(~n+1);//32-n
int x_shifted=x<<shift_number>>shift_number;
return !(x_shifted^x);
}
dividePower2函数
实现分析：
补码 2 k 2^k 2k除法，如果是正数，直接移k位，但是负数会出现向下取整的情况，为了实现趋零截断，需要对负数加一个特定的偏置，即 + 2 w − 1 +2^w-1 +2w−1
判断正数和负数，可以通过类似于前面conditional的全0/全1mask实现，本次直接用符号位构造mask。
如果是正数，mask就全是0，bias不生效，如果是复数，mask都是1，bias生效。
函数实现：
int dividePower2(int x, int n) {
int mask=x>>31;/*00000000 or 1111111*/
int bias=mask&((1<<n)+(~0));
return (x+bias)>>n;
}
negate函数
实现分析：
如代码，不仅是正转负是按位取反+1，负转正也是这样，很神奇，实际上有离散数学作为理论支持，这是必然结果。
函数实现：
int negate(int x) {
return ~x+1;
}
howManyBits函数
实现分析：
补码的最高表示位前面的所有数字应该都是全0(正数)或是全1(负数)。
将原数与左移一位后的数字异或则最高的不同的那个位置为1，我们只需要找到这个最高的不同位即可。这个信息储存在temp中。
之后就是用二分法去测试最高位在哪里，比如bit_16=!!(temp>>16)<<4;结果不为0，说明最高非零位至少在16位以后，我们进一步将高16位留下观察。反之，如果为0，说明最高位介于0和16之间，于是不做处理，等的后面8位处理进行判断。
由此，通过二分法得到若干shift值，有的是16，8这类数，有的就是0，最后加起来，给一个+1的偏置就可以得到需要的位数。
函数实现：
int howManyBits(int x) {
int temp=x^(x<<1);
int bit_16,bit_8,bit_4,bit_2,bit_1;
bit_16=!!(temp>>16)<<4;
temp=temp>>bit_16;
bit_8=!!(temp>>8)<<3;
temp=temp>>bit_8;
bit_4=!!(temp>>4)<<2;
temp=temp>>bit_4;
bit_2=!!(temp>>2)<<1;
temp=temp>>bit_2;
bit_1=!!(temp>>1);//no need to shift back
return bit_1+bit_2+bit_4+bit_8+bit_16+1;//1 offset
}
isLessOrEqual函数
实现分析：
比较大小可以转换为作差。但是如果是异号，就可能出现溢出，所以异号要单独拿出来分析，同号就可以直接作差。
最后将两种情况合并到return式子里，用或综合返回。
函数实现：
int isLessOrEqual(int x, int y) {
int sign_x=(x>>31)&1;
int sign_y=(y>>31)&1;
int sign_y_x=((y+(~x+1))>>31)&1;
return (!(sign_x^sign_y)&!sign_y_x)|((sign_x^sign_y)&sign_x);//
}
intLog2函数
实现分析：
x是大于0的，所以是原码形式，是简化版的howManyBits。
函数实现：
int intLog2(int x) {
int temp=x;
int bit_16,bit_8,bit_4,bit_2,bit_1;
bit_16=!!(temp>>16)<<4;
temp=temp>>bit_16;
bit_8=!!(temp>>8)<<3;
temp=temp>>bit_8;
bit_4=!!(temp>>4)<<2;
temp=temp>>bit_4;
bit_2=!!(temp>>2)<<1;
temp=temp>>bit_2;
bit_1=!!(temp>>1);//no need to shift ba
return bit_1+bit_2+bit_4+bit_8+bit_16;
}
floatAbsVal函数
实现分析：
浮点数看这篇：
浮点数基础E=0xffff且M=0为Inf，E=0xffff且M！=0为Nan：Nan，Inf判断
首先通过掩码，抓取8位阶码，如果是特殊值，就直接返回，否则把符号位置0就可以。
函数实现：
unsigned floatAbsVal(unsigned uf) {
if((uf&0x7f800000)>>23==255 && uf<<9)
return uf;//uf<<9!=0
return uf&0x7fffffff;
}
floatScale1d2函数
实现分析：
首先取出符号位和阶码。先判断是否是特殊值，如果不是就进行下一步规范化判断。
规范化的指数至少为2，否则就是exp==1和0的时候，这个时候会考虑舍入。
如果E>1，说明是规范化值，直接用掩码把x的阶码屏蔽，使用移位后的阶码覆盖即可。
反之，说明是不规范的极小值，考虑舍入。
floatAbsVal会考虑是否规范化。关于非规范化：规范化参考
函数实现：
unsigned floatScale1d2(unsigned uf) {
int E = (uf&0x7f800000) >> 23;
int S = uf&0x80000000;//sign
//int S = uf&0x80000000;
if((uf&0x7fffffff) >= 0x7f800000) //Nan Inf
return uf;
if(E>1) //regular
return (uf&0x807fffff)|(--E)<<23;
else //irregular E==1 E==0
{
if((uf&0x3)==0x3)
uf+=0x2;
return ((uf>>1)&0x007fffff)|S;
}
}
floatFloat2Int函数
实现分析：
把浮点数转int，首先取出符号位和阶码（将移码转换为真实数），以及尾数。
如果E太大，就会溢出，如果E小于0，说明真实值介于-1和1之间，趋零截断就会变成0.
如果正常，就要令尾数与科学计数法的宽度统一，如果E更大，就把尾数左移，E小就把尾数右移。
最后根据符号位返回正负值。文章来源：https://www.toymoban.com/news/detail-723567.html
函数实现：
int floatFloat2Int(unsigned uf) {
int sign=uf>>31;//unsigned logical shift
int E=((uf&0x7f800000)>>23)-127;//8-bits exp
int frac=(uf&0x007fffff)|0x00800000;//frac and add the 1(regular)
if(E>=32)
{
return 0x80000000;//overflow up
}
else if(E<0)
{
return 0;//between -1,1
}
else
{
if(E>=23)//more than frac, pow 2
{
frac<<=(E-23);
}
else//less than frac,pow
{
frac>>=(23-E);
}
return sign?-frac:frac;
}
}
到了这里，关于CSapp-DataLab——深入理解函数实现原理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
