第2章信息的表示和处理作业

2.55 - 2.57

using byte_pointer = unsigned char *;
using byte = unsigned char;

void show_bytes(byte_pointer start, size_t size)
{
    std::vector<byte> vb;
    for (size_t i = 0; i < size; i++)
        vb.emplace_back(*(start + i));
    reverse(vb.begin(), vb.end()); // little endian
    for (const auto &x : vb)
        printf("%.2x", x);
    puts("");
}
template <typename T>
void show(T x)
{
    show_bytes((byte_pointer)&x, sizeof(T));
}

2.58

bool is_little_endian()
{
    int i = 1;
    return *(byte_pointer)(&i) == 0x01;
}

2.59

(x&0xff)|(y&(~0xff))

2.60

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

2.61

A

!~x

B

!x

C

!~(x&0xff|~0xff)

D

!(x>>(sizeof(int)-1<<3)&0xff)

2.62

bool int_shifts_are_arithmetic()
{
    return (~0x00) >> 1 == ~0x00;
}

2.63

unsigned srl(unsigned x, int k)
{
    unsigned xsra = (int)x >> k;
    return xsra & ((2 << (sizeof(int) << 3) - k - 1) - 1);
}

int sra(int x, int k)
{
    int xsrl = (unsigned)x >> k;
    int w = sizeof(int) << 3;
    int sign = !!(x & 1 << (w - 1));
    int mask = (sign << 1) << w - k - 1;
    return xsrl | (~mask + 1);
}

$srl$ 的主要逻辑是把高位的 $k$ 位置 $0$ 。
$sra$ 的主要逻辑是根据符号置高位的 $k$ 位。
用 $2$ 来左移 $w-k-1$ 位来取代 $1$ 左移 $w-k$ 位，避免左移 $32$ 位的情况出现。

2.64

int any_odd_one(unsigned x)
{
    return !!(x & 0x55555555);
}

2.65

int odd_ones(unsigned x)
{
    x ^= x >> 16;
    x ^= x >> 8;
    x ^= x >> 4;
    x ^= x >> 2;
    x ^= x >> 1;
    return x & 1;
}

首先答案是各位异或起来，然后可以折半异或，每次把高位的一半和低位的一半异或，这样答案不变且规模缩小。

2.66

int left_most(unsigned x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return (x >> 1) + x && 1;
}

2.67

A

左移 $32$ 位没有遵循 $C$ 语言标准，根据各个实现可能不一样。

B

int int_size_is_32()
{
    int set_msb = 1 << 31;
    int beyond_msb = set_msb << 1;
    return set_msb && !beyond_msb;
}

C

int int_size_is_32_v16()
{
    int set_msb = 1 << 15 << 15 << 1;
    int beyond_msb = set_msb << 1;
    return set_msb && !beyond_msb;
}

疑问

这里有个疑问，我一开始的答案是：

int int_size_is_32()
{
    return -1 != 0xffff && -1 == 0xffffffff;
}

个人感觉也是对的，首先在 $32$ 或 $64$ 位机上显然是正确的，其次在 $16$ 位机上， $0xffffffff$ 会被解释为 $longlong$ 从而编译不会出现警告，所以感觉没问题，然而参考了网上的答案发现没有人是这样写的，这里就留一个疑问，不确定是否正确。

2.68

int lower_one_mask(int n)
{
    return (2 << n - 1) - 1;
}

2.69

unsigned rotate_left(unsigned x, int n)
{
    int w = sizeof(int) >> 3;
    return x << n | x >> 1 >> w - 1 - n;
}

2.70

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

看了半天才看懂，大概意思是 $x$ 截断成 $n$ 位后是否还是保持原样。

2.71

A

看了半天才看懂。。错在是负数的时候，因为 $word$ 是无符号的，右移会错。

B

typedef unsigned packed_t;
int xbyte(packed_t word,int bytenum)
{
    return word << ((3 - bytenum) << 3) >> (bytenum << 3);
}

2.72

A

$sizeof$ 运算符返回 $size\_t$ ，这是一个 $unsigned$ 值，在和 $int$ 类型值进行运算时会将其转化成 $unsigned$ 导致结果一定大于等于 $0$ 。

B

