[描述]给定两个长度相同的整数数组.设计一种能够判断它们是否相同的算法."相同"的定义是,如果这两个数组按排序顺序排列,则相应位置的元素应该相同.
[Example]
<1 2 3 4> = <3 1 2 4>
<1 2 3 4> != <3 4 1 1>
[限制]算法应该需要恒定的额外空间和O(n)运行时间.
假设您正在使用x86 32位系统.您的任务是尽快实现strlen.
你需要注意两个问题:1.地址对齐.2.读取机器字长(4字节)的存储器.
在给定的字符串中找到第一个对齐地址并不难.
然后我们可以用4个字节读取一次内存,并计算总长度.但是,一旦在4个字节中有一个零字节,我们应该停止,并在零字节之前计算左字节.为了快速检查零字节,glibc提供了一个代码片段:
unsigned long int longword, himagic, lomagic;
himagic = 0x80808080L;
lomagic = 0x01010101L;
// There's zero byte in 4 bytes.
if (((longword - lomagic) & ~longword & himagic) != 0) {
// do left thing...
}
我在Visual C++中使用它,与CRT的实现进行比较.CRT比上面的快得多.
我不熟悉CRT的实现,他们是否使用更快的方法来检查零字节？