深入理解计算机系统(第三版)作业题答案(第二章)

#include int int_shifts_are_arithmetic() { int i = -1; return (i >> 1) == -1;}int main(void) { printf("%d", int_shifts_are_arithmetic());}2.63

#include #include int int_size_is_32() { int set_msb = 1 << 31; int beyond_msb = set_msb << 1; return set_msb && !beyond_msb;}int int_size_is_32_for_16bit() { int set_msb = 1 << 15 << 15 << 1; int beyond_msb = set_msb << 1; return set_msb && !beyond_msb;}int main(void) { printf("1: %lu n", sizeof(1)); printf("32: %d n", int_size_is_32()); printf("16: %d n", int_size_is_32_for_16bit());}2.68#include #include int lower_one_mask(int n) { int w = sizeof(int) << 3; return (unsigned)-1 >> (w - n);}int main(void) { assert(lower_one_mask(6) == 0x3F); assert(lower_one_mask(17) == 0x1FFFF); assert(lower_one_mask(32) == 0xFFFFFFFF); return 0;}2.69

#include #include #include #include void copy_int(int val, void *buf, int maxbytes) { if (maxbytes >= (int)sizeof(val)) { memcpy(buf, (void *)&val, sizeof(val)); }}int main() { int maxbytes = sizeof(int) * 10; void *buf = malloc(maxbytes); int val; val = 0x12345678; copy_int(val, buf, maxbytes); assert(*(int *)buf == val); val = 0x11111111; val = 0xAABBCCDD; copy_int(val, buf, 0); assert(*(int *)buf != val); return 0;}2.73

int64_t mul = (int64_t) x * y; return mul >> 32;}unsigned unsigned_high_prod(unsigned x, unsigned y) { /* TODO calculations */ int sig_x = x >> 31; int sig_y = y >> 31; int signed_prod = signed_high_prod(x, y); return signed_prod + x * sig_y + y * sig_x;}/* a theorically correct version to test unsigned_high_prod func */unsigned another_unsigned_high_prod(unsigned x, unsigned y) { uint64_t mul = (uint64_t) x * y; return mul >> 32;}int main(int argc, char* argv[]) { unsigned x = 0x12345678; unsigned y = 0xFFFFFFFF; assert(another_unsigned_high_prod(x, y) == unsigned_high_prod(x, y)); return 0;}2.76

#include #include #include #include #include void *another_calloc(size_t nmemb, size_t size) { if (nmemb == 0 || size == 0) { return NULL; } size_t buff_size = nmemb * size; if (nmemb == buff_size / size) { void *ptr = malloc(buff_size); memset(ptr, 0, buff_size); return ptr; } return NULL;}int main() { void *p; p = another_calloc(0x1234, 1); assert(p != NULL); free(p); p = another_calloc(SIZE_MAX, 2); assert(p == NULL); free(p); return 0;}2.77

* lm3d4 = lm3 >> 2 * * when x < 0, rounding to zero acts like divide_power2 in 2.78 * * bias = 0x3 // (1 << 2) - 1 * lm3d4 = (lm3 + bias) >> 2 */int threeforths(int x) { int is_neg = x & INT_MIN; int f = x & ~0x3; int l = x & 0x3; int fd4 = f >> 2; int fd4m3 = (fd4 << 1) + fd4; int lm3 = (l << 1) + l; int bias = (1 << 1) + 1; (is_neg && (lm3 += bias)); int lm3d4 = lm3 >> 2; return fd4m3 + lm3d4;}int main(int argc, char* argv[]) { assert(threeforths(8) == 6); assert(threeforths(9) == 6); assert(threeforths(10) == 7); assert(threeforths(11) == 8); assert(threeforths(12) == 9); assert(threeforths(-8) == -6); assert(threeforths(-9) == -6); assert(threeforths(-10) == -7); assert(threeforths(-11) == -8); assert(threeforths(-12) == -9); return 0;}2.81

#include #include #include int A(int k) { return -1 << k;}int B(int k, int j) { return ~A(k) << j;}int main(int argc, char* argv[]) { assert(A(8) == 0xFFFFFF00); assert(B(16, 8) == 0x00FFFF00); printf("%d", -INT_MIN); return 0;}2.82/* * 2.82.c */#include #include #include #include "lib/random.h"// 强调的是这个推导的过程/* broken when x is INT_MIN */int A(int x, int y) { return (x < y) == (-x > -y);}/* * right * * ((x + y) << 4) + y - x * => * x << 4 - x + y << 4 + y * =>

