const int one_in_char[256]=
{
0, 1, 1, 2, 1, 2,2,3
......
,8
}
此为 0-255 每个数中 1 的个数。
这个雕虫小技在密码，crc...等地方使用很广泛。
int func2(int v)
{
int n=v;
unsigned char *ptr=(unsigned char *)&n;
return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
对任何数，任何体系结构的cpu， 只要 sizeof(int)-1 次加法。
而且很容易扩展到任何数据类型。
使用 case最慢， 使用条件转移要受流水线预测错误的干扰。
converse 回复于：2006-07-20 09:37:35
不错!
mik 回复于：2006-07-20 09:51:39
是不错，
但估什不一定能比他贴的这个方法快
unsigned int func(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
// Version 1
x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
return x;
#else
// Version 2
x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x >> 8; // 0-16 in 8 bits
x += x >> 16; // 0-32 in 8 bits
return x & 0xff;
#endif
}
测试一下看看
kuaizaifeng 回复于：2006-07-20 09:54:16
确实够快！！！
mike_chen 回复于：2006-07-20 10:03:16
引用：原帖由 mik 于 2006-7-20 09:51 发表
是不错，
但估什不一定能比他贴的这个方法快
unsigned int func(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
x = (x & ...
好！
unicorns 回复于：2006-07-20 10:37:34
引用：原帖由 mik 于 2006-7-20 09:51 发表
是不错，
但估什不一定能比他贴的这个方法快
unsigned int func(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
x = (x & ...
把楼主的举一反三一下.
穷举unsigned int4个字节可能出现的所有情况.
一次偏移就行了.
楼主只是一个思路,我觉得这个思路是最快的.
linh123 回复于：2006-07-20 10:46:52
学习一下.
converse 回复于：2006-07-20 10:55:31
加精鼓励一下,希望以后好东西多多分享
connet 回复于：2006-07-20 10:56:21
在 P4 2.8G 上 redhat 9.0, 升级kernel 到2.4.32
不优化结果：
time of func: 58
time of func2: 31
O2优化结果：
time of func: 22
time of func2: 17
在 via C7 1.3G 上 kernel 2.6.16.22
不优化结果：
time of func: 151
time of func2: 135
O2优化结果：
time of func: 25
time of func2: 40
在 AMD64 3000+ 上， FC5, 2.6.16-1.2122_FC5
不优化结果：
time of func: 48
time of func2: 61
O2优化结果：
time of func: 25
time of func2: 40
在 AMD64 3000+ 上， redhat 9 2.4.20-8
不优化结果：
time of func: 48
time of func2: 54
O2优化结果：
time of func: 24
time of func2: 41
可以看到无论是否优化，在intel CPU 上， 我的算法快， 但是在 AMD+FC5 上，我的慢。
但是在 via C7上， 我的算法优化前快， 优化后反而比那个算法慢。
不优化 gcc -o one one.c
优化 gcc -O2 -o one2 one.c
程序如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
int count=0x7FFFFFFF;
unsigned int func(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
// Version 1
x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
return x;
#else
// Version 2
x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x >> 8; // 0-16 in 8 bits
x += x >> 16; // 0-32 in 8 bits
return x & 0xff;
#endif
}
int one_in_char[256];
int func2(int *v)
{
unsigned char *ptr=(unsigned char *)v;
return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
void test_1()
{
int t1, t2;
int i, v;
char v2=0;
t1 = time(NULL);
for (i=0; i<count; i++)
{
v = func(i);
v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
}
t2 = time(NULL);
printf("time of func: %d v2=%d\n", t2-t1, v2);
}
void test_2()
{
int t1, t2;
int i, v;
char v2=0;
for (i=0; i<256; i++)
one_in_char=i%8; /* 这 256 为硬编码， 为简便起见，随便设，不影响计算时间 */
t1 = time(NULL);
for (i=0; i<count; i++)
{
v = func2(&i);
v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
}
t2 = time(NULL);
printf("time of func2: %d v2=%d\n", t2-t1, v2);
}
int main(int argc, char **argv)
{
test_1();
test_2();
return 0;
}
[ 本帖最后由 connet 于 2006-7-20 11:00 编辑 ]
unicorns 回复于：2006-07-20 11:03:11
http://bbs.chinaunix.net/viewthread.php?tid=513621&extra=&page=1
一年多了.........
connet 回复于：2006-07-20 11:07:57
引用：原帖由 unicorns 于 2006-7-20 11:03 发表
http://bbs.chinaunix.net/viewthread.php?tid=513621&extra=&page=1
一年多了.........
果然以前有人讨论过
isjfk 回复于：2006-07-20 11:44:22
AMD 平台内存速度一直是拖后腿的地方，因此集中在 CPU 寄存器上进行的运算反而比需要访问内存的优化算法快。Intel 平台的内存带宽很大，lz 算法的优势就体现出来了。
看来优化的时候平台的特性也必须考虑进去，空间换时间并不总是有效的。
liubinbj 回复于：2006-07-20 11:48:38
楼主如果真是想挑战最快，那请用我的算法来对比吧，在我的《放出一个世界上最快的判断32位整数二进制中1的个数的算法》帖子里，楼主用于对比的方法已经被证明比我的算法慢，它不是最快的。
yulc 回复于：2006-07-20 11:48:39
引用：原帖由 isjfk 于 2006-7-20 11:44 发表
AMD 平台内存速度一直是拖后腿的地方，因此集中在 CPU 寄存器上进行的运算反而比需要访问内存的优化算法快。Intel 平台的内存带宽很大，lz 算法的优势就体现出来了。
看来优化的时候平台的特性也必须考虑进去， ...
楼上的,请教一下.
如书上所说, 不管你内存速度有多快, 但总是比不过寄存器的呀, 难道Inter平台上,访问内存的速度会快过寄存器?
isjfk 回复于：2006-07-20 11:55:54
我说过内存速度比寄存器快？
我只是说空间换时间的方法在内存 IO 比较低的平台上可能得不到预期的效果。
内存 IO 只是影响算法速度的一个因素，没有多少算法是只访问寄存器或者只访问内存的。
yulc 回复于：2006-07-20 12:01:29
理解错了...
我知道你要表达的意思了.
connet 回复于：2006-07-20 12:13:16
引用：原帖由 liubinbj 于 2006-7-20 11:48 发表
楼主如果真是想挑战最快，那请用我的算法来对比吧，在我的《放出一个世界上最快的判断32位整数二进制中1的个数的算法》帖子里，楼主用于对比的方法已经被证明比我的算法慢，它不是最快的。
你怎么测试的呢？
我测试下来你的最慢。
connet 回复于：2006-07-20 13:19:25
P4 2.8G redhat 9.0, kernel 2.4.32
不优化 liubinbj方法 网上方法 我的方法
154.6641 63.7537 31.7395
O2优化 liubinbj方法 网上方法 我的方法
78.1829 19.3305 13.0671
VIA C7 1.3G , 2.6.16.22
不优化 liubinbj方法 网上方法 我的方法
431.7528 151.2660 169.5686
O2优化 liubinbj方法 网上方法 我的方法
277.4617 58.1803 59.8410
AMD64 3000+ FC5, 2.6.16-1.2122_FC5
不优化 liubinbj方法 网上方法 我的方法
180.3114 51.2969 62.6047
O2优化 liubinbj方法 网上方法 我的方法
85.9299 21.0763 24.1614
任何平台下 liubinbj方法 最慢， 是其余方法的 3-5倍时间
欢迎挑战，欢迎测试
程序存为 one.c
不优化 gcc -o one one.c
优化 gcc -O2 -o one2 one.c
运行 one 和 one2 得到结果
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
unsigned int count=0x7FFFFFFF;
static struct timeval _tstart, _tend;
static struct timezone tz;
void time_start(void)
{
gettimeofday(&_tstart, &tz);
}
void time_end(void)
{
gettimeofday(&_tend,&tz);
}
double time_val()
{
double t1, t2;
t1 = (double)_tstart.tv_sec + (double)_tstart.tv_usec/(1000*1000);
t2 = (double)_tend.tv_sec + (double)_tend.tv_usec/(1000*1000);
return t2-t1;
}
unsigned int func(unsigned int x)
{
x = (x & 0x55555555UL) + ((x >> 1) & 0x55555555UL); // 0-2 in 2 bits
x = (x & 0x33333333UL) + ((x >> 2) & 0x33333333UL); // 0-4 in 4 bits
#if 1
// Version 1
x = (x & 0x0f0f0f0fUL) + ((x >> 4) & 0x0f0f0f0fUL); // 0-8 in 8 bits
x = (x & 0x00ff00ffUL) + ((x >> 8) & 0x00ff00ffUL); // 0-16 in 16 bits
x = (x & 0x0000ffffUL) + ((x >> 16) & 0x0000ffffUL); // 0-31 in 32 bits
return x;
#else
// Version 2
x = (x + (x >> 4)) & 0x0f0f0f0fUL; // 0-8 in 4 bits
x += x >> 8; // 0-16 in 8 bits
x += x >> 16; // 0-32 in 8 bits
return x & 0xff;
#endif
}
int one_in_char[256];
int func2(unsigned int *v)
{
// int n=v;
unsigned char *ptr=(unsigned char *)v;
return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
int func3(unsigned int n){
int count=0;
//高16位
if(n&0xFFFF0000) {
//高8
if(n&0xFF000000) {
//高4
if(n&0xF0000000) {
if(n&0x10000000) count++;
if(n&0x20000000) count++;
if(n&0x40000000) count++;
if(n&0x80000000) count++;
}
//低4
if(n&0x0F000000) {
if(n&0x01000000) count++;
if(n&0x02000000) count++;
if(n&0x04000000) count++;
if(n&0x08000000) count++;
}
}
//低8
if(n&0x00FF0000) {
//高4
if(n&0x00F00000) {
if(n&0x00100000) count++;
if(n&0x00200000) count++;
if(n&0x00400000) count++;
if(n&0x00800000) count++;
}
//低4
if(n&0x000F0000) {
if(n&0x00010000) count++;
if(n&0x00020000) count++;
if(n&0x00040000) count++;
if(n&0x00080000) count++;
}
}
}
//低16位
if(n&0x0000FFFF) {
//高8
if(n&0x0000FF00) {
//高4
if(n&0x0000F000) {
if(n&0x00001000) count++;
if(n&0x00002000) count++;
if(n&0x00004000) count++;
if(n&0x00008000) count++;
}
//低4
if(n&0x00000F00) {
if(n&0x00000100) count++;
if(n&0x00000200) count++;
if(n&0x00000400) count++;
if(n&0x00000800) count++;
}
}
//低8
if(n&0x000000FF) {
//高4
if(n&0x000000F0) {
if(n&0x00000010) count++;
if(n&0x00000020) count++;
if(n&0x00000040) count++;
if(n&0x00000080) count++;
}
//低4
if(n&0x0000000F) {
if(n&0x00000001) count++;
if(n&0x00000002) count++;
if(n&0x00000004) count++;
if(n&0x00000008) count++;
}
}
}
return count;
}
void test_1()
{
unsigned int i;
char v, v2=0;
time_start();
for (i=0; i<count; i++)
{
v = func(i);
v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
}
time_end();
printf("test func use %0.4f seconds, v2=%d\n",time_val(), v2);
}
void test_2()
{
unsigned int i;
char v, v2=0;
for (i=0; i<256; i++)
one_in_char=i%8; /* 这 256 为硬编码， 为简便起见，随便设，不影响计算时间 */
time_start();
for (i=0; i<count; i++)
{
v = func2(&i);
v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
}
time_end();
printf("test func2 use %0.4f seconds, v2=%d\n",time_val(), v2);
}
void test_3()
{
unsigned int i;
char v, v2=0;
time_start();
for (i=0; i<count; i++)
{
v = func3(i);
v2+=v; /* 若不加这个，v 没使用,循环被优化掉了 */
}
time_end();
printf("test func3 use %0.4f seconds, v2=%d\n",time_val(), v2);
}
int main(int argc, char **argv)
{
test_1();
test_2();
test_3();
return 0;
}
Arghawk 回复于：2006-07-20 13:56:02
你这个方法跟http://bbs.chinaunix.net/viewthread.php?tid=513621&extra=&page=1里面那个方法是一样的嘛，只是他算的是char中有多少个1，你算的是一个int中有多少个1
connet 回复于：2006-07-20 14:04:36
引用：原帖由 Arghawk 于 2006-7-20 13:56 发表
你这个方法跟http://bbs.chinaunix.net/viewthread.php?tid=513621&extra=&page=1里面那个方法是一样的嘛，只是他算的是char中有多少个1，你算的是一个int中有多少个1
恩， 我看到了， 前面 unicorns 已经告诉我了。
你有更好的方法？
liubinbj 回复于：2006-07-20 14:52:17
to conect:
无论怎么算，首先应该正确。
你的代码速度倒是够快，可怎么总是返回0 ？我特别不解，不知道是不是我把你的函数理解错了？
我测试了看到的两个你的版本，测试代码如下：
int one_in_char[256];
int func1(unsigned int *v)
{
unsigned char *ptr=(unsigned char *)v;
return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
int func2(int v)
{
int n=v;
unsigned char *ptr=(unsigned char *)&n;
return one_in_char[ptr[0]]+one_in_char[ptr[1]]+one_in_char[ptr[2]]+one_in_char[ptr[3]];
}
int main(int argc, char **argv)
{
unsigned int k= 6;
int i;
for(i=0;i<10000;i++)
{
if(func1(&i)!=0) printf("func1 !=0 on %d\n",i);
if(func2(i)!=0) printf("func2 !=0 on %d\n",i);
}
printf("finish\n",func2(k));
return 0;
}
没有一个不等于0的输出，我的是gcc-4.0.3
gcc -O2或者不优化结果都相同。
青野志狼 回复于：2006-07-20 14:56:01
楼主的方法确实不错，受教了
青野志狼 回复于：2006-07-20 14:57:49
引用：原帖由 liubinbj 于 2006-7-20 14:52 发表
to conect:
无论怎么算，首先应该正确。
你的代码速度倒是够快，可怎么总是返回0 ？我特别不解，不知道是不是我把你的函数理解错了？
我测试了看到的两个你的版本，测试代码如下：
int one_in_ch ...
没设置one_in_char
connet 回复于：2006-07-20 14:59:03
引用：原帖由 liubinbj 于 2006-7-20 14:52 发表
to conect:
无论怎么算，首先应该正确。
你的代码速度倒是够快，可怎么总是返回0 ？我特别不解，不知道是不是我把你的函数理解错了？
我测试了看到的两个你的版本，测试代码如下：
int one_in_ch ...
const int one_in_char[256]=
{
0, 1, 1, 2, 1, 2,2,3
......
,8
}
one_in_char 表示 0-255 这256 个数每个的1 的数目。我的测试程序只测试速度， 没有初始化这256个值。
assiss 回复于：2006-07-20 15:03:29
都别吵啦。
这个题目在这里很久以前就讨论过，不止一次。
网上有关于这个题目的总结性网页，大家不用闭门造车了。
http://www.everything2.com/index.pl?node_id=1181258
十全大补丸 回复于：2006-07-20 16:25:23
看来我比较笨，半天才搞懂是怎么回事……
liubinbj 回复于：2006-07-20 16:43:26
引用：原帖由 十全大补丸 于 2006-7-20 16:25 发表
看来我比较笨，半天才搞懂是怎么回事……
这里讲的比较详细 http://www.everything2.com/index.pl?node_id=1181258
就是查表法
J.W.Y 回复于：2006-07-20 16:43:49
学习学习，希望有高手出来写出更牛的方法。
linh123 回复于：2006-07-20 17:26:53
共同进步.
liubinbj 回复于：2006-07-20 17:57:46
我来突破楼主的速度
unsigned char table[]={
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
8,9,9,10,9,10,10,11,9,10,10,11,10,11,11,12,
9,10,10,11,10,11,11,12,10,11,11,12,11,12,12,13,
};
int func5(unsigned int m)
{
unsigned n;
n = table[m & 0x1FFF];
n+= table[m>>13 & 0x1FFF];
n+= table[m>>26 & 0x3F];
return n;
}
在我的机器上，用楼主的计算法，从0－0x7FFFFFFF
楼主的算法 我的算法
28.4203秒 17.0208秒
还快了不少，世界记录又被打破了！:em02:
mik 回复于：2006-07-20 18:01:33
:cry:
这样做没什么意义吧~
适当则可了吧
assiss 回复于：2006-07-20 18:07:02
啥叫算法，啥叫程序，唉。
liubinbj 回复于：2006-07-20 18:18:46
引用：原帖由 mik 于 2006-7-20 18:01 发表
:cry:
这样做没什么意义吧~
适当则可了吧
存脆为了速度:em02:，只不过我的长了点，呵呵，其实都是查表啊，谈不上算法了。
liubinbj 回复于：2006-07-20 21:53:44
略微修改一下代码,会看起来简短些
unsigned char table[]={
0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,
3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,
3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,
4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,
3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,
6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,
4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,
6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,
3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,
4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,
6,7,6,7,7,8,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,
4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,
4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,
4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,
6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,
7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,
5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,
4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,
7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,
6,7,7,8,6,7,7,8,7,8,8,9,1,2,2,3,2,3,3,4,2,3,3,4,3,
4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,
4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,
7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,
4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,
5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,2,3,3,4,3,4,4,5,3,4,
4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,
5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,
6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,
6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,
7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,2,3,3,4,3,4,4,
5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,
6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,
5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,
7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,3,4,4,5,
4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,
7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,
7,8,6,7,7,8,7,8,8,9,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,
8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,5,6,6,7,6,7,7,8,
6,7,7,8,7,8,8,9,6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,1,
2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,
4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,
5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,
4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,
5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,
7,8,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,
6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,5,6,4,
5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,
5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,
8,7,8,8,9,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,
4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,
6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,3,4,4,5,4,5,
5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,
8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,
6,7,7,8,7,8,8,9,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,
5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,
6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,4,5,5,
6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,
7,8,8,9,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,6,7,7,8,7,
8,8,9,7,8,8,9,8,9,9,10,2,3,3,4,3,4,4,5,3,4,4,5,4,5,
5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,
6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,
3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,
6,6,7,6,7,7,8,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,
6,7,6,7,7,8,6,7,7,8,7,8,8,9,3,4,4,5,4,5,5,6,4,5,5,
6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,5,5,6,
5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,
8,8,9,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,
7,8,6,7,7,8,7,8,8,9,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,
9,6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,3,4,4,5,4,5,5,6,
4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,4,
5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,
7,8,7,8,8,9,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8,5,6,6,
7,6,7,7,8,6,7,7,8,7,8,8,9,5,6,6,7,6,7,7,8,6,7,7,8,
7,8,8,9,6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,4,5,5,6,5,
6,6,7,5,6,6,7,6,7,7,8,5,6,6,7,6,7,7,8,6,7,7,8,7,8,
8,9,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,6,7,7,8,7,8,8,
9,7,8,8,9,8,9,9,10,5,6,6,7,6,7,7,8,6,7,7,8,7,8,8,9,
6,7,7,8,7,8,8,9,7,8,8,9,8,9,9,10,6,7,7,8,7,8,8,9,7,
8,8,9,8,9,9,10,7,8,8,9,8,9,9,10,8,9,9,10,9,10,10,11,
};
int bitcount(unsigned int m)
{
unsigned n;
n = table[m & 0x7FF];
n+= table[m>>11 & 0x7FF];
n+= table[m>>22 & 0x3FF];
return n;
}
benwood068 回复于：2006-07-21 01:09:45
好贴。。。。。版主用心了
isjfk 回复于：2006-07-21 08:22:40
我无语......
yuxh 回复于：2006-07-21 08:44:14
liubinbj 的程序思想上与楼主没有差异（都是穷举），但用这么大的数组。。。
程序的时间与空间应该有个合理的可接受的比例，这个比例严重失调啊！
偷颗白菜犯得着用大炮轰么？
caibird3rd 回复于：2006-07-21 09:28:53
引用：原帖由 yuxh 于 2006-7-21 08:44 发表
liubinbj 的程序思想上与楼主没有差异（都是穷举），但用这么大的数组。。。
程序的时间与空间应该有个合理的可接受的比例，这个比例严重失调啊！
偷颗白菜犯得着用大炮轰么？
单纯追求算法的精美是一种误区
有时候看起来最笨的办法也许在某些方面是最好的
以前看过一个帖子，讲google的高手追求的是如何用最简单的办法最有效的解决问题
liubinbj 回复于：2006-07-21 11:29:51
引用：原帖由 yuxh 于 2006-7-21 08:44 发表
liubinbj 的程序思想上与楼主没有差异（都是穷举），但用这么大的数组。。。
程序的时间与空间应该有个合理的可接受的比例，这个比例严重失调啊！
偷颗白菜犯得着用大炮轰么？
仅适用于比较苛刻计算的场合，大量的大循环计算，少量的计算楼主的算法已经够好了。
注意到你曾经提到过这个用例：
例如:在n!中2的因子的个数=n-(n的二进制中1的个数)
如:10！2的因子个数为2、6、10各1个，4两个，8三个，所以共有3+2+3=8，也=10-2
100=(1100100), 所以100！中2的因子个数为100-3=97,等等
有没有考虑到n!有10万个bit，而且循环计算n+1,n+2...的情况？这种情况也许你会考虑一下我后给出的方法。
[ 本帖最后由 liubinbj 于 2006-7-21 11:36 编辑 ]
unicorns 回复于：2006-07-21 12:07:31
低个头很难吗.奇怪.
其实有的时候只是知与不知,先知与后知的区别.
低个头也不代表自己的水平比别人差啊.
[ 本帖最后由 unicorns 于 2006-7-21 12:09 编辑 ]
yzc2002 回复于：2006-07-21 12:20:44
引用：原帖由 liubinbj 于 2006-7-21 11:29 发表
仅适用于比较苛刻计算的场合，大量的大循环计算，少量的计算楼主的算法已经够好了。
注意到你曾经提到过这个用例：
例如:在n!中2的因子的个数=n-(n的二进制中1的个数)
如:10！2的因子个数为2、6、10各1个 ...
对于一个大整数n,它的位数大约为log2(n),按你的做法是11位11位地进行计算,所以大约需log2(n)/11次计算
而用下面这个:
unsigned numbits(unsigned int i)
{
unsigned int const MASK1 = 0x55555555;
unsigned int const MASK2 = 0x33333333;
unsigned int const MASK4 = 0x0f0f0f0f;
unsigned int const MASK8 = 0x00ff00ff;
unsigned int const MASK16 = 0x0000ffff;
i = (i&MASK1 ) + (i>>1 &MASK1 );
i = (i&MASK2 ) + (i>>2 &MASK2 );
i = (i&MASK4 ) + (i>>4 &MASK4 );
i = (i&MASK8 ) + (i>>8 &MASK8 );
i = (i&MASK16) + (i>>16&MASK16);
return i;
}
用到的次数是log2(log2(n))的
当log2(n)/11 > log2(log2(n)), 至少当n>2^2^7(^这里是乘方)时,你的程序速度就比它慢了
另外,你好象没看懂我(yuxh)那个用例吧?
[ 本帖最后由 yzc2002 于 2006-7-21 12:24 编辑 ]
liubinbj 回复于：2006-07-21 12:28:43
引用：原帖由 unicorns 于 2006-7-21 12:07 发表
低个头很难吗.奇怪.
其实有的时候只是知与不知,先知与后知的区别.
低个头也不代表自己的水平比别人差啊.
大概是针对我的吧，那我来回。
你可能没看到一个叫“知错能改”的帖子（后被版主移动到别处了），在确认了connet的算法比我的2分法强的时候，我立即发了这个新贴，承认了我的2分算法不如connet查表快，到现在我也是肯定connet的发布的，在“知错能改”的帖子里我已经低头了，2分法确实不够快，但那种算法确实是我的不够成熟的原创。
即使connet的算法快，也不代表别人不能改进不是？追求速度的极限没什么过错吧。我一扩展connet给出的算法立即有人说是一样的，我没说不一样，我只求速度快。既然他这个线索是对的，我沿着这个线索继续发展一下怎么就不可以。难道你写一篇论文就不引用别人的成果？很多科技发展总是基于前人的工作一步步走下来的。
assiss 回复于：2006-07-21 13:06:50
引用：原帖由 yzc2002 于 2006-7-21 12:20 发表
另外,你好象没看懂我(yuxh)那个用例吧?
原来你是yuxh的马甲？难怪。
yzc2002 回复于：2006-07-21 13:10:03
引用：原帖由 assiss 于 2006-7-21 13:06 发表
原来你是yuxh的马甲？难怪。
这个我早就宣布过了:mrgreen:
后来你也来得少了，我也不常来了。
冥王星 回复于：2006-07-22 13:03:11
学习一下！
achun.shx 回复于：2006-07-23 21:28:06
大家用空间换时间确实是个好办法。
其实很多优秀的程序都这样干，
不过大家的热情竟然这么高，是在是让人摸不着头脑。
lenovo 回复于：2006-07-23 21:34:00
引用：原帖由 assiss 于 2006-7-21 13:06 发表
原来你是yuxh的马甲？难怪。
晕，地球人都知道。:em15:
mailjzwu_1 回复于：2006-07-24 21:03:53
学习学习！大家热情高阿！
|
