111qqz的小窝

老年咸鱼冲锋!

【施工完成】CSAPP data lab

CSAPP第二章的内容以前组成原理基本都学过…所以就简单翻了翻。

对应的lab是用位运算实现各种有的没的…

题目基本都很tricky…

除了用到一些常规的位运算性质,还用到了一些奇怪的条件:

  • ~0x7FFFFFFF = 0x7FFFFFFF + 1
  • 0xFFFFFFFF +1 =  0x00000000
  • 0 == ~0+1

唯一让我觉得比较有趣的是how many bits这道题

题目要求是给一个32-bit signed int,问最少用多少位能得到它的补码表示。

考虑正数,显然,高位的连续的多个0是不必要的,只需要一个符号位的0即可。

那么对于负数,高位的连续的多个1也是不必要的。 原因是,-2^k + 2^(k-1) =  -2^(k-1),也就是说,去掉两个连续的1中高位的那个,数值没有改变。

我们可以将正数和负数统一来看,都是找到最高位的0和1的交界。

这可以通过和相邻的位置求异或,找到最高位的1的方式来实现。

接下来就是如何找一个数的最高位的1的位置了。

方法是构造一个单调的函数f,假设最高位位置为a,那么f((a,32))=0,f([0,a])=1.

然后在函数f上二分。

全部问题的代码如下,思路写在注释里了。还有3个涉及浮点数的问题之后补。

 

补上三个涉及浮点数的问题…比较无聊,按照IEEE754操作即可.

 

 

 

快速乘

16年北京网络赛遇到了这个技巧…但是竟然忘记记了下来?

快速乘是为了解决 计算ab % mod 时ab溢出LL 的问题

比如a=1E16,b=1E16,mod=1E18,虽然最后的结果没有溢出,但是中间溢出了。

原理和快速幂很类似,具体可以参考 晴川大爷的专栏

完全就是把快速幂中的乘法变成加法了嘛(从记忆角度考虑orz

 

 

 

acm 奇技淫巧 bitset

1.定义与初始化
在定义 bitset 时,要明确 bitset 有多少位,这个位数是整形常量

(tips:如果长度和输入的数m有关,在做翻转操作以后再统计时候会多算,一个可以的做法是设置一个长度为m,所有位上都是1的位串,然后翻转之后先与一下。类似的技巧还有很多。)

()
bitset<n> b;                          //b 有 n 位,每位都是 0
bitset<n> b(u);                     //b 是 unsigned long 型 u 的一个副本
bitset<n> b(s);                      //b 是 string 对象 s 中含有的位串的副本,这个s 必须是位串,也就是二进制码串
bitset<n> b(s, pos, n);        //b 是 s 中 从位置 pos 开始的 n 个位的副本

2.bitset 的操作
b.any()              //b 中是否存在置为 1 的二进制位?
b.none()             // 和b.any() 效果一样
b.count()            //b 中不存在置为 1 的二进制位吗?

b.any()             //b中存在置为1的二进制位吗?
b.size()              //b 中置为 1 的二进制位的个数
b[pos]               //访问 b 中在 pos 处二进制位
b.test(pos)        //b 中在 pos 处的二进制位置为 1
b.set()              // 把 b 中所有二进制位都置为 1
b.set(pos)        //把 b 中在 pos 处的二进制位置为 1
b.reset()          //把 b 中所有二进制位都置为 0
b.reset(pos)  //把 b 中在 pos 处的二进制位置为 0
b.flip()            //把 b 中所有二进制位逐位取反
b.flip(pos)       //把 b 中在 pos 处的二进制位取反
b.to_ulong()   //用 b 中同样的二进制位返回一个 unsigned long 值
os << b          //把 b 中的位集输出到 os 流
示例:

cout << b << endl;