深入理解计算机系统之读书笔记五
【摘要】 2.1.7 布尔代数简介与、或、按位取反、异或运算不再重述。关于布尔代数和布尔环的更多内容：有2^w个长度为w的位向量。当考虑长度为w的位向量上的^、&和~运算时，会得到一种不同的数学形式，我们称之为布尔环。布尔环与整数运算有很多相同的属性。整数的加法逆元，对应的是^的逆元是本身。而且具有结合律。 用位向量[aw-1,...,a1,a0]编码任何子集A{0,1，...，w-1}，比如用位...
2.1.7 布尔代数简介
与、或、按位取反、异或运算不再重述。
关于布尔代数和布尔环的更多内容：
有2^w个长度为w的位向量。当考虑长度为w的位向量上的^、&和~运算时，会得到一种不同的数学形式，我们称之为布尔环。布尔环与整数运算有很多相同的属性。整数
的加法逆元，对应的是^的逆元是本身。而且具有结合律。 用位向量[aw-1,...,a1,a0]编码任何子集A{0,1，...，w-1}，比如用位向量a=[01101001]表示集合{0,3,5,6}。
在大量实际应用中，我们都可用位向量来对集合编码。
练习题 2.9
习题1，所谓的补就是按位取反运算。
2.1.8 C语言中的位运算
位运算包含了&(与)、|(或)、^(异或)、~(按位取反)。其中异或的物理意义是去共（去除公交的部分），a^b等价于a|b - a&b。
通过异或来进行两个数的交换。注意一点，要保证a和b不能相等，即代码如下所示，使用了c++中的引用，实参为直接为int类型变量即可：
void swap(int &a, int &b){
if (a != b){
a = a^b;
b = a^b;
a = a^b;
}
}
练习题 2.10
void inplace_swap(int *x, int *y) {
*y = *x ^ *y; /* Step 1 */
*x = *x ^ *y; /* Step 2 */
*y = *x ^ *y; /* Step 3 */
}
练习题 2.11
A 最后一次循环，first超过了last，也就是first等于k+1，而last等于k。
B 因为对两个相同地址的数取异或运算，结果都为0
C first<=last，修改为first<last即可。
~0可以表示全为1的掩码。表示的是全机器长。所以可以实现跨平台，可移植。
练习题 2.12
A x&0xFF
B x^(~0xFF) 和0异或不变，和1异或取反。
C x| 0xFF
练习题 2.13
使用 bis 指令，这种修改就是在 m 为 1 的每个位置上，将 z 对应的位设置为 1。使用 bic指令，这种修改就是在 m 为 1 的每个位置，将 z 对应的位设置为 0。int bool_or(int x, int y) {
int result = bis(x,y);
return result;
}
int bool_xor(int x, int y) {
int result = bit(bis(x,y), bis(y,x));
return result;
}
2.1.9 C语言中的逻辑运算
a&&b，如果都为非0值，则为1。&&和||还有~的结果，也就是逻辑运算的结果不是0就是1。
练习题 2.15
x==y，可以用x^y来代替。
2.1.9 C语言中的移位运算
左移只有一种。右移的话分为算数右移和逻辑右移。对于一般情况而言，移动超过全字长，则按照移位数%全字长的结果来右移。另外，大多数都为算数右移，也就是空缺
位由符号位来填补。优先级而言的话，移位运算小于算数运算，比如int mid = left + (right-left)>>1;这就是错误的，应该是int mid = left + ((right-left)>>1);如何使用Python来计算逻
辑右移呢。可以先把int类型转换成字节码。
import struct
a = -12
bytes = struct.pack('i', a)
a = struct.unpack('I', bytes)此时就把a转换成了逻辑数，就可以进行右移运算了（相当于逻辑右移）。
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）