《csapp》信息的表示和处理

阅读深入理解计算机系统，书中的很多实践的练习值得尝试。

show bytes

void show_bytes(byte_pointer start, size_t len)
//这里的len表示从start开始
//包括start，例如ab ed 这样，每2个数字为一个单位
//总共有几个单位？

show_bytes的使用，具体能够打印类型为short、long和double的c语言对象的字节表示：
具体实现如下：

/* $begin show-bytes */
#include <stdio.h>
/* $end show-bytes */
#include <stdlib.h>
#include <string.h>
#include <iostream>

/* $begin show-bytes */

using namespace std;

typedef unsigned char *byte_pointer;
//unsigned char * 显示一位

void show_bytes(byte_pointer start, size_t len) {
    size_t i;
    //int k=0;
    for (i = 0; i < len; i++)
	     printf(" %.2x", start[i]);    //line:data:show_bytes_printf
       //buf[k++]=start[i];
    printf("\n");
}


void show_int(int x) {
    show_bytes((byte_pointer) &x, sizeof(int)); //line:data:show_bytes_amp1
}

void show_float(float x) {
    show_bytes((byte_pointer) &x, sizeof(float)); //line:data:show_bytes_amp2
}

void show_pointer(void *x) {
    show_bytes((byte_pointer) &x, sizeof(void *)); //line:data:show_bytes_amp3
}

void show_short(short x){
    show_bytes((byte_pointer) &x, sizeof(short));
}

void show_long(long x){
    show_bytes((byte_pointer) &x, sizeof(long));
}

void show_double(double x){
    show_bytes((byte_pointer) &x, sizeof(double));
}

/* $end show-bytes */


/* $begin test-show-bytes */
void test_show_bytes(int val) {
    int ival = val;
    float fval = (float) ival;
    int *pval = &ival;
    show_int(ival);
    show_float(fval);
    show_pointer(pval);
}
/* $end test-show-bytes */

void simple_show_a() {
/* $begin simple-show-a */
int val = 0x87654321;
byte_pointer valp = (byte_pointer) &val;
show_bytes(valp, 1); /* A. */
show_bytes(valp, 2); /* B. */
show_bytes(valp, 3); /* C. */
show_bytes(valp, 4);
/* $end simple-show-a */
}

void simple_show_b() {
/* $begin simple-show-b */
int val = 0x12345678;
byte_pointer valp = (byte_pointer) &val;
show_bytes(valp, 1); /* A. */
show_bytes(valp, 2); /* B. */
show_bytes(valp, 3); /* C. */
/* $end simple-show-b */
}

void float_eg() {
  int x = 3490593;
  float f = (float) x;
  printf("For x = %d\n", x);
  show_int(x);
  show_float(f);

  x = 3510593;
  f = (float) x;
  printf("For x = %d\n", x);
  show_int(x);
  show_float(f);

}

void string_ueg() {
/* $begin show-ustring */
const char *s = "ABCDEF";
show_bytes((byte_pointer) s, strlen(s));
/* $end show-ustring */
}

void string_leg() {
/* $begin show-lstring */
const char *s = "abcdef";
show_bytes((byte_pointer) s, strlen(s));
/* $end show-lstring */
}

void show_twocomp()
{
/* $begin show-twocomp */
    short x = 12345;
    short mx = -x;

    show_bytes((byte_pointer) &x, sizeof(short));
    show_bytes((byte_pointer) &mx, sizeof(short));
/* $end show-twocomp */
}

//check is_litter_endian
bool is_litter_endian()
{
    int a = 0x123456;
    if( *((char*)&a) == 0x56)
        return 1;
    else
        return 0;
}

int main(int argc, char *argv[])
{
    int val = 12345;


    if (argc > 1) {
	       if (argc > 1) {
	          val = strtol(argv[1], NULL, 0);
	       }
	       printf("calling test_show_bytes\n");
	       test_show_bytes(val);
    }
    else {
	           printf("calling show_twocomp\n");
	           show_twocomp();
	           printf("Calling simple_show_a\n");
	           simple_show_a();
	           printf("Calling simple_show_b\n");
	           simple_show_b();
	           printf("Calling float_eg\n");
	           float_eg();
	           printf("Calling string_ueg\n");
	           string_ueg();
	           printf("Calling string_leg\n");
	           string_leg();


             //exercise 2.59
             if(is_litter_endian())
                cout<<"litter endian"<<endl;
             else
                cout<<"big endian"<<endl;

    }
    return 0;
}

结果见图：

可以发现，我的电脑是小端法机器，浮点数的编码方法，和二进制的编码方法不太一样，浮点数的编码方法，我在
浮点数编码方法
最后一个例子有详细说明。

其中值得一提的是，取最低有效字节的方法：

x & 0xFF  //取出x的最低有效字节
y & ~0xFF  //取出y的最低有效字节
((x & 0xff) | (y & ~0xff))  //能够实现x的最低有效字节和
//y除了最低有效字节外的其他字节合并

#include <stdio.h>

//注意：不要打0x作为输入

int main()
{
    int x,y;
    int res;
    printf("Please int x(H) and y(H): ");
    scanf("%x%x",&x,&y);
    res = ((x & 0x000000ff) | (y & 0xffffff00));
    printf("The result is %.8x(H)\n",res);
}

类似的方法，常常用于处理某一个字节替换问题：

结论见图：

#include <stdio.h>
#include <iostream>

using namespace std;

unsigned replace_byte(unsigned x, unsigned char b, int i)
{
    return (x & ~(0xff<<(i<<3))) | (b<<(i<<3));
}

int main()
{
    printf("0x%x\n",replace_byte(0x12345678,0xab,2));
    printf("0x%x\n",replace_byte(0x12345678,0xab,0));
}

````

## 位级整数编码原则 ##

### 算术右移和逻辑右移的关系 ###

算术右移和逻辑右移是不一样的
算术右移需要考虑符号位，右移一位，若符号位为1，在左边补1
逻辑右移，补0就可以

这里以-1为例，-1算术右移一位，所产生的二进制码代表的数值不变；而逻辑右移则会使最高位为0，变成（1<<63）-1，最大值。

