2.55
//show_bytes.cpp
#include<stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len) {
size_t i;
for(int i = 0; i < len; i++) printf(" %.2x", start[i]);
printf("\n");
}
void show_int(int x) {
show_bytes((byte_pointer) &x, sizeof(int));
}
void show_float(float x) {
show_bytes((byte_pointer) &x, sizeof(float));
}
void show_pointer(void *x) {
show_bytes((byte_pointer) &x, sizeof(void *));
}
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);
}
int main() {
int test_num = 666;
test_show_bytes(test_num);
return 0;
}输出为
9a 02 00 00
00 80 26 44
cc fd 61 00 00 00 00 00而整数 666 的十六进制表示为 29A，则我的机器为小端法。
2.56
改变 test_num 的值后的运行结果如下。
//The val of test_num is : 114.
72 00 00 00
00 00 e4 42
cc fd 61 00 00 00 00 00//The val of test_num is : 514.
02 02 00 00
00 80 00 44
cc fd 61 00 00 00 00 00//The val of test_num is : 114514.
52 bf 01 00
00 a9 df 47
cc fd 61 00 00 00 00 002.57
完善后如下
//show_bytes.cpp
#include<stdio.h>
typedef unsigned char *byte_pointer;
void show_bytes(byte_pointer start, size_t len) {
size_t i;
for(int i = 0; i < len; i++) printf(" %.2x", start[i]);
printf("\n");
}
void show_int(int x) {
show_bytes((byte_pointer) &x, sizeof(int));
}
void show_float(float x) {
show_bytes((byte_pointer) &x, sizeof(float));
}
void show_pointer(void *x) {
show_bytes((byte_pointer) &x, sizeof(void *));
}
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));
}
void test_show_bytes(int val) {
int ival = val;
float fval = (float) ival;
int *pval = &ival;
short sval = (short) ival;
long lval = (long) ival;
double dval = (double) ival;
show_int(ival);
show_float(fval);
show_pointer(pval);
show_short(sval);
show_long(lval);
show_double(dval);
}
int main() {
int test_num = 666;
printf("//The val of test_num is : %d.\n",test_num);
test_show_bytes(test_num);
return 0;
}运行结果如下
//The val of test_num is : 666.
9a 02 00 00
00 80 26 44
bc fd 61 00 00 00 00 00
9a 02
9a 02 00 00
00 00 00 00 00 d0 84 402.58
#include<bits/stdc++.h>
using namespace std;
typedef unsigned char *byte_pointer;
bool is_little_endian() {
int test_num = 0xff;
byte_pointer start = (byte_pointer) &test_num;
return start[0] == 0xff;
}
int main() {
if(is_little_endian()) cout<<1<<endl;
else cout<<0<<endl;
return 0;
}我的机器为小端法机器，运行结果为 1 。
2.59
考虑掩码的性质容易得答案即为
(x & 0xff) | (y & ~0xff)代码如下
#include<bits/stdc++.h>
using namespace std;
int f(int x,int y) {
return (x & 0xff) | (y & ~0xff);
}
int main() {
int x = 0x89ABCDEF, y = 0x76543210;
cout<<hex<<f(x,y)<<endl;
return 0;
}2.60
#include<bits/stdc++.h>
using namespace std;
unsigned replace_byte(unsigned x, int i, unsigned char b) {
return (x & ~(0xff << (i << 3))) | (b << (i << 3));
}
int main() {
cout<<hex<<"0x"<<replace_byte(0x12345678, 2, 0xAB)<<endl;
cout<<hex<<"0x"<<replace_byte(0x12345678, 0, 0xAB)<<endl;
}2.61
bool A(int x) {
return !~x;
}
bool B(int x) {
return !x;
}
bool C(int x) {
return !~(x & 0xff);
}
bool D(int x) {
int shift_val = (sizeof(int) - 1) << 3;
return !(x >> shift_val & 0xff);
}
2.62
#include<bits/stdc++.h>
using namespace std;
bool int_shifts_are_arithmetic() {
int x = -1;
return !((-1 >> 1) ^ -1);
}
int main() {
cout<<int_shifts_are_arithmetic()<<endl;
return 0;
}2.63
srl 较简单，直接利用掩码性质取后 w-k 位即可。
sra 想了很长时间，由于只有当第 w-1 位为 1 时才需要处理，而且需要是表达式的形式，所以需要利用 int 类型的 -1 即为 0xFFFFFFFF，所以 x & -1 = x的性质。当第 w-1 位为 1 时，掩码不变；为 0 时，掩码为 0，据此构造表达式实现对掩码的修改。答案用 xsrl 或上掩码即可。
#include<bits/stdc++.h>
using namespace std;
unsigned srl(unsigned x, int k) {
/* Perform shift arithmetically */
unsigned xsra = (int) x >> k;
int w = 8 * sizeof(int);
int mask = -1 << (w - k);
return ~mask & xsra;
}
int sra(int x, int k) {
/* Perform shift logically */
int xsrl = (unsigned) x >> k;
int w = 8 * sizeof(int);
int mask = -1 << (w - k);
int y = 1 << (w - 1);
mask &= !(x & y) - 1;
return xsrl | mask;
}
int main() {
cout<<hex<<"0x"<<srl(0xabcdef12,8)<<endl;
cout<<hex<<"0x"<<sra(0xabcdef12,8)<<endl;
return 0;
}输出如下
0xabcdef
0xffabcdef2.64
int any_odd_one(unsigned x) {
return !!(0xAAAAAAAA & x);
}2.65
把 x 看成 w 个 0 或 1 。
那么如果有奇数个 1 ，这 w 个数的异或和应为 1 。
考虑每次向右移动一半进行异或，最后第 0 位上的值即为结果。
#include<bits/stdc++.h>
using namespace std;
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 test_num_1 = 0xFFFFFFFF;
int test_num_2 = 0x77777770;
cout<<odd_ones(test_num_1)<<" "<<odd_ones(test_num_2);
return 0;
}输出为
0 12.66
和上题思路差不多。
每次向右移动后与原数或一下，最后会形成一个形如 00....1111 的数，把这个数向右移一位后加 1 即为结果。
#include<bits/stdc++.h>
using namespace std;
int odd_ones(unsigned x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return (x >> 1) + 1;
}
int main() {
int test_num_1 = 0xFFFFFFFF;
int test_num_2 = 0x01ABCDEF;
cout<<hex<<odd_ones(test_num_1)<<" "<<odd_ones(test_num_2);
return 0;
} 输出为
80000000 10000002.67
A
左移动 32 位，大于等于了位数，是未定义行为。
B
#include<bits/stdc++.h>
using namespace std;
int bad_int_size_is_32() {
int set_msb = 1 << 31;
int beyond_msb = set_msb << 1;
return set_msb && !beyond_msb;
}
int main() {
cout<<bad_int_size_is_32()<<endl;
return 0;
}C
#include<bits/stdc++.h>
using namespace std;
int bad_int_size_is_32() {
int set_msb = 1 << 15 << 15 <<1;
int beyond_msb = set_msb << 1;
return set_msb && !beyond_msb;
}
int main() {
cout<<bad_int_size_is_32()<<endl;
return 0;
}2.68
#include<bits/stdc++.h>
using namespace std;
int lower_one_mask(int n) {
return (1 << (n-1) << 1) -1;
}
int main() {
int test_num = 32;
cout<<hex<<"0x"<<lower_one_mask(test_num)<<endl;
return 0;
}输出为
0xffffffff2.69
#include<bits/stdc++.h>
using namespace std;
unsigned rotate_left(unsigned x,int n) {
int w = sizeof(int) << 3;
unsigned y = x >> (w - n);
return x << n | y;
}
int main() {
int test_num = 0x12345678;
int test_n_1 = 4,test_n_2 = 20;
cout<<hex<<"0x"<<rotate_left(test_num, test_n_1)<<endl;
cout<<hex<<"0x"<<rotate_left(test_num, test_n_2)<<endl;
return 0;
}输出为
0x23456781
0x678123452.70
若数 x 可以被表示成一个 n 位的补码，则其第 n-1 到 w-1 位为全 0 或全 1 。
#include<bits/stdc++.h>
using namespace std;
int fits_bits(int x, int n) {
int y = x >> (n - 1);
return !y | !~y;
}
int main() {
int test_num = 0x3f;
int test_n_1 = 6,test_n_2 = 7;
cout<<fits_bits(test_num, test_n_1)<<" "<<fits_bits(test_num, test_n_2)<<endl;
return 0;
}输出为
0 12.71
A
并没有实现符号扩展
B
先左移再右移，利用算术右移性质
#include<bits/stdc++.h>
using namespace std;
typedef unsigned packet_t;
int xbyte(packet_t word, int bytenum) {
return (int)word << ((3 - bytenum) << 3) >> 24;
}
int main() {
packet_t test_num = 0xFEDCBA12;
cout<<hex<<xbyte(test_num, 0)<<" "<<xbyte(test_num, 1)<<" "<<xbyte(test_num, 2)<<" "<<xbyte(test_num, 3)<<endl;
return 0;
}输出为
12 ffffffba ffffffdc fffffffe2.72
A
sizeof 运算符返回类型为 size_t 的值，所以一直大于等于零。
B
强制类型转换一下。
2.73
正溢出：正+正=负
负溢出：负+负=正
#include<bits/stdc++.h>
using namespace std;
int saturating_add(int x, int y) {
int w = sizeof(int) << 3;
int TMAX = (1 << (w - 1)) -1;
int TMIN = 1 << (w - 1);
int sum = x + y;
int sign_x = x >> (w - 1);
int sign_y = y >> (w - 1);
int sign_sum = sum >> (w - 1);
int overflow_p = ~sign_x & ~sign_y & sign_sum;
int overflow_n = sign_x & sign_y & ~sign_sum;
return (overflow_p & TMAX) | (overflow_n & TMIN) | (~(overflow_p | overflow_n) & sum);
}
int main() {
int test_x = 0x3FFFFFFF, test_y = 0x7FFFFFFF;
cout<<saturating_add(test_x, 0)<<" "<<saturating_add(test_x, test_y)<<" "<<saturating_add(-test_x, -test_y)<<endl;
return 0;
}输出为
1073741823 2147483647 -21474836482.74
与上题类似。
#include<bits/stdc++.h>
using namespace std;
int tsub_ok(int x, int y) {
int w = sizeof(int) << 3;
int diff = x - y;
int sign_x = x >> (w - 1);
int sign_y = y >> (w - 1);
int sign_diff = diff >> (w - 1);
int overflow_p = ~sign_x & sign_y & sign_diff;
int overflow_n = sign_x & ~sign_y & ~sign_diff;
return ~(overflow_p | overflow_n) & 1;
}
int main() {
int test_x = 0x7FFFFFFF, test_y = 0x80000000;
cout<<tsub_ok(test_x, -1)<<" "<<tsub_ok(test_y, 1)<<" "<<tsub_ok(test_y, -test_x)<<endl;
return 0;
}输出为
0 0 12.75
按照书上的推导过程来就行，容易推得答案为
signed_high_prod(x, y) + x * (y >> (w - 1)) + y * (x >> (w - 1))代码：
#include<bits/stdc++.h>
using namespace std;
int w = sizeof(int) << 3;
int signed_high_prod(int x, int y) {
int64_t res = (int64_t) x * y;
return res >> w;
}
unsigned unsigned_high_prod(unsigned x, unsigned y) {
return signed_high_prod(x, y) + x * (y >> (w - 1)) + y * (x >> (w - 1));
}
int main() {
int test_x = 0x7FFFFFFF, test_y = 0x80;
cout<<hex<<" "<<unsigned_high_prod(test_x, test_y)<<endl;
return 0;
}输出为
3f2.77
A
(x << 4) + xB
x - (x << 3)C
(x << 6) - (x << 2)D
(x << 4) - (x << 7)