深入理解计算机系统 第2章 习题解析 Part1
之前学习CMU的15-213被劝退后，又通过华盛顿大学的Hardware Software Interface复习了书籍前面一部分的内容。两次学习后感受到《深入理解计算机系统》一书的重要性，所以决定细读该书，定个小目标，刷完该书的80%习题。由于工作后时间比较紧张，所以每周更新个5题左右。
电子书地址：
Chapter 2
58
只要理解大端小端的定义即可：
考虑一个$w$位的整数，其位表示为$[ x_{w-1},x_{w-2}, \cdots, x_{1}, x_{0}]$，其中$x_{w-1}$是最高有效位，$x_0$是最低有效位。
最低有效字节在最前面的方式，称为小端法(little endian)；最高有效字节在最前面的方式，称为大端法(big endian)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef unsigned char *byte_pointer;
int is_little_endian(){
int num = 0x100;
//小地址靠前
//小端:00,01
//大端:01,00
byte_pointer p = (byte_pointer) #
size_t size = sizeof(int);
if (p[0]){
return 0;
}else{
return 1;
}
}
int main(){
int res = is_little_endian();
if (res){
printf("This machine is little endian!\n");
}else{
printf("This machine is big endian!\n");
}
return 0;
}59
#include <stdio.h>
int calculate(int x, int y){
int mask = 0xFF;
int z = (x & mask) | (y & (~mask));
return z;
}
int main(){
int x = 0x89ABCDEF;
int y = 0x76543210;
int z = calculate(x, y);
printf("x:%x\n", x);
printf("y:%x\n", y);
printf("z:%x\n", z);
return 0;
}60
#include <stdio.h>
unsigned replace_byte (unsigned x, int i, unsigned char b){
int d = i * 8;
int mask = (0xFF << d);
//注意不能使用char类型
unsigned c = ((unsigned)b) << d;
unsigned y = (x & (~mask)) | c;
return y;
}
int main(){
unsigned x = 0x12345678;
unsigned y = 0xAB;
for (int i = 0; i < 4; i++){
printf("%x\n", replace_byte(x, i, y));
}
return 0;
}61
#include <stdio.h>
int expression(int x){
int w = sizeof(int) << 3;
//计算结果
int mask1 = !(x ^ (-1));
int mask2 = !(x ^ 0);
int mask3 = !((x & 0xFF) ^ 0xFF);
int mask4 = !((x & (0xFF << (w - 8))) ^ 0);
int res = mask1 | mask2 | mask3 | mask4;
return res;
}
int f(int x){
int w = sizeof(int) << 3;
int y = x & 0xFF;
int z = (x >> (w - 8)) & 0xFF;
if (x == 0xFFFFFFFF){
return 1;
}else if (x == 0){
return 1;
}else if (y == 0xFF){
return 1;
}else if (z == 0){
return 1;
}else{
return 0;
}
}
void test(){
int start = -10000;
int end = 10000;
//记录结果
int flag = 1;
for (int i = start; i <= end; i++){
if (expression(i) != f(i)){
printf("Wrong answer for %x!\n", i);
flag = 0;
break;
}
}
if (flag){
printf("Test sucess!\n");
}else{
printf("Test fail!\n");
}
return;
}
int main(){
test();
return 0;
}62
利用-1的逻辑右移等于-1即可：
#include <stdio.h>
int int_shifts_are_arithmetic(){
int x = -1;
int y = x >> 1;
//判断是否相等
int res = !(x ^ y);
return res;
}
int main(){
int res = int_shifts_are_arithmetic();
if (res){
printf("Arithmetic right shift!\n");
}else{
printf("Logic right shift!\n");
}
return 0;
}63
srl函数需要将前k个比特设为0，所以需要如下形式的mask：
注意k=0时要特殊处理。
sra将前k个比特设为符号位，注意k=0时也要特殊处理。
这里使用如下技巧，给定s(0或1)，如何生成
方法如下：
//s=0时mask=1111，否则为1110
int mask = ~s;
//s=0时mask=0000，否则为1111
mask = mask + 1;代码如下：
#include <stdio.h>
unsigned srl(unsigned x, int k){
/* Perform shift arithmetically */
unsigned xsra = (int) x >> k;
//w需要特殊处理
//int比特数
int w = sizeof(int) << 3;
//k=0时mask=0，否则为1
int mask = !(!k);
//k=0时mask=1111，否则为1110
mask = ~mask;
//k=0时mask=0000，否则为1111
mask = mask + 1;
//生成1...10...0
mask = mask << (w - k);
//生成0...01...1
mask = ~mask;
//生成结果
xsra = xsra & mask;
return xsra;
}
int sra(int x, int k){
/* Perform shift logically */
unsigned xsrl = (unsigned) x >> k;
//int比特数
int w = sizeof(int) << 3;
//获得符号位
int s = x & (1 << (w - 1));
//根据符号位生成mask
s = !(!s);
//k=0时s=0
s = s & (!(!k));
//取反,x<0时为1110,x>=0时为1111,k=0时为1111
int mask = ~s;
//x<0时为1111,x>=0时为0000,k=0时为0000
mask = mask + 1;
//移位,生成ssss0000
mask = mask << (w - k);
//生成结果
xsrl = xsrl | mask;
return xsrl;
}
void test_srl(){
int w = sizeof(int) << 3;
int start = -100;
int end = 100;
int flag = 1;
for (int i = start; i <= end; i++){
if (!flag){
break;
}
for (int k = 0; k < w; k++){
unsigned res = (unsigned)i >> k;
unsigned ans = srl(i, k);
if (ans != res){
printf("Wrong answer for %d!\n", i);
flag = 0;
break;
}
}
}
if (flag){
printf("srl test succeed.\n");
}else{
printf("srl test fail.");
}
}
void test_sra(){
int w = sizeof(int) << 3;
int start = -1000;
int end = 1000;
int flag = 1;
int f2 = 1;
for (int i = start; i <= end; i++){
if (!f2){
break;
}
for (int k = 0; k < w; k++){
int res = i >> k;
int ans = sra(i, k);
if (ans != res){
printf("Wrong answer for %d!\n", i);
f2 = 0;
break;
}
}
}
if (f2){
printf("sra test succeed.\n");
}else{
printf("sra test fail.");
}
}
int main(){
test_srl();
test_sra();
return 0;
}64
#include <stdio.h>
/* Return 1 when any odd bit of x equals 1; 0 otherwise.
Assume w=32 */
int any_odd_one (unsigned x){
//A=1010,这里假设最低位索引为0
int mask = 0xAAAAAAAA;
int res = x & mask;
res = !!(res);
return res;
}
int any_odd_one_(unsigned x){
int res = 0;
int i = 0;
while (x != 0){
int d = x % 2;
x /= 2;
if (i && d){
res = 1;
break;
}
i = 1 - i;
}
return res;
}
void test(){
int start = -10000;
int end = 10000;
int flag = 1;
for (int i = start; i <= end; i++){
if (any_odd_one(i) != any_odd_one_(i)){
flag = 0;
break;
}
}
if (flag){
printf("Test pass!\n");
}else{
printf("Test fail!\n");
}
}
int main(){
test();
return 0;
}65
这里利用如下技巧：
假设
记$T(x)$为$x$中$1$的个数的奇偶性，那么很容易验证
注意到
所以我们可以得到如下代码
//只考虑16位
int a1 = (x ^ (x >> 16)) & 0xFFFF;
//只考虑8位
int a2 = (a1 ^ (a1 >> 8)) & 0xFF;
//只考虑4位
int a3 = (a2 ^ (a2 >> 4)) & 0xF;
//只考虑2位
int a4 = (a3 ^ (a3 >> 2)) & 0x11;
//生成结果
int res = (a4 ^ (a4 >> 1)) & 1;这样一共需要15次运算，显然超过了要求。
注意到我们每次只要考虑低位，可以忽略高位，所以前几步可以不需要&的操作，于是得到如下代码：
/* Return 1 when x contains an odd number of 1s;0 otherwise.
Assume w=32 */
#include <stdio.h>
int odd_ones(unsigned x){
//只考虑16位
int a1 = (x ^ (x >> 16));
//只考虑8位
int a2 = (a1 ^ (a1 >> 8));
//只考虑4位
int a3 = (a2 ^ (a2 >> 4));
//只考虑2位
int a4 = (a3 ^ (a3 >> 2));
//生成结果
int res = (a4 ^ (a4 >> 1)) & 1;
return res;
}
int odd_ones_(unsigned x){
int res = 0;
int cnt = 0;
while (x != 0){
cnt += x % 2;
x /= 2;
}
return cnt % 2;
}
void test(){
int start = -10000;
int end = 10000;
int flag = 1;
for (int i = start; i <= end; i++){
if (odd_ones(i) != odd_ones_(i)){
flag = 0;
break;
}
}
if (flag){
printf("Test pass!\n");
}else{
printf("Test fail!\n");
}
}
int main(){
test();
return 0;
}总结
63,65比较有意思，可以多回顾几遍。
另外这里总结几个常用技巧。
技巧1
if (a == b){
return 1;
}else{
return 0;
}等价于
return !(a ^ b);技巧2
给定s(0或1)，如何生成
方法如下：
//s=0时mask=1111，否则为1110
int mask = ~s;
//s=0时mask=0000，否则为1111
mask = mask + 1;本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Doraemonzzz！
相关推荐
评论
ValineLivere