文档章节

csapp 习题 - 如何实现异或 exclusive-or

ylme
 ylme
发布于 01/20 23:54
字数 575
阅读 8
收藏 0
Lua

阅读 csapp v3 时,练习题 2.13 很有意思。练习题描述如下。

位设置是对于参数 mask 中每一个为 1 的位,那么参数 x 中相应位则被设置为 1 ;位清除是对于参数 mask 中每一个为 1 的位,那么参数 x 中相应位则被设置为 0 。假设有两个函数 bis 和 bic 来实现位设置和位清除,请使用这两个函数实现两个数的异或结果。

小提示:可以使用的位运算是

local function bis(x, mask)
	return x | mask
end

local function bic(x, mask)
	return x & ~mask
end

什么是异或呢?异或就是两个值中,至少有一个为真,但不全为真,那么结果就是真,否则结果就是假。对于两个二进制位,至少有一个位为 1 但不全为 1,那么结果就是 1,否则结果是 0 。
也就是说只有 (1 异或 0) 或者 (0 异或 1) 结果才为 1,其余结果都为 0 。只要两个位不相同,那么结果就是 1 。所以问题变成了如何判断两个位不同。
运算要求两个位都是 1 时,结果才是 1,因此 1 & ~0 结果是 1 而 ~0 & 1 结果也是 1,这做实现了两个位不同,而结果是 1 。由于存在 1 & ~0~0 & 1,因此异或运算可被拆分为 (1 & ~0) | (~0 & 1) 。推广成 (x & ~y) | (~x & y)

经过分析后,发现完全可以代入上面的函数。于是实现异或的代码如下。

local function exor(x, y)
	return bis(bic(x, y), bic(y, x))
end

完整的测试用例 Lua 代码如下。

local function bis(x, mask)
	return x | mask
end

local function bic(x, mask)
	return x & ~mask
end

local function exor(x, y)
	return bis(bic(x, y), bic(y, x))
end

local x, y = 0x12345678, 0x87654321
assert(exor(x, y) == x ~ y

参考内容

  • 深入理解计算机操作系统 - 习题 2.13

© 著作权归作者所有

共有 人打赏支持
ylme
粉丝 12
博文 42
码字总数 42711
作品 0
广州
程序员
私信 提问
c语言setbits,invert

k&r习题2-6,setbits(x,p,n,y),将x中从第p位开始的n个二进制位设置为y中最右边n位的值,x的其余各位保持不变。 #include<stdio.h> unsigned setbits(unsigned x, int p, int n,unsigned y){...

好铁
2014/09/10
350
0
如何通过自学找到一份开发的工作?

点击上方“程序人生”,选择“置顶公众号” 第一时间关注程序猿(媛)身边的故事 注:本文转自知乎 origin 的回答,发布已获原作者授权。 https://www.zhihu.com/question/26421707/answer/5...

csdnsevenn
2018/01/10
0
0
解析 word 读取 内容的 好的思路

目前有一个上传习题的需求: 目前的实现方案是:按照我们提供的word、excel模板, 按照关键字解析文档中的单选、多选、判断、并提取习题,选项、答案、解析 关键字段, 目前存在一个问题:w...

kkkwoai
2015/08/25
316
2
感受异或的神奇

什么是异或? Wikipedia的解释: 在逻辑学中,逻辑算符异或(exclusive or)是对两个运算元的一种逻辑析取类型,符号为 XOR 或 EOR 或 ⊕(编程语言中常用^)。但与一般的逻辑或不同,异或算...

囚兔
2016/04/29
64
0
一道逻辑题 - 我拿走了哪个数

有 1 到 10000 共 10000 个数,如果我从中随机拿走一个数,你如何知道我拿走了哪个? 相信很多人看过这道题,并知道答案,这几天和同事聊天时听到了这个问题,因为有过自己的思考过程,不妨记...

justjavac
2014/09/16
177
4

没有更多内容

加载失败,请刷新页面

加载更多

[Android O] Camera 服务启动流程简析

前言 去年正式进入框架组的时候,啥也不会,瞎jb分析了一通 Android N 上面的 Camera 相关流程。其实基本上都是跟着别人的分析日志看代码,然后按照自己的理解记了些笔记而已。 不过当时感觉...

天王盖地虎626
3分钟前
0
0
MySql 常用函数

一、字符串函数 contact(s1,s2,s3...) : 把传入的参数连接成字符串 mysql> select concat('a','b','c'); +---------------------+ | concat('a','b','c') | +---------------------+ | abc |......

嘴角轻扬30
4分钟前
1
0
通过Spark进行ALS离线和Stream实时推荐

ALS简介 ALS是alternating least squares的缩写 , 意为交替最小二乘法;而ALS-WR是alternating-least-squares with weighted-λ -regularization的缩写,意为加权正则化交替最小二乘法。该方...

东风飘兮神灵雨
5分钟前
1
0
Twemproxy增加或剔除Redis节点后对数据有何影响

本篇文章,Twemproxy增加或剔除Redis节点后对数据的影响是接着”通过Twemproxy代理Redis数据分片方案“这篇文章写的。最好还要懂一致性哈希(ketama)的原理。 上一篇文章中,我们配置了一个...

linuxprobe16
8分钟前
1
0
Java魔法类——Unsafe应用解析

前言 Unsafe是位于sun.misc包下的一个类,主要提供一些用于执行低级别、不安全操作的方法,如直接访问系统内存资源、自主管理内存资源等,这些方法在提升Java运行效率、增强Java语言底层资源...

微笑向暖wx
8分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部