* => * x*16 - x + y*16 + y * whether overflow or not, => * x*15 + y*17 */int B(int x, int y) { return ((x + y) << 4) + y - x == 17 * y + 15 * x;}/* * right * * ~x + ~y + 1 * => * ~x + 1 + ~y + 1 - 1 * => * -x + -y - 1 * => * -(x + y) - 1 * => * ~(x + y) + 1 - 1 * => * ~(x + y) */int C(int x, int y) { return ~x + ~y + 1 == ~(x + y);}/* * right * * (ux - uy) == -(unsigned) (y - x) * => * -(ux - uy) == (unsigned) (y - x) * => * (ux - uy) == (unsigned) (x - y) */int D(int x, int y) { unsigned ux = (unsigned) x; unsigned uy = (unsigned) y; return (ux - uy) == -(unsigned) (y - x);}/* * right * * x >> 2 << 2 * => * x & ~0x3 * => * x - num(00/01/10/11) * => * ((x >> 2) << 2) <= x */int E(int x, int y) { return ((x >> 2) << 2) <= x;}int main(int argc, char* argv[]) { init_seed(); int x = random_int(); int y = random_int(); assert(!A(INT_MIN, 0)); assert(B(x, y));

/* * 2.89.c */#include #include #include #include "lib/random.h"/* * most important thing is that all double number come from ints *//* right */int A(int x, double dx) { return (float)x == (float)dx;}/* wrong when y is INT_MIN */int B(int x, double dx, int y, double dy) { return dx-dy == (double)(x-y);}/* right */int C(double dx, double dy, double dz) { return (dx+dy)+dz == dx+(dy+dz);}/* * wrong * * FIXME I don't know what conditions cause false */int D(double dx, double dy, double dz) { return (dx*dy)*dz == dx*(dy*dz);}/* wrong when dx != 0 and dz == 0 */int E(double dx, double dz) { return dx/dx == dz/dz;}int main(int argc, char* argv[]) { init_seed(); int x = random_int(); int y = random_int(); int z = random_int(); double dx = (double)x; double dy = (double)y; double dz = (double)z; printf("%x %x %xn", x, y, z); assert(A(x, dx)); assert(!B(0, (double)(int)0, INT_MIN, (double)(int)INT_MIN)); assert(C(dx, dy, dz)); /* magic number, brute force attack */ assert(!D((double)(int)0x64e73387, (double)(int)0xd31cb264, (double)(int)0xd22f1fcd)); assert(!E(dx, (double)(int)0)); return 0;}2.90

#include #include typedef unsigned float_bits;float_bits float_negate(float_bits f) { unsigned sig = f >> 31; unsigned exp = f >> 23 & 0xFF; unsigned frac = f & 0x7FFFFF; int is_nan = (exp == 0xFF && frac != 0); if (is_nan) { return f; } return ~sig << 31 | exp << 23 | frac;}int main() { printf("%u", float_negate(32.0)); assert(float_negate(32.0) == -32.0); return 0;}2.93#include #include typedef unsigned float_bits;float_bits float_absval(float_bits f) { 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;}int main() { printf("%un", float_absval(32.0)); return 0;}

if ((i & INT_MIN) != 0) { return 32; } unsigned u = (unsigned)i; int length = 0; while (u >= (1< 0x00000007 * 16 => 0x0000FFFF */unsigned bits_mask(int l) { return (unsigned) -1 >> (32-l);}/* * Compute (float) i */float_bits float_i2f(int i) { unsigned sig, exp, frac, rest, exp_sig /* except sig */, round_part; unsigned bits, fbits; unsigned bias = 0x7F; if (i == 0) { sig = 0; exp = 0; frac = 0; return sig << 31 | exp << 23 | frac; } if (i == INT_MIN) { sig = 1; exp = bias + 31; frac = 0; return sig << 31 | exp << 23 | frac; } sig = 0; /* 2's complatation */ if (i < 0) { sig = 1; i = -i; } bits = bits_length(i); fbits = bits - 1; exp = bias + fbits; rest = i & bits_mask(fbits); if (fbits <= 23) { frac = rest << (23 - fbits); exp_sig = exp << 23 | frac; } else { int offset = fbits - 23; int round_mid = 1 << (offset - 1); round_part = rest & bits_mask(offset); frac = rest >> offset;

}// printf("E=%d,frac=%xn", E, frac); return (sign << 31 | exp << 23) + frac;}void test_i2f(){ unsigned UMAX = ~0; int before ; float after; float correct; int valid; for (unsigned u = 0; u < UMAX ; u++) { before = (int)u; after = u2f(float_i2f(before)); correct = (float)before; valid = after == correct; if (!valid) printf("invalid! u=%x,b=%d,a=%f,c=%fn", u, before, after, correct); } printf("success!n");}总结代码已上传github如有错误之处，还请指正啊。。。