void copy_int(int val, void *buf, int maxbytes)
{
    if (maxbytes > 0 && maxbytes >= sizeof(val))
        memcpy(buf, (void *)&val, sizeof(val));
}

2.73

int saturating_add(int x, int y)
{
    int sum = x + y;
    int x_sign = x & INT_MIN, y_sign = y & INT_MIN, sum_sign = sum & INT_MIN;
    int up_overflow = !x_sign && !y_sign && sum_sign, down_overflow = x_sign && y_sign && !sum_sign;
    int non_overflow = !up_overflow && !down_overflow;
    return (-up_overflow & INT_MAX) | (-down_overflow & INT_MIN) | (-non_overflow & sum);
}

主要想法就是通过符号位判断是否上溢下溢，最后进行结果的一个选择。

2.74

int tsub_ok(int x, int y)
{
    int diff = x - y;
    int x_sign = x & INT_MIN, y_sign = y & INT_MIN, diff_sign = diff & INT_MIN;
    return x_sign == y_sign || y_sign != diff_sign;
}

上一题子集。

2.75

unsigned unsigned_high_prod(unsigned x, unsigned y)
{
    int x_sign = !!(x & INT_MIN), y_sign = !!(y & INT_MIN);
    return signed_high_prod(x, y) + (-x_sign) & x + (-y_sign) & y;
}

感觉我这个实现比较好，对答案的时候发现我看的两个人好像都有问题，都用了乘法，不符合位级编码的规则。
至于这个公式的话用补码和无符号整数之间的关系，分类讨论推一下公式就出来了，还是比较优美的。

2.76

void *my_calloc(size_t nmemb, size_t size)
{
    if (!nmemb || !size)
        return nullptr;
    size_t space = nmemb * size;
    if (space / nmemb != size)
        return nullptr;
    void *ptr = malloc(space);
    if (!ptr)
        memset(ptr, 0, space);
    return ptr;
}

2.77

A

(x<<4)+x

B

x-(x<<3)

C

(x<<6)-(x<<2)

D

(x<<4)-(x<<7)

2.78

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

2.79

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

2.80

int threefourths(int x)
{
    //int q = x >> 2;               //buggy
    int q = divide_power2(x, 2);    //quotient
    int r = x - (q << 2);           //remain
    return (q << 1) + q + mul3div4(r);
}

我对答案的两位大哥好像都做复杂了，感觉我这个实现是对的，测了几个数据也没发现问题。
主要想法就是将 $x$ 拆成能被 $4$ 整除的部分和余数，能被 $4$ 整除的部分就先除再乘避免溢出，剩下的余数因为不大就直接算。需要注意的部分是取商和余数的时候要保持符号不变不然可能会有问题。

2.81

A

-(1<<k)

B

(1<<k+j)-(1<<j)

2.82

A

否，反例： $x=INT\_MIN$

B

是，原理：溢出后会对 $2^{32}$ 取模，无论是乘法运算符还是左移运算符都一样，不改变位级表示。

C

是，原理：两边都补上 $1$ 后，可以解释为分别取相反数然后加起来和加起来取相反数。

D

是，原理：位级更改一致且左右都解释为无符号

E

是，原理：相当于将最低两位置 $0$ ，无论正负，在各自的范围内位级表示是单调增的，所以等式成立。

2.83

A

$\frac{Y}{2^k-1}$ ，考虑无穷级数求和

B

(a) $\frac{5}{7}$
(b) $\frac{2}{5}$
(c) $\frac{19}{63}$

2.84

int tsub_ok(int x, int y)
{
    int diff = x - y;
    int x_sign = x & INT_MIN, y_sign = y & INT_MIN, diff_sign = diff & INT_MIN;
    return x_sign == y_sign || y_sign != diff_sign;
}

2.85

$bias=2^{k-1}-1$

A

$E=10_2$
$M=1.11_2$
$f=0.11_2$
$V=7.0_{10}$

B

首先看小数部分，最大为 $1+\frac{2^n-1}{2^n}$ ，要维持奇数又要尽量大，指数必须等于 $n$ 。
$E=n$
$M=1.1...1$
$f=0.1...1$
$V=2^{n+1}-1$

C

