17 mai
昨天讨论到的几个简单的算法, 从易到难
1. 如何计算1--10000之间的所有质数？
方法1:
for i=1 to 10000
for j=2 to i-1
if (i%j == 0) i is not prime number and go to next i
next j
i is prime number
next i
方法2:
for i=1 to 10000
for j in every prime number we found already
if (i%j == 0) i is not prime number and go to next i
next j
i is prime number
next i
方法3:
dim bitset[10000], clear elements to 0
for i=2 to 10000
if bitset[i]==0 then set bitset[i, 2i, ... n*i] to 1
next i
for i=2 to 10000
if bitset[i]==0, i is prime number
next i
2, 如何把大写ASCII字母转换成小写ASCII字母，要注意效率！
方法1:
char foo(char c)
{
return c-('A'-'a');
}
简单直观对吧，减去大小写之间的差距就可以了。相信99%的人都会写这个函数。面试官看看函数，再看看你，给你说，有没有更有效率的方法。如果你想不起，他会提醒你，查表如何？
哦，于是你就写:
char foo(char c)
{
return mytable[c];
}
mytable是程序初始化的时候建立的大小写对应表，这下子直接返回一个值就就可以了，根本不用计算！我不知道面试官是不是会接受这个答案，但如果我是面试官，我会让你再仔细看看，到底怎么才算有效率？
如果你还比较警觉的话，你会发现，第一种方法虽然要做计算(做一次减法)，但是计算是在寄存器内完成的。第二种方法，虽然不做计算，但是结果却是在mytable这个内存上去取的。哪怕mytable在cache里面，谁会更快一点呢？
3, 如何写一个合格的strcpy函数
这个问题在面试中出现过很多次了对吧。普通人能够把算法写对，有点常识的人会检查source/dest地址是否重合，有点经验的人会使用assert来提供两个不同的版本，但是，strcpy的核心在这里吗？
下面这个篇文章可能会让你思考更多的东西:
好，做一个总结，仔细思考的人，除了写正确strcpy外，还会考虑效率:
1). 别一个字节一个字节地写。每次写4个字节，用DWORD*来操作，这样在32bit的芯片上，CPU周期才不会浪费。同时注意4字节对齐
关于这一点，有一个重要的讨论，事后补充上的，请参考:
2). Inline
4, 如何计算一个DWORD的二进制表示有多少个1
Level1 (my level
):
while(i!=0)
{
n+=(i&1);
i=i>>1;
}
Level2:
while ( n > 0)
{
n = n & (n-1); count++;
}
Level3 (my level after upgrade
):
byte* b=(byte*)(&n);
n=mytable[b]+mytable[b+1]+mytable[b+2]+mytable[b+3]; //mytable saves the count of 1's for 0-f
有了第三个问题的经验，你应该会怀疑一下Level3跟Level2到底谁快
Level4:
static UInt32 count_ones(UInt32 n)
{
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
return n;
}
Level5:
unsigned int ones32(register unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x >> 1) & 0x55555555);
x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
x = (((x >> 4) + x) & 0x0f0f0f0f);
x += (x >> 8);
x += (x >> 16);
return (x & 0x0000003f);
}
Level4, Level5我是想不出来的，不过好歹能看懂
。要是看不懂，可以参考:
考虑完这4个题目后，我终于相信:
1, 没有最好，只有更好
2, 别老以为头头是道的分析就是正确的结果，是驴子是马，拿vc跑一遍再说
comments by nickol, thanks again :)
1的方法3有问题哦, 应该是这样吧：
dim bitset[10000], clear elements to 0
for i=2 to 10000
if bitset[i]==0 then set bitset[2*i, ... n*i] to 1
next i
for i=2 to 10000
if bitset[i]==0, i is prime number
next i
PS, 把一个全排列算法也补在这里:
mine:
define NUM 6
int nLevel=0,List[256]={0},ALL;
p()
{
int nCount,nJudge,key;
nLevel++;
if(nLevel>NUM)
{
print();
nLevel--;
return;
}
for(nCount=1;nCount<=NUM;nCount++)
{
key=0;
for(nJudge=0;nJudge<=nLevel-1;nJudge++)
if(nCount==List[nJudge])
{
key=1;
break;
}
if(key==0)
{
List[nLevel]=nCount;
p();
}
}
nLevel--;
}
print()
{
int nCount;ALL++;
for(nCount=1;nCount<=NUM;nCount++)printf("%d ",List[nCount]);
printf("\t%d\n",ALL);
}
main()
{p();
}
A better one from 马舒德:
public class allsort {
/** Creates a new instance of allsort */
public allsort() {
}
public static void swap(int[] a,int i,int j){
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
public static void perm(int[] list,int k,int m){
if(k==m){
for(int i=0;i<=m;i++)
System.out.print(list[i]);
System.out.println();
}
else
for(int i=k;i<=m;i++)
{
swap(list,k,i);
perm(list,k+1,m);
swap(list,k,i);
}
}
public static void main(String args[]){
int[] list={1,2,3,4,5,6,7,8,9,0};
perm(list,0,9);
}
}
Outils 
Aide