```bash
#include <stdio.h>
#include <iostream>

using namespace std;

int judge_if_all_1(int x)
{
    return !(~x);
}

int judge_if_all_0(int x)
{
    return !x;
}

int judge_low_is_0(int x)
{
    //最低有效字节：x & 0xff
    return !(x & 0xff);
}

int judge_low_is_1(int x)
{
    return (x & 0xff);
}

int judge_high_is_0(int x)
{
    //除最高字节以外的位数
    //howmanybit=(sizeof(int)-1)<<3
    // a<<3表示a*8，因为一位有8个比特

    //右移howmanybit位
    return !( (x>>((sizeof(x)-1)<<3)) );
}

int main()
{
    int a;
    scanf("%x",&a);

    cout<<judge_low_is_0(a)<<endl;
    cout<<judge_low_is_1(a)<<endl;
    cout<<judge_high_is_0(a)<<endl;
    cout<<judge_if_all_0(a)<<endl;
    cout<<judge_if_all_1(a)<<endl;
}

#include <stdio.h>
#include <iostream>
using namespace std;

//int_shifts_are_arithmetic()
//对int类型数使用算术右移返回1，否则返回0；
//显然，只需考虑负数即可（非负数算术右移与逻辑右移相同）。
//显这里以-这里以-这里以-这里以-1为例，
//-1算术右移一位，所产生的二进制码代表的数值不变；
//-而逻辑右移则会使最高位为0，变成（1<<31）-1，最大值。

int int_shifts_are_arithmetic()
{
    printf("%x %x\n", ((-1)>>1),-1);
    return ((-1)>>1)==-1;
}

int main()
{
    cout<<int_shifts_are_arithmetic()<<endl;
    return 0;
}

算术右移有一个特点，移几位，补几个最高位
举一个例子
$[x_{w-1},x_{w-1}...x_{w-1},x_{w-2}...x_{k}]$

算术右移和逻辑右移相互表示

这里先提一点：算术右移和逻辑右移，其中涉及到有符号数和无符号数的相互转换，这个问题比较重要，公式如下：

$T2U_w(x)= \begin{cases} x+2^w& \text{x<0}\\ x& \text{x>=0} \end{cases}$

一个无符号数，转换成对应的有符号数，依据是：补码原则

$U2T_w(x)= \begin{cases} u& \text{u<TMaxw}\\ u-2^w& \text{u>TMaxw} \end{cases}$

其中 $TMax_w$ 表示符号类型如 $int$ 最大的位数

基于以上公式，我们发现从 $int$ 类型向 $unsigned$ 类型转换的时候，只有x为负数，逻辑右移和算术右移才能够体现出区别，我们这里仅研究 $x<0$ 的情况

1 2	sra()表示用逻辑右移完成算术右移 srl()表示用算术右移完成逻辑右移

原理表示如下(仅仅研究 $x<0$ 情况)：

int sra(int x,int k)
{
    //Perform shift logically
    int xsrl = (unsigned)x >> k; //转换成为无符号数
    int w = (sizeof(int))<<3;
    returnx xsrl |= (-1 << (w-k));
}

unsigned srl(unsigned x, int k)
{
    //Perform shift arithmetically
    unsigned xsra = (int) x >> k;
    int w = (sizeof(int)) << 3;
    return xsra &= ~(-1 << (w-k));
}

判断奇数位是否为1

#include <stdio.h>
#include <iostream>


bool any_odd_one(unsigned x)
{
    //将所有的奇数位全部置为0，偶数位不变
    //考虑&...01010101
    //&0x55555555(32bits)
    //若奇数位有1，则提取奇数位，结果不为0
    return 0!=(x&0x55555555);
}

int main()
{
    printf("%d\n",any_odd_one(0x5) );
    printf("%d\n",any_odd_one(0x25) );
    printf("%d\n",any_odd_one(0x7) );
    return 0;
}

二分法位运算：有多少个位包含1

注意：^异或运算，相当于无进位的加法，可以消除位中的1

有两种方法：

#include <stdio.h>
#include <iostream>

using namespace std;

//不用位运算的方法
int even_ones_without_bit(unsigned x)
{
    int result = 0;
    for(int i=0;i<(sizeof(int)<<3);i++)
    {
        int y = x>>i;
        y=y&1;
        if(y)
          result++;
    }
    if(result%2)
        return 1;
    else
        return 0;
}

int odd_ones(unsigned x)
{
    //用异或运算消除偶数
    x ^= (x>>16);
    x ^= (x>>8);
    x ^= (x>>4);
    x ^= (x>>2);
    x ^= (x>>1);
    return (x&1);
}
int main()
{
    int x;
    scanf("%x",&x);
    int res=odd_ones(x);
    printf("%d\n",res);
}

二分法运算：只保留最高位的1

函数功能如下：

1	0xFF00-->0x8000 0x6600-->0x4000

实现方法：

#include <stdio.h>

int leftmost_one(unsigned x)
{
    x |= (x>>1);
    x |= (x>>2);
    x |= (x>>4);
    x |= (x>>8);
    x |= (x>>16);

    x &= ~(x>>1);
    return x;
}

int main()
{
    int x;
    scanf("%x",&x);
    int res=leftmost_one(x);
    printf("%x\n",res);
}

移位运算需要注意的

可以知道：移位运算，移位的量，区间是 $(0,w-1)$
通过移位运算，使得在32位的机器上可以运行

这里说一下移位运算的溢出：
注意第一位是符号位

0000 -- 0
0001 -- 1
0010 -- 2
...
0111 -- 7
1000 -- -8

以32位机器举例，int的最大值位 $2^{32-1}=2147483648$
int型，若为正数，可以表示的最大的数为

0111 1111 1111 1111 1111 1111 1111 1111
//最高位是符号位，为0,值为2147483647
//加上1之后
1000 0000 0000 0000 0000 0000 0000 0000
//值为负数，-2147483648

判断一个机器是否为32位，只要用上述方法可以判断。
具体实现如下：

#include <stdio.h>

bool int_size_is_32()
{
    int set_msb = ~(1<<31);
    return (set_msb+1<0);
}

int main()
{
    bool res = int_size_is_32();
    printf("%d\n",res);
}

位级运算完成置位

lower_one_mask

使用位级运算完成置位的过程，通常需要将二进制转换成如下形式：

00000 111111
//即前几个数都为0，后几个数都为1的形式

//lower_one_mask函数的实现
//0xFFFFFFFF>>(32-n)
//00...011...1形式，最后就有n位为1

#include <stdio.h>

int lower_one_mask(int n)
{
    unsigned mark = 0xffffffff;
    mark = mark >> (32-n);
    return mark;
}

int main()
{
    int n;
    scanf("%d",&n);
    int res = lower_one_mask(n);
    printf("%x",res);
}

旋转：rotate_left

1
2
3

//取最高m位和最低n位的方法：
x>>(32-m)
x<<(32-n)

#include <stdio.h>

unsigned rotate_left(unsigned x, int n)
{
    if(n==0)
        return x;
    else
    {
        unsigned low = x<<n;
        unsigned high = x>>(32-n);
        return low | high;
    }
}

int main()
{
    int x,n;
    scanf("%x%d",&x,&n);
    int res=rotate_left(x,n);
    printf("%x\n",res);
}

补码运算的原理

1、补码中取反，反码的求法。

反码，以下讨论不包括符号位
010110的反码
111111-010110 = 101001
这里不讨论符号位

2、补码原理：

假设计算机字长为n，源码、反码和补码的关系如下：

原码：

[+1]_源 = 0000 0001
[-1]_源 = 1000 0001
其中第一位为符号位
取值范围
[1111 1111, 01111 1111]
-->[-127,127]

从公式上看，当 $x>0$ 时，很显然x的源码就是x自身
$x<0$ 时候，除去最高位外，剩下的位数的值等于 $|x|=-x$ ，
再加上最高位的1，即加上 $2^{n-1}$ ，最后的值为 $2^{n-1}-x$

反码：

正数反码不变
负数反码，符号位不变，各位取反
[+1]=[0000 0001]_源=[0000 0001]_反
[-1]=[1000 0001]_源=[1111 1110]_反

可以用[1000 0000]表示-128

负数的反码，除了符号位，各位取反，其实是

1 2	仅看数值位(n-1) 11...1 - xxxxx

数值位取反即为 $2^{(n-1)}-1-(-x)=2^{(n-1)}-1+x$
解释：

1	0xffffffff-(-x)

最高位，即符号位为 $2^{n-1}$ ，数值位全部为1，表示为 $2^{n-1}-1$
数值位取反 $2^{n-1}-1-(-x)$

最后我们再加上符号位 $2^{n-1}$
所以答案为 $2^{n-1}+(2^{n-1}-1+x)=2^n+x-1$

补码：
为什么是取反码加一？
假设我们有正数 0000 0000 0000 1111，我们如何表示其相反数呢？一般我们的思路是，找一个数，跟它相加的结果等于0，但是我们发现，要找出一个与它相加后结果等于0的数还是要略加思考一下的（因为要计算进位），所以，为何不找出一个与它相加后结果是1111 1111 1111 1111的数，然后该数+1即是我们所要的答案啦。

A+(相加等于全部是11111的数)+1 = 0
所以A的相反数等于：求出与A相加全部是11…1的数，然后加1
于是就推出：
补码等于反码+1

缩进后再暴露最高位的方法，来看看补码是否等于原来的数

#include <stdio.h>

//一个数能够用二进制补码表示
//可以知道这个数为正数
int fits_bits(int x, int n)
{
    //对最高位进行缩进表示
    int bias = (sizeof(int) << 3)-n;
    return ((x<<bias)>>bias)==x;
}

int main()
{
    int x,n;
    scanf("%d%d",&x,&n);
    int res = fits_bits(x,n);
    printf("%d\n",res);
}

xbyte

#include <stdio.h>

typedef unsigned packed_t;

int xbyte(packed_t word, int bytenum)
{
    int move_to_high = (3-bytenum)<<3;
    //将要处理的字节移动到首字节
    unsigned mask = (0xff) << 24;
    //第一个字节设置掩码

    int res = (word << move_to_high) & mask;
    res = res >> 24;
    return res;

}

int main()
{
    int hex,n;
    scanf("%x%d",&hex,&n);
    printf("%x\n",xbyte(hex,n));
    return 0;
}

特别注意的地方：

if(maxbytes-sizeof(val)>=0)
{
    //
}

条件是恒正的，因为结果是无符号数，无符号数大于0是肯定的
正确写法：
if(maxbytes>=sizeof(val))

位运算实现饱和加法

饱和加法，在正溢出的时候，返回 $TMax$ 。

先来看正常情况下的加法

1
2
3

两个正数加法溢出
011...1 + 1 = 100...0
最后sum的符号位被置为1

所以最后的 $TMax$ 会是一个绝对值比较大的负数

这里我们要返回 $TMax$

#include <stdio.h>
#include <iostream>

using namespace std;

int saturating_add(int x, int y)
{
    int mask = INT_MIN;
    //INT_MIN所有位均为1，构成了掩码

    int sum = x+y;
    int w = sizeof(int)<<3;

    //负溢出的时候，获取最小值
    //负溢出的情况，原来x,y的第一位为1
    //即有(x & mask) (y & mask)
    //注意&&运算，() && ()，
    //注意&&运算，连接两个非0数，
    //结果也只为0或者1
    //(x & mask) && (y & mask) && !(sum & mask)
    //在负溢出的时候为1，1<<(w-1)>>(w-1)
    //会把所有的位置为1，因为有符号数要补上符号位
    //最后 & INT_MIN，保证INT_MIN正确输出

    int tmin = ( ((x&mask) && (y&mask) && !(sum&mask)) <<(w-1)>>(w-1) ) & INT_MIN;
    //这一步，关键是如果前半部分的值为1，说明溢出，溢出返回的是INT_MIN
    //不用if语句，我们要得到INT_MIN，需要INT_MIN & 11...1
    //前半部分的值为1，要让所有的位值都是1，需要<<(w-1)>>(w-1)
    //算术右移，前面是带上符号位的

    int tmax = ( ((~x&mask) && (~y&mask) && (sum&mask)) <<(w-1)>>(w-1) ) & INT_MAX;
    return (sum& ~(!(tmin | tmax))) | tmin | tmax;

    //这里重点说明一下没有溢出的情况：
    //[tmin,tmax) 其中tmin=11...1 tmax=011...1
    //tmin|tmax = 11...1，这样的目的是把符号位的1也参与进运算中
    //--> !(tmin | tmax)=00...0 --> ~(!(tmin|tmax))=11...1
    //sum & res = sum，符号位也原封不动地包含下来
}

void show_saturating_add(int x,int y)
{
    printf("satuarating_add(0x%08x,0x%08x)=0x%08x-->%d\n",x,y,saturating_add(x,y),saturating_add(x,y));
    printf("%d+%d=%d\n",x,y,x+y);
    printf("\n");
}
int main()
{
    int x,y;
    scanf("%x%x",&x,&y);
    show_saturating_add(x,y);
}

同样，怎么判断减法是否溢出呢？
减法的溢出会导致一个非常大的正数，用这样的思路来分析。

#include <stdio.h>
#include <iostream>

using namespace std;

//判断x-y溢出，返回1
int tsub_ok(int x,int y)
{
    return ( (y>0 && x-y>x) || (y<0 && x-y<x) );
}

void show_tsub_ovf(int x, int y)
{
    printf("%d-%d=%d %s\n",x,y,x-y,tsub_ok(x,y)?"overflow":"not_overflow");
}

int main()
{
    int x,y;
    scanf("%x%x",&x,&y);
    show_tsub_ovf(x,y);

}

理解定点数的乘法

对于位模式 $x$ ，我们计算 $B2U_w(x)-B2T_w(x)=x_{w-1}(2^{w-1}-(-2^{w-1}))=x_{w-1}2^w$
$B2U_w(T2B_w(x))=T2U_w(x)=x+x_{w-1}2^w$
$x'=x+x_{w-1}2^w$
$y'=y+y_{w-1}2^w$
$(x'\times y')\bmod 2^w =$
$[(x+x_{w-1}2^w)\times (y+y_{w-1}2^w)]\bmod 2^w=[x \times y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}y_{w-1}2^{2w}]\bmod 2^{w}$
$=(x \times y)\bmod2^w$

重点看一下定点数乘法的运算过程

原码乘法

原码乘法的原理可以用下图表示：

原码乘法的计算过程，如上面的公式表示的那样， $w$ 位的两个数相乘，最后得到的数是 $2w$ 位。所以用“部分积寄存器”来表示积的高位，用“乘数寄存器”来表示低位。其中，乘数的位为0或者1，0表示不加任何数，1表示加上被乘数。乘数的位值，仅仅是一个标志，表示是否加上被乘数。被乘数保持不变。

具体的实现方法如下：

值得注意的是，原码乘法执行的是逻辑右移

补码乘法

补码乘法有两种：
第一是校正法，注意在末尾加上 $[-x]_{complement}$

第二种方法是booth方法，booth方法，最后一步不移位，那怎么判断乘积是否结束了呢？
看看在乘数寄存器中，新更新的位数，是不是恰好为 $w$ 位？

位运算与定点数乘法

从上面的分析可以看出，定点数乘法， $w$ 位的两个数相乘，我们可以得到 $2w$ 位。
如果 $x$ 和 $y$ 都是无符号数，并且运行在数据类型是unsigned的 $w$ 位机器上。乘积的低 $w$ 位能够用表达式 $x\times y$ 计算。我们需要一个具有下列原型的函数：

1 2	unsigned unsigned_high_prod(unsigned x,unsigned y); //计算无符号变量x*y的高w位

1 2	int signed_high_prod(int x,int y) //计算x和y采用补码形式的情况下，x*y的高w位

针对上面的公式，我们不妨把计算结果用 $2w$ 来表示
$[(x+x_{w-1}2^w)\times (y+y_{w-1}2^w)]\bmod 2^w=[x \times y+(x_{w-1}y+y_{w-1}x)2^w+x_{w-1}y_{w-1}2^{2w}]\bmod 2^{w}$

将计算结果对 $2^w$ 取余，比如64位的量，可以对 $2^{64}$ 取mod，最后的结果是有64位：
位分别为0,1,2…63

我们要获得高 $32$ 位，可以

unsigned unsigned_high_prod(unsigned x, unsigned y) {
  int sig_x = x >> 31;
  int sig_y = y >> 31;
  int signed_prod = signed_high_prod(x, y);

上述运算实现了：
$[x \times y+(x_{w-1}y+y_{w-1}x)2^w]\bmod 2^{w}$

我们将上述值同时移位 $w$ ，就可以实现
$[(x \times y) (>>w)+(x_{w-1}y+y_{w-1}x)]$

其中 $x_{w-1}$ 就是 $x$ 的符号位

1 2	int sig_x = x >> 31 //获取x_(w-1)的值

其中 $x\times y$ 表示int类型的值，是有符号数。

实现如下：

#include <stdio.h>
#include <inttypes.h>

int signed_high_prod(int x,int y)
{
    int64_t mul = (int64_t) x*y;
    return mul >> 32;
}

unsigned unsigned_high_prod(unsigned x,unsigned y)
{
    int sig_x = x >> 31;
    int sig_y = y >> 31;
    int signed_prod = signed_high_prod(x,y);
    return signed_prod + sig_x * y + sig_y * x;
}

unsigned compared_high_prod(unsigned x,unsigned y)
{
    uint64_t mul = (uint64_t) x*y;
    return mul >> 32;
}

int main()
{
    unsigned x = 0x12345678;
    unsigned y = 0xffffffff;

    int test = unsigned_high_prod(x,y);
    int compared = compared_high_prod(x,y);

    printf("Test: %8x\n",test);
    printf("compared: %8x\n",compared);
}

本章中的其他一些问题(库函数)

calloc.c

1	void* calloc(size_t nmemb, size_t size);

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void* my_calloc(size_t nmemb,size_t size)
{
    if(nmemb==0 || size==0)
        return NULL;
    size_t buf_size = nmemb * size;

    if(nmemb == buf_size/size)
    {
        void* ptr = malloc(buf_size);
        memset(ptr,0,buf_size);
        return ptr;
    }
    return NULL;
}

int main()
{
    void* p;
    p = my_calloc(0x1234,1);
    //一共有0x1234个元素，每个元素1字节
    bool flag = (p!=NULL);
    if(flag)
        printf("Case 1 :Not Null \n");
    else
        printf("Case 1 :Null\n");
    free(p);

    p = my_calloc(SIZE_MAX,2);
    flag = (p==NULL);
    if(flag)
        printf("Case 2 :NULL\n");
    else
        printf("Case 2 :Not Null\n");
}

使用移位运算完成倍乘

//注意乘数为负数的时候怎么表示？
int A(int x)
{
    return x - (x << 3);
    //表示-7x
}

#include <stdio.h>
#include <assert.h>
#include <iostream>

using namespace std;

int A(int x)
{
    return x + (x << 4);
}

int B(int x)
{
    return x - (x << 3);
}

int C(int x)
{
    return (x << 6) - (x << 2);
}

int D(int x)
{
    return (x << 4) - (x << 7);
}

int main()
{
    int x = 0x1;
    printf("Case A: %d\n",A(x));
    printf("Case B: %d\n",B(x));
    printf("Case C: %d\n",C(x));
    printf("Case D: %d\n",D(x));
}

移位运算与舍入问题

仅有乘法或除法

移位运算的舍入问题，遵循以下不等式：
$[x]+[x+\frac{1}{n}]+[x+\frac{2}{n}]+\cdots+[x+\frac{n-1}{n}]=[nx]$

观察上图：
从上表中可以看到，当右移8位的时候，得到-49，这与向零舍入的结果-48并不吻合。
右移总是向下舍入，而对于向零舍入的负数来说是向上舍入，因此为了保证结果吻合，需要进行一个偏置。

bias偏移规律如下：

1
2
3

if(A<0)
    A+=(1<<k)-1;
A>>n;

实现方法：


#include <stdio.h>
#include <assert.h>
#include <limits.h>

int divide_power2(int x, int k)
{
    int is_neg = x & INT_MIN;
    if(is_neg)
        x += (1<<k)-1;
    return x>>k;
}

int mul3div4(int x)
{
    int mul3 = x+(x<<1);
    return divide_power2(mul3,2);
}

int main()
{
    int x;
    scanf("%x",&x);
    printf("%8x\n",divide_power2(x,2));
    printf("%8x\n",x/4);

    int y;
    scanf("%x",&y);

    printf("mul3div4: %x\n",mul3div4(y));
    printf("check: %x\n",3*y/4);
    return 0;
}

乘除法相结合

可以发现我们需要：1、最后 $k$ 位置为0，得到 $low$ 。2、将前面 $w-k$ 位置为0，得到 $high$

//例如：x*(6/8),8=2^3
int low = x & 0x7;
//仅仅保留最后3位，用掩码(111 & x)

int high = x & ~0x7
//掩码获得x的高位，将低3位置为0

//low high分别计算

具体实现：

#include <stdio.h>
#include <limits.h>

int threefourths(int x)
{
    int is_neg = x & INT_MIN;
    int low = x & 0x3;
    int high = x & ~0x3;

    int highd4 = high >> 2;
    int highd4m3 = highd4 + (highd4 << 1);

    int lowm3 = low + (low << 1);
    int bias = (1<<2) - 1;
    if(is_neg)
        lowm3 += bias;
    int lowm3d4 = lowm3 >> 2;

    return lowm3d4 + highd4m3;
}

int main()
{
    int x;
    scanf("%d",&x);

    printf("Test: %d\n",threefourths(x));
    printf("Real: %d\n",x*3/4);
}

位模式的表示方式

$1^{w-k}0^k$
$0^{w-k-j}1^k0^j$

这两种都可以用移位来表示

其中 $0^{w-k-j}1^k0^j$
可以分成三步走：
第一步：获取 $1^{w-k}0^k$ ，通过右移实现
第二步：获取 $0^{w-k}1^k$ ，通过取反实现
第三部：再右移 $j$ 位

实现方法：

#include <stdio.h>
#include <iostream>

int A(int k)
{
    return -1 << k;
    //表示-1重复k次
}

int B(int k,int j)
{
    return (~A(k)) << j;
}

int main()
{
    int x;
    scanf("%d",&x);
    printf("%8x\n",A(x));
    printf("0xFFFFFF00\n");

    printf("%8x\n",B(16,8));
    printf("0x00FFFF00\n");
}

移位运算时候常见的错误

int x = random();
int y = random();

unsigned ux = (unsigned) x;
unsigned uy = (unsigned) y;

补码的非位级表示：对于任意数值

1	-x == ~x+1

从数学上解释这一点：

$-^{t}_{w}x= \begin{cases} TMin_{w}& \text{x=TMinw}\\ -x& \text{x>TMinw} \end{cases}$

$2^w-x=-x$
$-x$ 表示 $x$ 的相反数

$2^w-x-1=-x-1$
$2^w-1-x$ 表示全1的位减去 $x$ ，得到~x

-x=~x+1

成立

(x<y) == (-x>-y)
//wrong! x=INT_MIN
//此时-x = ~x + 1
//~x=011...1
//~x+1 = 100...0 仍然为INT_MIN

1	((x+y)<<4)+y-x == 17y+15x

1
2
3

~x+~y+1=(~x+1)+(~y+1)-1
=-x+-y-1
=-(x+y)-1

1
2
3

(ux-uy)==-(unsigned)(y-x)
--> -(ux-uy)==(unsigned)(y-x)
--> (uy-ux)==(unsigned)(y-x) 显然成立

(x>>2)<<2
--> x& ~(0x3)
--> x + -num(00/01/10/11)
--> (x>>2)<<2 <= x

特殊的二进制无穷串

一些数字的二进制表示是 $0.yyy\cdots$ ，其中 $y$ 是一个 $k$ 位的序列。

n = 0.yyy...
n<<k = y.yyy...=Y+n
--> n<<k-n=Y
--> n = Y/(2^k-1)

应用：
a) 101
   Y=5 k=3 n=5/7
b) 0110
   Y=6 k=4 n=6/15=2/5
c) 010011
   Y=19 k=6 n=19/63

用unsigned测试float型数据的大小

#include <stdio.h>

unsigned f2u(float x)
{
    return *(unsigned*) &x;
}

int float_le(float x,float y)
{
    unsigned ux = f2u(x);
    unsigned uy = f2u(y);

    unsigned sx = ux >> 31;
    unsigned sy = uy >> 31;

    return sx==sy ? (sx==0 ? ux<=uy : ux>=uy) : sx>sy;
}

int main()
{
    int x,y;
    scanf("%d%d",&x,&y);

    int flag = float_le(x,y);
    printf("%d\n",flag);
}

浮点数概论

为什么要引入 $bias$ ？
因为就小数部分而言，比如 $0.1010$ ，计算机是按照二进制编码来计算 $1010=10$ ，无法表示 $2^{-k}$ ，所以我们引入 $bias$ 来表示。
因为没有负值的符号位啊！
$e_{k-1}e_{k-2}\cdots e_{0}$ ，要表示 $(-1)00\cdots 0$ ，只要 $0-2^{k-1}$ ，表示把符号位置为 $-1$ 。
可是为什么bias取 $2^{k-1}-1$ 而不是 $2^{k-1}$
直观上可以这么理解， $00\cdots 0$ 表示0，而 $11\cdots 1 \ 00\cdots0$ 表示无穷大。
所以要除掉那个无穷大的，即为 $2^{k-1}-1$

几个问题：
1、32位ieee 754的阶码偏移量为何用127?而不是128
为了让表示的范围能够对称起来。

当阶码E为全0且尾数M也为全0时，表示的真值x为零，结合符号位S为0或1，有正零和负零之分。
当阶码E为全1且尾数M为全0时，表示的真值x为无穷大，结合符号位S为0或1，也有+∞和-∞之分。
这样在32位浮点数表示中，要除去E，用全0和全1(255)表示零和无穷大的特殊情况，指数的偏移值不选128(10000000)，而是127(01111111)。
对于规格化浮点数，阶码E范围是1~254。

非规格化数 $E=1-bias$
规格化数 $E=e-bias$ ，其中 $e=e_{k-1}e_{k-2}\cdots e_{0}$

对于规格化的值
当 $exp$ 的位模式既不全为0，也不全为1， $E=e-bias$
$e=e_{k-1}e_{k-2}\cdots e_{0}$
$bias=2^{k-1}-1$
很显然 $e_{min}=1$ ，则 $E_{min}=1-2^{k-1}+1=2-2^{k-1}\geq 2-1=1$
同理 $e_{max}=2^k-2$ ，(扣除全部为1的值), $E_{max}=2^k-2-2^{k-1}+1=2^{k-1}-1$

$127=2^{8-1}-1$ ，此时 $k=8$
想一想，如果我们让偏移值为128，而不是127，会是什么样？
$E_{min}=1-2^7=-127$ ，所表示的值为 $2^{-127}=5.877471754111438\times 10^{-39}$
$E_{max}=2^7-2=126$ ，所表示的值 $2^126=8\times 10^{37.9297}$
不对称。

而相反，我们让偏移值为127，可以得到取值范围为：
$E_{min}=1-2^{7}+1=-126$ ， $2^{-126}=1.1754943508222875\times 10^{-38}$
$E_{max}=2^7-1=127$ ， $2^{127}=1.7 \times 10^{38.23080944932561}$

很显然，偏移值为127的时候上下对称。

非规格化数的平滑处理
为什么要将 $E$ 定义为 $1-bias$ ,这样的方法归功于平滑性的设计。
你肯定想问，1是哪里来的？

浮点数编码表示方法

注意《深入理解计算机系统》这本书中，尾数的表示方法，和现行的中文教材不太一样。
在《深入理解计算机系统》这本书中提到：尾数的范围是 $[1,2-\epsilon)$
而在我们现行的教材上，尾数的范围是 $[0,1-\epsilon)$

浮点数编码能够表示的范围

注意在尾数部分，小数点是跟在数符后面的。

浮点数的规格化

浮点数的规格化表示，要求小数点后的第一位必须是 $1$ (基数 $r=2$ )，其他情况如果 $r=4$ ，则小数点后最高2位不全为0。

举例1

特别注意，在这个例子中，阶码是正数，它的补码保持不变，尾数的补码要取反加一

在《深入理解计算机系统》这本书中，规定尾数M是二进制小数，它的范围是 $[1,2-\epsilon)$
如果按照这样的规定：
$7.0=111.0$
$111.0=1.11\times 2^{10}$ ，特别说明这里 $2^{10}$ 表示小数点往右移动2位， $10$ 是二进制数。
可以知道阶码用2位来表示， $E=2$ ， $M=1.11$ ， $f=0.11$ ， $e=bias+E$

举例2

与Intel兼容的处理器采用“扩展精度”浮点形式。这种格式具有80位字长，1个符号位，k=15个阶码位，1个单独的整数位和n=63个小数位。
注意，阶码位15个，其中一个位用来保存阶符。所以如果阶码部分全部为1，其阶码值为 $bias=2^{14}-1$
最小的正非规格化数
$1,11\cdots 1(14) \; 00\cdots 0(62)1$ ，括号表示位值重复了多少次。
相对应的十进制值为 $2^{-bias}\times 2 \times 2^{-63}=2^{1-bias-63}$
特别注意，非规格化数的偏置值为 $1-bias$ 而不是 $-bias$ ，多乘了一个2，为什么？这个是为了表示非规格化值平滑转换到规格化值。

最小的正规格化数
$1,11\cdots 1(14) \; 100\cdots 0(62)=2^{-bias}\times 2^{-1}=2^{-(bias+1)}$

最大的规格化数
$0,11\cdots 1(14) \; 11\cdots 1(63)=2^{bias}\times (1-2^{-63})$

举例3

在2008版的IEEE浮点数标准中，为了表示数 $\frac{7}{8}$ ，很显然 $s=0$ ，表示正数， $7=111.0$ ， $\frac{7}{8}$ 表示小数点左移3位。
$\frac{7}{8}=\frac{7}{4} \times 2^{-1}$ ，其中 $V=(-1)^{s}\times M \times 2^{E}$ ，对比一下可以推出 $M=\frac{7}{4}$ ， $E=-1$
$bias=2^{4}-1=15$ ， $e=E+bias=-1+15=14$ ，14用二进制表示为 $01110$ ，这是阶码字段。
尾数字段计算如下： $1.11 \times 2^{E}$ ，其中1.11扩充成10位。 $1100000000$ 表示尾数字段。
$01110 \ combined \ with \ 1100000000=hex(3b00)$

由此我们可以填表：
情况1：机器0
$bias=2^{4}-1=15$
-0，表示机器0，机器0的 $M$ 值为0，由于规格化表示隐含小数点后的第一位是1，所以 $e=XXX.100\cdots 0$ ，即 $e=1$ ， $E=e-bias=1-15=-14$
$V=-0 \ D=-0.0$
$hex(0b10000 \ 0000000000)=0x8000$

情况2：最小的大于2的值
$(-1)^{s} \times M \times 2^{E}$ ，要使得最小，很显然 $E=1$ ，并且使得 $s=0$ 并且 $M$ 最小。
$e=E+bias=1+15=16$ ，所以阶码部分可以表示成 $10000$ ，再来看 $M$ ， $M$ 要尽可能小，怎么样才能让 $M$ 尽可能小， $M$ 为正数。
$M=0000000001$ ，这样该值的二进制表示为 $100000000000001$ ，十六进制为 $0x4001$
注意到由于是规格化表示，这个数的尾数数值部分应该是 $1.000000001$ ，如果看成是小数点移动，则 $10000000001=2^{10}+1=1025$ ，可以看作小数点向左移动10位，所以 $1.000000001=1025/2^{10}=1025/1024$ ，
所对应的 $V=\frac{1025}{1024} \times 2^{E}=\frac{1025}{512}=2.001953125$

情况3:512
$512.0=2^{9} \times 1$ ， $1=2^{0}$ ，可以看作不移动小数点。
$M=1.0000000000$ ，这里只研究小数部分，所以为 $.0000000000$
$M=1 \; E=9 \quad e=E+bias=9+15=24=0b11000$
组合起来 $11000 \; 0000000000=0x6000$

最大的非规格化数
此时 $M$ 不包括开头的1，最大的值对应的尾数部分是 $0.0111111111=001111111111 \times 2^{-10}=\frac{1023}{1024}$
再看阶码部分，非规格化数的阶码恒为 $E=1-bias=1-15=-14$ ，综合看来， $\frac{1023}{1024} \times 2^{-14}=\frac{1023}{2^{24}}$
上述结果为 $6.097555160522461e-05$
十六进制的值为 $00000001111111111=0x3ff$

负无穷
负无穷就是阶码值全部为1，尾数字段全部为0
$1111110000000000=0xfc00$

十六进制为3bb0的数
$3bb0=011101110110000$ ，可以去除阶码部分的5位数 $01110=14 \quad e=14 \quad E=e-bias=14-15=-1$
再看 $M=1110110000=$ ，其实，实际上表示的数为 $1.111011$ ，规格化数中这里的1省略， $.111011=\frac{111011}{2^{6}}=59/64$
综上 $\frac{59}{64} \times 2^{E}=\frac{59}{128}$

举例4

对于第一行的例子： $\frac{9}{16}$ 要凑成一个大于1的数
$\frac{9}{16}=\frac{9}{8} \times \frac{1}{2}=(1+\frac{1}{8}) \times 2^{-1}=(1+\frac{2}{16}) \times 2^{-1}$
$E=-1 \quad e=E+bias=-1+7=6$
可以写成是： $f \quad 0010 \quad \quad e \quad 0110$
$1 \ 0110 \ 0010$

对于1
阶码为 $10110$ ，
$e=22 \quad E=e-bias=22-15=7 \quad f=\frac{0b101}{2^{3}}=\frac{1+4}{8}=\frac{5}{8}$
$M=1+\frac{5}{8}=\frac{13}{8} \quad V=(-1)^{s} \times M \times 2^{E}=13 \times 2^{4}$

先确定下在格式B中的 $frac=1010$ ， $f=\frac{0b1010}{2^{4}}=\frac{5}{8} \quad M=\frac{13}{8}$
$V=(-1)^{s} \times \frac{13}{8} times 2^{E} \quad E-3=4 \quad e=7+bias=14$
$14=0b1110$
$0 \ 1110 \ 1010$

对于2
$e=00111=7 \quad E-7-bias=7-15=-8$
$f=\frac{0b110}{8}=\frac{6}{8} \quad M=1+f=\frac{7}{4}$
$V=(-1)^{s} \times 2^{E} \times M=- \frac{7}{2^{10}}$

在格式B下：
$frac=1100$
$f=\frac{0b1100}{16}=\frac{12}{16}=\frac{3}{4} \quad M=1+f=\frac{7}{4}$
$M \times 2^{E}=\frac{7}{2^{10}} \quad E=-8 \quad e=E+bias=-8+7=-1$
推出在格式B下为非规格化数
由此 $e=0b0000 \quad E=1-bias=1-7=-6 \quad 2^{-6} \times M = 7 \times 2^{-10}$
$f=M=7 \times \frac{1}{2^{4}}$
$frac=f \times 16 = 7 = 0b0111$
$1 \ 0000 \ 01111$

对于3
$e=0b00000 \quad E=1-bias=1-15=-14$
$f=M=\frac{0b101}{8}=\frac{1+4}{8}=\frac{5}{8} \quad V=\frac{5}{8} \times 2^{-14}=\frac{5}{2^{17}}$

对于非规格化数
$e=0b0000 \quad E=1-bias=1-7=-6$
$M \times 2^{E}=\frac{5}{2^{17}} \quad M=f=5 \times 2^{-11}$
$frac=f \times 2^4=\frac{5}{2^{7}}$ ，舍入到1，结果为
$0 \ 0000 \ 0001$

$e=0b0000 \quad E=1-bias=1-7=-6$
$f=M=\frac{1}{16}$
$V=M \times 2^{-6}=\frac{1}{2^{10}}$

对于4
$e=0b11011=27 \quad E=e-bias=27-15=12$
$f=\frac{0b000}{2^3}=0 \quad M=1$
$V=-M \times 2^{12}=-2^{12}$

$frac=0b0000$ 肯定是不行的，会出现溢出，仅靠e的部分无法表示 $2^{12}$
阶码位最大为 $4$ 位，能够取得的最大值为 $0b1111$ ， $e=15 \quad E=e-bias=15-7=8$
但注意到在IEEE标准中， $1111 \ 0000$ 表示 $\infty$ ，所以我们让 $e=14$
$e=14 \quad e=0b1110 \quad E=e-bias=14-7=7$
$V=-2^{12}=-2^{5} \times 2^{7}$
$-2^{5}$ 舍入到 $-31$ ，所以 $V=-31 \times 2^{7}$

$0000$ 要向上舍入，而原来的A<0，所以取绝对值减一，舍入到 $0000-1=1111$
$frac=1111 \quad f=\frac{1111}{16}=\frac{15}{16} \quad M=1+f=\frac{31}{16}$
$V=(-1)^{s} \times \frac{31}{16} \times 2^{E}$
$\frac{31}{16} \times 2^{E}=31 \times 2^{7}$
$e \leq 14$ ，所以 $e \leq 1110 \quad E \leq (e-bias=7)$
$\frac{31}{16}$ 舍入到 $31$
$E=7 \quad e=1110$
$e=1110 \quad frac=1111$
$1 \ 1110 \ 1111 \quad V=- \frac{31}{16} \times 2^{7}=-31 \times 2^{3}$

对于5
$frac=0b100 \quad f=\frac{0b100}{8}=\frac{4}{8}=\frac{1}{2} \quad M=\frac{3}{2}$
$e=0b11000=24 \quad E=e-bias=24-15=9$
$V=(-1)^{s} \times 2^{E} \times M=3 \times 2^{8}$

对于B， $frac=0b1000=8$
$f=\frac{8}{16}=\frac{1}{2} \quad M=1+f=\frac{3}{2}$
$V=3 \times 2^{8}$
$3 \times 2^{8}=\frac{3}{2} \times 2^{E} \quad 2^{8}=2^{E-1} \quad E=9$
$e=9+7=16$ ，很显然溢出了。
向正无穷舍入 $\frac{3}{2}$ 舍入到 $\frac{6}{2}$ ，即有 $3 \times 2^{8}=\frac{3}{2} \times 2^{E}$
$E=8 \quad e=8+7=15 \quad e=0b1111$
$e=0b1111$ ，很显然结果为 $\infty$
$0 \ 1111 \ 0000 \quad V=\infty$

举例5

float类型的值使用32位的IEEE格式，double类型的值使用64位IEEE格式。
随机数转换成为double类型的值，来测试精度的转换。

这里值得注意的是，浮点运算一般是不能结合的。
主要是因为舍入的问题，容易出错。

0.2+0.3=0.5->1
1+0.5=1.5->2

0.3+0.5=0.8->1
0.2+1=1.2->1

(0.2+0.3)+0.5=1+0.5->2
0.2+(0.3+0.5)=0.2+1->1
二者并不相等

在本机上，运行相关代码得到的结果如下：

#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <assert.h>
#include <ctime>

using namespace std;

/*int create_random()
{
    srand((unsigned)time(NULL));
    return rand();
}*/

int A(int x,double dx)
{
    return (float) x == (float) dx;
}

int B(int x,int y,double dx,double dy)
{
    return (dx-dy) == (double) (x-y);
}

int C(double dx,double dy,double dz)
{
    return (dx+dy)+dz == dx+(dy+dz);
}

int D(double dx,double dy,double dz)
{
    return (dx*dy)*dz == dx*(dy*dz);
}

int E(double dx,double dz)
{
    return dx/dx == dz/dz;
}

int main()
{
    srand( (unsigned)time(NULL) );
    int x = rand();
    int y = rand();
    int z = rand();
    printf("x: %d\n",x);
    printf("y: %d\n",y);
    printf("z: %d\n",z);

    double dx = (double) x;
    double dy = (double) y;
    double dz = (double) z;

    printf("check:\n");
    cout<<"A: "<<A(x,dx)<<endl;
    cout<<"Another A: "<<A(0x20001,(double)0x20001)<<endl;
    cout<<"B: "<<B(0,INT_MIN,(double)0,(double)INT_MIN)<<endl;
    dx = (double)0x2001;
    dy = (double)INT_MIN;
    dz = (double)100;
    cout<<"C: "<<C(dx,dy,dz)<<endl;

    cout<<"rand c:"<<endl;
    dx = (double)rand();
    dy = (double)rand();
    dz = (double)rand();
    cout<<C(dx,dy,dz)<<endl;

    dx = (double)rand();
    dy = (double)0xFFFFFFFF;
    dz = (double)INT_MIN;
    cout<<"D: "<<D(dx,dy,dz)<<endl;

    dx = (double)rand();
    cout<<"E: "<<E(dx,(double)0)<<endl;
}

从以上代码可以看出：
减法行为，在

1 2	x=0; y=INT_MIN;

会出现溢出错误。

除法行为，在除数为0的时候会发生错误。

举例6

编写一个C函数来计算 $2^{x}$ 的浮点表示。完成这个任务最好的方法是直接创建结果的IEEE单精度表示。当 $x$ 太小时，你的程序会返回 $0.0$ ，当x太大时，它会返回 $+ \infty$ 。填写代码的空白部分，计算正确结果。假设函数 $u2f$ 返回的浮点值与它的无符号参数有相同的位表示。

浮点值和无符号参数的位表示相同

float u2f(unsigned x)
{
    return *(float*) &x;
    // &x是变量x的地址
    // (float*) &x 获取float型指针
    // *(float*) &x 对指针解引用，得到float型的值
}

$2^{x}$ 的浮点表示，最终结果是IEEE的单精度表示，如下图所示：

先确定偏置量， $bias$ 等于 $exp$ 中的位数。

bias=1<<(8-1)-1=pow(2,7)-1=127

//Denormalized
E=1-bias=2-pow(2,7)

//Normalized
E=e-bias=e-pow(2,7)

float fpwr2(int x)
{
    // x仅仅表示指数，只需要观察指数部分
}

浮点表示： $(-1)^{s} \times frac \times 2^{E}$

1、x小于最小的非规格化数
此时 $E=1-bias=2-pow(2,7)$ ，而frac部分有23位，全部清0，相当于 $2^E>>23$ ，右移23位可以让 $frac$ 部分清0，这样得到的数比最小的非规格化数还小
$2^{E}>>23$ ，此时满足的条件是： $x<2-pow(2,7)-23$

2、x小于最小的规格化数，此时 $2^x$ 表示非规格化数
此时 $e=1$ ， $bias=pow(2,7)-1$ ， $E=e-bias=2-pow(2,7)$
$x<2-pow(2,7)$ ，此时仅有frac部分。

很显然，此时 $E=0$ ， $2^{E}=1$ ，所以 $2^{x}=frac$
$frac=2^{x}=2^{b}$ ， $b$ 此时的值是 $x$ 相对于最小基准 $2-pow(2,7)-23$ ，即只取超出 $2-pow(2,7)-23$ 的部分。

1	frac=1<<(unsigned)(x-(2-pow(2,7)-23))

3、x小于最大的规格化数，此时 $2^x$ 表示规格化数
最大的规格化数，此时指数 $E=bias=pow(2,7)-1$ ，注意到此时E可以取到 $pow(2,7)-1$

此时取 $frac=0$
$2^{x}=2^{E}$ ， $x=E=exp-bias$ ，可以得到 $exp=x+bias=x+pow(2,7)-1$

4、剩余情况，取无穷
$exp=0xFF$
$frac=0$

实现代码如下：

#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <iostream>

using namespace std;

float u2f(unsigned x)
//这里涉及到无符号数转换成浮点数
//使用引用
{
    return *(float*) &x;
    // &x是变量x的地址
    // (float*) &x 获取float型指针
    // *(float*) &x 对指针解引用，得到float型的值
}

float fpwr2(int x)
{
    unsigned expr,frac;
    unsigned u;

    if(x < 2-pow(2,7)-23)
    {
        expr = 0;
        frac = 0;
    }
    else if(x < 2-pow(2,7))
    {
        expr = 0;
        frac = 1 << (unsigned)(x - (2-pow(2,7)-23) );
    }
    else if(x < pow(2,7)-1+1)
    {
        expr = x + pow(2,7) - 1;
        frac = 0;
    }
    else
    {
        expr = 0xFF;
        frac = 0;
    }

    u = expr << 23 | frac;
    return u2f(u);
}

int main()
{
    cout<<"calculate: "<<powf(2,0)<<" test: "<<fpwr2(0)<<endl;
    cout<<"calculate: "<<powf(2,100)<<" test: "<<fpwr2(100)<<endl;
    cout<<"calculate: "<<powf(2,-100)<<" test: "<<fpwr2(-100)<<endl;
    cout<<"calculate: "<<powf(2,10000)<<" test: "<<fpwr2(10000)<<endl;
    cout<<"calculate: "<<powf(2,-10000)<<" test: "<<fpwr2(-10000)<<endl;
    return 0;
}

举例7

$\pi$ 的单精度浮点值的十六进制表示为 $0x40490FDB$
注意，给的数为单精度浮点型的小数，frac部分有23位，exp部分有8位。
1、二进制小数
表示的二进制小数的小数部分为：
$100 \ 1001 \ 0000 \ 1111 \ 1101 \ 1011$
二进制小数的阶码部分为：
$1000 \ 0000$
$bias=2^{8-1}-1=127$
$E=exp-bias=128-127=1$
由于二进制的阶码部分不为0，所以二进制小数是规格化数，二进制小数可以如下表示：
$1.100 \ 1001 \ 0000 \ 1111 \ 1101 \ 1011$
二进制小数可以表示成：
$1.100 1001 0000 1111 1101 1011 \times 2^{1}=11.0010010000111111011011$

2、 $\frac{22}{7}$ 的二进制小数表示是什么
$\frac{22}{7}=3+\frac{1}{7}$
$3=0b11$
$\frac{1}{7}$ 的二进制小数表示是：
$\frac{Y}{2^{k}-1}$ ，可以知道 $Y=1 \ k=3$ ， $y$ 是一个3位的序列。
可以看作 $1>>3=\frac{1}{2^{3}-1}=0.001$
综上 $\frac{22}{7}$ 的二进制表示是： $0b11.001001001(001)$

3、这两个 $\pi$ 的近似值从小数点后第九位开始不同

位级浮点编码规则

对于参数 $f$ ，如果 $f$ 是非规格化的，该函数返回 $\pm0$

float_bits float_denorm_zero(float_bits f)
{
    unsigned sign = f >> 31;
    //相当于把小数点放置在第31位后面，这样就得到符号位

    unsigned exp = f >> 23 & 0xFF;
    //相当于把小数点放置在exp位置之后，这样就得到了阶码部分
    //取出相应的值，只要&ff就可以

    unsigned frac = f & 0x7FFFFF;
    //只取小数位，共23位

    if(exp == 0)
    {
        frac = 0;
    }
    return (sign << 31) | (exp << 23) | frac;
    //这里移动小数点，相当于右移小数点
}

例1

对于浮点数 $f$ ，计算 $-f$ ，如果 $f=\infty$ ，函数返回 $f$

#include <stdio.h>
#include <iostream>
#include "float_negate.h"
#include <math.h>
#include <cmath>
#include <algorithm>
#include <assert.h>
#include <string.h>
#include <cstring>
#include <limits.h>
#include <climits>
using namespace std;

float_bits float_negate(float_bits f)
{
    unsigned sign = f >> 31;
    cout << sign << endl;

    unsigned exp = f >> 23 & 0xFF;
    cout << exp << endl;

    unsigned frac = f & 0x7FFFFF;
    cout << frac << endl;

    if(exp == 0xFF && frac != 0)  //NAN
        return f;

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

int main()
{
    unsigned testV;
    cin >> testV;
    
    unsigned res = float_negate(testV);
    cout << "test value is " << *(float*) (&res) << endl;

    cout << "The real value is " << -(*(float*)(&testV)) << endl;
    
}

实现结果：

例2

遵循位级浮点编码规则，实现具有如下原型的函数：

1	float_bits float_absval(float_bits f);

实现方法如下：

#include <stdio.h>
#include <iostream>
#include <limits.h>
#include <math.h>

using namespace std;

/*
 * float-absval.h
 */

typedef unsigned float_bits;

float_bits float_absval(float_bits f);


float_bits float_absval(float_bits f)
{
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;

    int is_NAN = (exp == 0xFF) && (frac != 0);
    if(is_NAN)
        return f;
    
    return 0 << 31 | exp << 23 | frac;
}

float u2f(unsigned u)
{
    return *(float*) &u;
}

unsigned f2u(float u)
{
    return *(unsigned*) &u;
} 

int main()
{
    unsigned testV;
    float f_test;
    cin >> testV >> f_test;

    float testF = u2f(testV);

    unsigned u_test = f2u(f_test);
    

    if(isnan(testF))
    {
        cout << "test " << testF;
        cout << "real " << testV;
    }
    else
    {
        cout << "test1= " << u2f(float_absval(testV)) << endl;
        cout << "real1= " << fabs(testF) << endl;

        cout << "test2= " << u2f(float_absval(u_test)) << endl;
        cout << "real2= " << fabs(f_test) << endl;
    }
}

结果：

例3

实现能够计算 $2.0 \times f$ 的函数。

实现函数如下：

#include <stdio.h>
#include <iostream>
#include <limits.h>

using namespace std;

typedef unsigned float_bits;

float_bits float_half(float_bits f);

/*
    本例中要求舍入到偶数
    0b00 --> 0b00 + addition(0) = 0b00
    0b01 --> 0b00 + addition(0) = 0b00
    0b10 --> 0b01 + addition(0) = 0b01
    0b11 --> /2=1.5=2 --> 0b01 + addition(1) = 0b10

    only 0b11 --> addition = 1
    if &0b11 == 0b11
        addition = 1
    else
        addition = 0

    addition = (frac & 0x3) == 0x3
*/

float_bits float_half(float_bits f)
{
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;

    unsigned remain = f & 0x7FFFFFFF;

    int is_NAN_or_infinity = (exp == 0xFF);
    if(is_NAN_or_infinity){
        return f;
    }

    int addition = (frac & 0x3) == 0x3;

    if(exp == 0)
    {
        //Denormalized
        frac >>= 1;
        frac += addition;
    }
    else if(exp == 1)
    {
        //Normalized to Denormalized
        remain >>= 1;
        remain += addition;
        exp = (remain >> 23) & 0xFF;
        frac = remain & 0x7FFFFF;
    }
    else
    {
        //include factor 2
        exp -= 1;
    }

    return sign << 31 | exp << 23 | frac;
}

float u2f(unsigned u)
{
    return *(float*) &u;
}

unsigned f2u(float u)
{
    return *(unsigned*) &u;
}

int main()
{
    float f_test;
    cout << "input float : ";
    cin >> f_test;

    unsigned u_test = f2u(f_test);
    float real = f_test / 2;

    cout << "real: " << real << endl;
    cout << "test: " << u2f(float_half(u_test)) << endl;
}

结果：

例4

对于浮点数f，这个函数计算(int)f，如果f是NaN，你的函数应该向0舍入。如果f不能用整数表示，例如，超出表示范围，或者它是一个NaN，那么函数应该返回0x800000000

我们这里仅仅考虑正数的情况：
有如下几种：

第一种：

1
2
3

0 00000000 00000000000000000000000
    ===>
0 01111111 00000000000000000000000

值所能表示的范围是：
$1.0 \times 2^{0}$ ，此时 $2^{E}=2^0$ ，对应的指数的值为 $E=exp-bias=0$ ，可以求出 $exp=7$

取值范围为： $0 \leq f \leq 1$ ，值舍入到0

第二种：

1
2
3

0 01111111 00000000000000000000000
    ===>
0 (01111111+31) 00000000000000000000000

此时，我们得到的上界为 $NaN$ ，浮点数可以表示32为整数，其中最高位为符号位，能够表示的最大的值为 $2^{31}-1$ ，所以最大的 $int$ 用浮点数表示就是：
0 (01111111+31) 00000000000000000000000

第三种：

0 (01111111+31) 00000000000000000000000
    ===>
infinity
return 0x80000000

值得注意的是，把浮点数转换成整形，必须

1	frac \| 0x80000000

来获取整数部分，如何最后我们如何舍去小数部分？
采用移位的方式：
$\pm \ 1.frac \times 2^{exp-bias}$ ，用移位的方式去掉frac部分，如下图：

最后我们得到 $M \times 2^{E}$ ，相当于我们在 $M$ 的基础上，执行M<<E运算。

如果 $E>23$ ，则执行 $M \times 2^E$ ，相当于小数点右移23位，除去小数点，然后再整体执行左移(E-23)位，即M<<(E-23)

如果 $E<23$ ，则执行 $M \times 2^{E}$ 之后还会有小数点，小数点并不能完全消除掉。我们要人为地把小数点后的数全部抛弃，此时小数点的位置在距离末尾(23-E)处，此时M>>(23-E)，即可舍去小数点后的部分。

/*
 * float-f2i.h
 */

#include <stdio.h>
#include <iostream>
#include <limits.h>

using namespace std;

typedef unsigned float_bits;

int float_f2i(float_bits f);

int float_f2i(float_bits f)
{
    unsigned sign = f >> 31;
    unsigned exp = f >> 23 & 0xFF;
    unsigned frac = f & 0x7FFFFF;
    unsigned bias = 0x7F;

    /*
        consider positive numbers

        0 00000000 00000000000000000000000
        ===>
        0 01111111 00000000000000000000000
        1.0*(2^0),now E=exp-bias=0,means exp=7
        exp=1111111
        now 0<=f<=1
        we get integer 0


        0 01111111 00000000000000000000000
        now E=exp-bias=0 2^E=1
        ===>
        NaN的取值为多少？我们注意到浮点数可以表示32位整数，最高位是符号位
        所以能表示的最大的值是2^{31}-1
        上面这个数用浮点数表示是：
        0 (01111111+31) 00000000000000000000
    */
    unsigned M;
    unsigned E;
    int val;

    if(exp >=0 && exp < 0 + bias)
    {
        val = 0;
    }
    else if(exp >= 31 + bias)
    {
        //overflow
        val = 0x80000000;
    }
    else
    {
        E = exp - bias;
        M = frac | 0x800000;
        if(E > 23)
            val = M << (E - 23);
        else
            val = M >> (23 - E);
    }

    return sign ? -val : val;
}

int u2i(unsigned u)
{
    return *(int*) &u;
}

unsigned i2u(int u)
{
    return *(unsigned*) &u;
}

unsigned f2u(float u)
{
    return *(unsigned*) &u;
}

int main()
{
    float f_test;
    cout << "input float : ";
    cin >> f_test;

    unsigned u_test = f2u(f_test);
    int real = (int)f_test;
    //注意，float转换为int，要舍入，直接(int) float_v
    //而不是*(int*) float_v

    cout << "real : " << real << endl;
    cout << "test : " << float_f2i(u_test) << endl;
}

注意，float转换为int，要舍入，直接(int) float_v
而不是*(int*) float_v

例5

给出一个函数计算(float) i的位级表示。
浮点数向偶数舍入的问题
有效数字超出规定数位，例如，多余数字是1001，超出了规定最低位的一半，(规定最低位的一半为：1000)，故最低位进1.
如果多余数字是0111，它小于最低位的一半，则舍掉多余数字（截断尾数）即可
如果对于数字是1000，正好是最低位一半的特殊情况，例如：0 1000，最低位为0，舍掉多余位，1 1000，最低位为1，则舍掉多余位后加1，使得最低位为0(偶数)。

举例，要求保留小数点后3位。

对于1.0011001，舍入处理后为1.010（去掉多余的4位，加0.001）
对于1.0010111，舍入处理后为1.001（去掉多余的4位）
对于1.0011000，舍入处理后为1.010（去掉多余的4位，加0.001，使得最低位为0）

对于1.1001001，舍入处理后为1.101（去掉多余的4位，加0.001）
对于1.1000111，舍入处理后为1.100（去掉多余的4位）
对于1.1001000，舍入处理后为1.100（去掉多余的4位，不加，因为最低位已经为0）

对于1.01011，舍入处理后为1.011（去掉多余的2位，加0.001）
对于1.01001，舍入处理后为1.010（去掉多余的2位）
对于1.01010，舍入处理后为1.010（去掉多余的2位，不加）

对于1.01111，舍入处理后为1.100（去掉多余的2位，加0.001）
对于1.01101，舍入处理后为1.011（去掉多余的2位）
对于1.01110，舍入处理后为1.100（去掉多余的2位，加0.001）

在整数向浮点数转换的过程中，很重要的一点是，浮点数写成 $2^{E}$ ，一定是规格化数，所以 $exp$ 不为0。因为 $exp$ 等于0的情况我们单独考虑。

整数转换成浮点数，需要以下几个函数：
$bit-length()$ 判断int型有几位，是否超过了最大的32位
frac的位数可能会超过23位，这个时候我们要把特定的舍入位数，比如低xx位取出来，完成这个取出任务所需要的函数是 $bits-mask()$ ，给位数盖一个面罩，然后取出
值得注意的是，由于int转换成float，必定为规格化数，所以最后的fbits=bits-1，float型的frac部分要减去最开始的1

比较难以理解的是 $i=0xffffffff$ 的情况，此时整数转换成浮点数，是一个 $-2^{E}$ ，注意此时frac为0，因为整数并不包含小数点后的部分，frac部分为1.0000…，是一个绝对值非常非常大的负数，指数expe要尽可能大，如果把指数看成是小数点移位的话，指数最大可以取多少呢？可以移动多少位呢？最多为31位。
expe=bias+31

我们让expe=bias+fbits，这样可以看成是小数点在最左边，然后往右移动fbits位。唯一要考虑的就是23位够不够放int型的整数？
int型的整数，罩上mask，获取val值，来进行移位操作
val=i & bits_mask(fbits)

如果值为负数，记得取反加1

思路

1、首先考虑符号位，然后讲i取绝对值，当成一个正数转化即可。然后判断i是2的几次幂，可以通过类似于二分法的方式判断。即右移16位判断是否不为0，如果不为0则exp+16，然后判断右移16位后剩余的位数有几位，否则右移8位判断依次类推。
2、因为是正数，小数点左边存在一个隐式的1，所以num=( ~ (1<< exp ) ) & num ;把最高的1去掉，然后把剩余的数放进frac中，同时要考虑向偶数取整的问题。
3、如果num不足23位，直接移动相应位数，放入frac中，否则截掉多余的位数，如果最后一位并且舍去一段中的最高也为1或者舍去的东西超过0.5那么就给frac+1，判断一下frac时候有溢出，溢出的话给exp+1，然后取剩余的23位的值即可。最后就是给exp加上bias偏置值，前提是如果num不为0。

重要思路：

unsigned val = i;
unsigned sign = i < 0 ? 1 : 0;

if(sign)
    val = ~val + 1;

unsigned exp = 0;
unsigned frac = 0;
unsigned temp = val;

if(val >> 16)
{
    exp += 0x10; //除以16，再加回来
    val = val >> 0x10;
}
if(val >> 8)
{
    exp += 0x8;
    val = val >> 0x8;
}
if(val >> 4)
{
    exp += 0x4;
    val = val >> 0x4;
}
if(val >> 2)
{
    exp += 0x2;
    val = val >> 0x2;
}
if(val >> 1)
{
    exp += 0x1;
    val = val >> 0x1;
}
//此时exp表示小数点从右边开始，往左多少位

//去掉小数点最高位1
val = temp;
val = (~(1 << exp)) & val;
//此时val为小数点后面的部分

// (temp >> 23)判断temp大于23位

最终 $\times 2^{expe}$ 小数点在最右边，所以expe实际上表示小数点的实际位置：即从最右边开始，向左移动expe位就是小数点实际位置

舍入原则上面说明了，值得注意的是，向偶数舍入，frac+=1，可能会造成frac溢出
例如： frac=111 1111 1111 1111 1111 1111
frac+1=1000 0000 0000 0000 0000 0000
相当于小数点从右边开始移动到实际位置要多移动1位，所以是expe+=1
frac=frac & 0x7fffff
取最后23位

可能遇到的情况描述如下图：

实现方法：

#include <stdio.h>
#include <limits.h>
#include <iostream>
#include <cstdio>
#include <math.h>

using namespace std;

typedef unsigned float_bits;

float_bits float_i2f(int i);

unsigned mask(unsigned bits)
{
    return (1 << bits) - 1;
}
unsigned leftmost(unsigned bits)
{
    return 1 << bits;
}

float_bits float_i2f(int i)
{
    unsigned val = i;
    unsigned sign = i < 0 ? 1 : 0;

    if(sign)
        val = ~val + 1;
    
    unsigned expe = 0;
    unsigned frac = 0;
    unsigned temp = val;


    if(val >> 16)
    {
        expe += 0x10; //除以16，再加回来
        val = val >> 0x10;
    }
    if(val >> 8)
    {
        expe += 0x8;
        val = val >> 0x8;
    }
    if(val >> 4)
    {
        expe += 0x4;
        val = val >> 0x4;
    }
    if(val >> 2)
    {
        expe += 0x2;
        val = val >> 0x2;
    }
    if(val >> 1)
    {
        expe += 0x1;
        val = val >> 0x1;
    }
    //此时expe表示小数点从右边开始，往左多少位

    //去掉小数点最高位1
    val = temp;
    val = (~(1 << expe)) & val;
    //此时val为小数点后面的部分

    if(temp >> 23)
    {
        unsigned offset = expe - 23;
        //溢出部分
        frac = val >> offset;
        unsigned roundv = 0;
        unsigned round_bits = val & mask(offset);
        int cond1 = ( (val & mask(offset)) > leftmost(offset-1));
        int cond2 = ( (frac & 0x1) && (round_bits == leftmost(offset-1)) );

        if( (expe != 23) && (cond1 || cond2) )
        {
            frac += 1;
        }
        //向偶数舍入溢出了怎么办？
        //小数点从右边开始，往左边多移动1位
        if(frac >> 23)
        {
            expe += 1;
            frac = frac & 0x7fffff;
        }
    }
    else
        frac = val << (23 - expe);

    if(temp)
        expe += 127;

    return sign << 31 | expe << 23 | frac;
}

float u2f(unsigned u)
{
    return *(float*)&u;
}

int main()
{
    int i_test;
    cout << "input int: ";
    scanf("%d",&i_test);

    float real = (float) i_test;

    printf("real: %f\n",real);
    printf("test: %f\n",u2f(float_i2f(i_test)));
}