小数部分为 $0$ ，指数部分为最小的负数 $1-bias=2-2^{k-1}$ ，取倒数相当于对指数取相反数。
$E=1...101_2$
$M=0.0...0_2$
$f=0.0...0_2$
$V={2^{2^{k-1}-2}}$

2.86

$a^b$ 代表 $a$ 数字重复了 $b$ 次
$bias=2^{14}-1$

最小的正非规格化数

$0^1\ 0^{15}\ 0^1\ 0^{62}1^1 = 2^{-62-bias}$

最小的正规格化数

$0^1\ 0^{14}1^1\ 1^1\ 0^{63} = 2^{1-bias}$

最大的规格化数

$0^1\ 1^{14}0^1\ 1^1\ 1^{63} = 2^{bias}*(2-2^{-63})$

2.87

描述	Hex	M	E	V	D
$-0$	$0x0000$	$0$	$-14$	$-0$	$-0$
$最小的>0的值$	$0x4001$	$\frac{1025}{1024}$	$1$	$\frac{1025}{512}$	$2.00195$
$512$	$0x6000$	$1$	$9$	$512$	$512$
$最大的非规格化数$	$0x03ff$	$\frac{1023}{1024}$	$-14$	$\frac{1023}{2^{24}}$	$6.09756e-005$
$-∞$	$0xfc00$	$-$	$-$	$-∞$	$-∞$
$十六进制表示为3BB0的数$	$0x3bb0$	$\frac{123}{64}$	$-1$	$\frac{123}{128}$	$0.960938$

2.88

格式A		格式B
位	值	位	值
$1\ 01110\ 001$	$\frac{-9}{16}$	$1\ 0110\ 0010$	$\frac{-9}{16}$
$0\ 10110\ 101$	$208$	$0\ 1110\ 1010$	$208$
$1\ 00111\ 110$	$\frac{-7}{2^{10}}$	$1\ 0000\ 0111$	$\frac{-7}{2^{10}}$
$0\ 00000\ 101$	$\frac{5}{2^{17}}$	$0\ 0000\ 0000$	$0$
$1\ 11011\ 000$	$-2^{12}$	$1\ 1110\ 1111$	$-248$
$0\ 11000\ 100$	$768$	$0\ 1110\ 1111$	$248$

题目中说找最接近的，如果要舍入往正无穷舍入，感觉有点矛盾，这里按照最接近的做。
第四个和两个对答案的大哥的答案，三个人的答案两两不同，我觉得我是对的。

2.89

A

是，原理：会损失精度，但位模式一样，损失的形式也一样。

B

否，反例： $x==INT\_MIN \&\& y==INT\_MAX$

C

是，原理：虽然不满足结合律，但是数字都较小，精度能够保持。

D

不知道，算了一下发现三个 $int$ 乘起来远远大过 $double$ 能表示的精度，但是我用暴力跑了一部分大数据并没有发现反例，先留个空吧，有大佬找到反例的话请告诉我吧谢谢。

E

否，反例： $x==0 \&\& y==1$

2.90

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

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

    if (x < -149) // Too small. Return 0.0.
    {
        exp = 0;
        frac = 0;
    }
    else if (x < -126) // Denormalized result
    {
        exp = 0;
        frac = 1 << x + 149;
    }
    else if (x < 128) // Normalized result
    {
        exp = x + 127;
        frac = 0;
    }
    else // Too big. Return +oo
    {
        exp = 255;
        frac = 0;
    }

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

2.91

A

$11.0010010000111111011011_2$

B

$11.001001001...$

C

小数点后 $9$ 位开始

2.92

typedef unsigned float_bits;

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

float_bits float_negate(float_bits f)
{
    unsigned sign = f >> 31, exp = f >> 23 & 0xff, frac = f & 0x7fffff;
    if (exp == 0xff && frac)
        return f;
    return !sign << 31 | exp << 23 | frac;
}

bool test()
{
    for (unsigned i = 0; i < 0xffffffffu; i++)
        if (-u2f(i) != u2f(float_negate(i)))
        {
            printf("%x\n%x\n%x\n%f\n", i, f2u(-u2f(i)), float_negate(i), u2f(i));
            return false;
        }
    return true;
}

