这篇文章是基于csapp第二章的习题做的一个总结，习题以及答案在这里。

1. 信息的存储

计算机中信息的存储就是bit，每8个bit构成一个byte，所有的空间都是由一系列byte组成的。几个byte就可以表示一个信息，具体的信息就需要相应的context来解释。那么对于具有多个byte的对象来说，如何进行排列是很重要的。

1.1 字节序

这就涉及到了字节序的概念。根据不同的排列方式分类little-endian和big-endian。可以通过下面的代码来查看，对应的机器是否是little-endian的：

typedef unsigned char* byte_pointer;

int is_little_endian() {
    int val = 0xff;
    byte_pointer pval= (byte_pointer)&val;
    return pval[0]==0xff;
}

思路很简单，就是检查一下变量对应地址的第一个字节的内容。

一个字节（byte）是8 bit。C语言中，可以通过sizeof来查看指定类型所占字节数：

int size = sizeof(int);

1.2 位运算与逻辑运算

在移位操作中，如果移动i个字节，那么可以通过下面的方式得到具体的移动位：

i << 3

C语言中的位操作，除了位移，还有与（&）或亦（^）或（|）取反（~）等。

灵活使用一些位操作，可以很方便地达到一些目的。比如，不使用额外的变量来交换两个值：

void inplace_swap(int *x, int *y) {
    *y = *x ^ *y;
    *x = *x ^ *y;
    *y = *x ^ *y;
}

和位操作很像但是又有不同的是逻辑运算。有与（&&）或（||）非（!）。

一个小技巧就是，通过亦或和非来替代等于比较：

x == y

等同于：

!(x ^ y)

逻辑运算中，当第一个参数就能确定结果的时候，是不会计算第二个参数的值的。根据这个性质，我们可以通过一个小技巧，不使用if就可以达到if的效果。

比如下面的条件语句：

int flag;
int sum;
if (flag) {
    sum = INT_MIN;
}

这里，根据flag的值来对sum赋值。如果flag=1的话，那么sum就赋值为INT_MIN；否则保持原样。我们可以通过逻辑运算不使用if来达到这个效果：

flag && (sum = INT_MIN);

是不是很神奇？

1.3 移位运算

前面稍微提到了移位运算，移位运算也很重要。有两个方向，左移和右移，左移很简单了，主要是右移涉及到一些整数编码的问题。

整数的表示在下面介绍，这里只说，右移分为逻辑右移和算术右移。

逻辑右移就直接补0，算术右移需要看最高位的值，用最高位的值来补移出的空位。

好的，现在有一台机器，使用C语言来看看，这台机器右移是否是算术右移：

int int_shifts_are_arithmetic() {
    int val = -1;
    return !(val ^ (val >> 1));
}

这里我们通过位运算代替了==操作符。

关于右移还有一个有意思的问题就是，通过逻辑右移来实现算术右移以及，通过算术右移来实现逻辑右移：

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

unsigned sra(int x, int k) {
    /* Perform shift logically */
    int xsrl = (unsigned)x >> k;
    int w = (sizeof(int)) << 3;
    int mask = ((int)-1) << (w - k);
    /* Get the most significant bit unchanged, 0 for other bits */
    int m = 1 << (w - 1);
    /* Make mask unchanged if the most significant bit of x is 1, changed otherwise */
    mask &= !(x & m) - 1;
    return xsrl | mask;
}

这里就涉及到一些位运算和移位操作的综合了。

对于移位操作，需要注意在C语言中：

If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined.

2. 整数的表示

C语言中整数有signed和unsigned。对于signed，使用最高位作为符号，1为负0位正。所以可以通过查看这个最高位来检查正负：

int sign = i & INT_MIN;

如果sign==0就说明是正数，否则为负。

如果一个signed类型一共有n个bit，那么我们可以知道这个类型所能表示值的范围：[$-2^{n-1}$,$2^{n-1}-1$)。对于一个int类型的值x，能否使用n个bit来进行补码编码呢？

int fits_bits(int x, int n) {
    int w = sizeof(int) << 3;
    int offset = w - n;
    return (x << offset >> offset) == x;
}

能的话就返回1，否则返回0。

3. 整数的运算

整数的运算，由于使用固定长度表示，就有溢出的可能。

判断加法是否溢出：

int tadd_ok(int x, int y) {
    int sum = x + y;
    int neg_over = x < 0 && y < 0 && sum >= 0;
    int pos_over = x >= 0 && y >= 0 && sum < 0;
    return !neg_over && !pos_over;
}

判断减法是否溢出：

int tsub_ok(int x, int y) {
    int sub = x - y;
    int pos_flag = x >= 0 && y < 0 && sub < 0;
    int neg_flag = x < 0 && y >= 0 && sub >=0;
    return !pos_flag && !neg_flag;
}

判断乘法是否溢出：

int tmult_ok(int x, int y) {
    int p = x * y;
    return !x || p/x == y;
}

无符号整数除以2的幂次数的时候，直接右移就可以了；但是对于有符号数，负数不可以直接右移，因为需要向0取舍。所以负数做2的幂次数的除法时，需要添加bias。

/*
 * 3*x/4 should not overflow, then divide 4 first, and multiple 3
 * Rounding to zero:
 *        x is equal to m30(the most significant 30 bits) plus l2(the least significant 2 bits)
 *        x = m30 + l2
 *        m30 = x & ~0x3;
 *        l2 = x & 0x3;
 *        when x >= 0, m30d4m3 = (m30 >> 2) << 1 + (m30 >> 2), l2m3d4 = ((l2 << 1) + l2) >> 2;
 *        when x < 0, need bias, bias = 3
 */
int threefourths(int x) {
    int neg_flag = x & INT_MIN;
    int m30 = x & ~0x3;
    int l2 = x & 0x3;
    int m30d4m3 = ((m30 >> 2) << 1) + (m30 >> 2);
    int bias = 3;
    int l2m3 = (l2 << 1) + l2;
    (neg_flag) && (l2m3 = l2m3 + bias);
    int l2m3d4 = l2m3 >> 2;
    return m30d4m3 + l2m3d4;
}

这个例子综合了乘法与除法，以及溢出的概念。

4. 浮点数

浮点数的表示比整数复杂多了，需要对于IEEE浮点数表示法有所了解。

对于以0.yyy…（y是k bit的序列）这样表示的二进制浮点数来说，它的值n可以表示为：$n=\frac{Y}{2^k-1}$，其中$Y=B2U_k(y)$。

这样我们可以对一个不能使用二进制精确表示的分数得到一个近似的二进制表示了。

比如5/7，k=3，y=101，所以二进制表示就是0.101101101…

IEEE的浮点数表示法有三个主要的部分：sign, exp和frac，这三个部分对于浮点数的一些计算很重要。

比如将一个$2^x$形式的整数使用浮点数的形式表示：

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

float fpwr2(int x) {
    /* Result exponent and fraction */
    unsigned exp, frac;
    unsigned u;

    /* E=1-bias=1-127=-126 n=23 */
    if (x < -149) {
        /* Too small. Return 0.0 */
        exp = 0;
        frac = 0;
    } else if (x < -126) {
        /* Denormalized result */
        exp = 0;
        frac = 1 << (unsigned) (x+149);
    } else if(x < 128){
        /* Normalized result */
        exp = x + 127;
        frac = 0;
    } else {
        /* Too big. Return +oo */
        exp = 0xFF;
        frac = 0;
    }

    /* Pack exp and frac into 32 bits */
    u = exp << 23 | frac;
    /* Return as float */
    return u2f(u);
}

自己手动来拼接浮点数的表示对于理解浮点数的表示很有帮助。

拿到一个浮点数的编码来计算对应的值是很容易的。但是将一个整数转成浮点数编码，还是比较复杂的：

typedef unsigned float_bits;

/* Get bit length for integer i. Return 32 when i is negative. */
int bits_length(int i) {
    if ((i & INT_MIN) != 0) {
        return 32;
    }

    int length = 0;
    unsigned u = (unsigned)i;
    while(u >= (1 << length)) {
        length++;
    }
    return length;
}

/* Generage mask for length len. e.g. 3->0x7 */
unsigned generate_mask(int len) {
    return (unsigned)-1 >> (32-len);
}

float_bits float_i2f(int i) {
    unsigned sign, exp, frac, exp_frac;
    unsigned bias = 0x7F;

    /* i = 0 */
    if (i == 0) {
        sign = 0;
        exp = 0;
        frac = 0;
        return sign << 31 | exp << 23 | frac;
    }

    /* i = INT_MIN */
    if (i == INT_MIN) {
        sign = 1;
        exp = 31 + bias;
        frac = 0;
        return sign << 31 | exp << 23 | frac;
    }

    sign = 0;
    /* i is negative */
    if (i < 0) {
        sign = 1;
        i = -i;
    }

    int length = bits_length(i);
    int flength = length - 1;
    unsigned mask = generate_mask(flength);
    unsigned f = i & mask;
    exp = bias + length - 1;

    if (flength <= 23) {
        /* no overflow */
        frac = f << (23 - flength);
        exp_frac = exp << 23 | frac;
    } else {
        /* overflow */
        int offset = flength - 23;
        frac = f >> offset;
        exp_frac = exp << 23 | frac;
        int round_mid = 1 << (offset - 1);
        int round_part = f & generate_mask(offset);

        /* round to even */
        if (round_part < round_mid) {

        } else if (round_part > round_mid) {
            exp_frac += 1;
        } else {
            if ((frac & 0x1) == 1) {
                exp_frac += 1;
            }
        }
    }
    return sign << 31 | exp_frac;
}

需要考虑各种情况。其中round to even部分的代码解释了，怎么才能round to even。