程序写的是没错，但在测试的过程中发现对 $NaN$ 取反会改变原数的二进制，所以导致不是所有的数都能这样转换，在搜索资料的过程中发现也有人提出了相同的问题，目前还不知道原理。

2.93

float_bits float_absval(float_bits f)
{
    unsigned sign = f >> 31, exp = f >> 23 & 0xff, frac = f & 0x7fffff;
    if (exp == 0xff && frac)
        return f;
    return 0 << 31 | exp << 23 | frac;
}

2.94

float_bits float_twice(float_bits f)
{
    unsigned sign = f >> 31, exp = f >> 23 & 0xff, frac = f & 0x7fffff;
    if (exp == 0xff)
        return f;
    if (exp == 0) // Denormalized
    {
        frac <<= 1;
    }
    else if (exp == 0xff - 1) // Normalized max
    {
        exp = 0xff;
        frac = 0;
    }
    else
    {
        exp++;
    }
    return sign << 31 | exp << 23 | frac;
}

由于 $IEEE$ 良好的设计，在非规格化阶段直接左移，在规格化阶段阶码直接加一即可。

2.95

float_bits float_half(float_bits f)
{
    unsigned sign = f >> 31, exp = f >> 23 & 0xff, frac = f & 0x7fffff;
    if (exp == 0xff)
        return f;
    if (exp <= 1)
    {
        unsigned carry = (frac & 0x3) == 0x3;
        frac = frac >> 1 | exp << 22;
        frac += carry ;
        exp = frac >> 23;
        frac = frac & 0x7fffff;
    }
    else
    {
        exp--;
    }
    return sign << 31 | exp << 23 | frac;
}

注意向偶数舍入的细节。

2.96

int float_f2i(float_bits f)
{
    unsigned sign = f >> 31, exp = f >> 23 & 0xff, frac = f & 0x7fffff;
    if (exp == 0x7fffff && frac) //NaN
        return 0;
    if (exp == 0x7ffff && !frac) //oo
        return INT_MIN;
    if (exp < 127) //  floats less then 1.0 or denormalized
        return 0;
    exp -= 127;
    if (exp > 30) // too big
        return INT_MIN;
    frac |= 1 << 23;
    frac = frac << 7 >> 30 - exp;
    return sign ? (~frac + 1) : frac;
}

本以为很难，结果一发就写对了，仔细分析好就不会错。
验证了所有的情况，全是一致的，完美模拟了 $float$ 向 $int$ 强制转换。

2.97

想了半天怎么只用位运算求出前导 $0$ 的数量，看了别人的答案发现都用了循环。。那还不如直接用 $\_\_builtin\_clz$ 吧。
不知道语言标准中丢失精度时是如何舍入的，这里写了两个版本，不带注释的是向 $0$ 舍入的，带注释的是向偶数舍入的。

float_bits float_i2f(int i)
{
    if (i == 0)
        return 0;
    unsigned sign = i >> 31;
    unsigned value = sign ? (~i + 1) : i;
    int first_bit_pos = 31 - __builtin_clz(value); //first bit position
    if (first_bit_pos <= 23)
    {
        unsigned exp = first_bit_pos + 127;
        value -= 1 << first_bit_pos;
        return sign << 31 | exp << 23 | value << 23 - first_bit_pos;
    }
    /*
    unsigned rounded_part = value & ((1 << first_bit_pos - 23) - 1);
    unsigned rounded_part_bitcount = first_bit_pos - 23;
    unsigned border = 1 << rounded_part_bitcount - 1;

    if ((rounded_part_bitcount == 1 && rounded_part == 1) || (rounded_part_bitcount > 1 && rounded_part > border))
    {
        value += border;
    }
    else if (rounded_part_bitcount == 2 && rounded_part == border)
    {
        if (value & 1 << rounded_part_bitcount)
            value += border;
    }
    */
    
    first_bit_pos = 31 - __builtin_clz(value);
    unsigned exp = first_bit_pos + 127;
    value -= 1 << first_bit_pos;
    return sign << 31 | exp << 23 | value >> first_bit_pos - 23;
}

代码比较复杂，可能哪里有错误，但大致是对的，至少不损失精度的范围内都通过了验证。

第2章 信息的表示和处理 作业