才一个主题贴，就奉上这么长的代码，着实让我吃惊。。虽然我能看得懂代码，但毕竟内功远远不够，:L
我开始醒悟，我既非理科，又非计算机专业的，进了这地方，是一个很大的冒失啊。
向你们致敬，想你们学习了！
:)
用我给出的表，直接查表，似乎还能加速
你的代码已经比我给出的表数据多了
我从0.342优化到0.171,如果优化后速度再提高一倍，就是第一名了。按照楼主的思路，将XOR和log10这2步操作合在一起，用汇编语言写成一个函数，速度应该可以更快。等有时间我将尝试一下。
呵呵
我第一次是0.468， 普通算法
不如shshsh_0510的普通算法
按照楼主的思路写的代码
现在是0.234
看来还需要优化啊
目前的笨代码
和各位无法比啊
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct
{
unsigned int d;
} UINT128;
unsigned int CompTable ={0,0, 0,0, 0,0, 0,1, 1,0, 1,0, 1,1, 2,0, 2,0, 2,1, 3,0, 3,0, 3,0, 3,1,
4,0,4,0,4,1,5,0,5,0,5,1,6,0,6,0,6,0,6,1,7,0,7,0,7,1,8,0,8,0,
8,1,9,0,9,0,9,0,9,1,10,0,10,0,10,1,11,0,11,0,11,1,12,0,12,
0,12,0,12,1,13,0,13,0,13,1,14,0,14,0,14,1,15,0,15,0,15,0,15,
1,16,0,16,0,16,1,17,0,17,0,17,1,18,0,18,0,18,0,18,1,19,0,19,
0,19,1,20,0,20,0,20,1,21,0,21,0,21,0,21,1,22,0,22,0,22,1,23,
0,23,0,23,1,24,0,24,0,24,0,24,1,25,0,25,0,25,1,26,0,26,0,26,
1,27,0,27,0,27,0,27,1,28,0,28,0,28,1,29,0,29,0,29,1,30,0,30,
0,30,1,31,0,31,0,31,0,31,1,32,0,32,0,32,1,33,0,33,0,33,1,34,
0,34,0,34,0,34,1,35,0,35,0,35,1,36,0,36,0,36,1,37,0,37,0,37,0,37,1,38,0};
UINT128 pow10 = {1,0,0,0,
10,0,0,0,
100,0,0,0,
1000,0,0,0,
10000,0,0,0,
100000,0,0,0,
1000000,0,0,0,
10000000,0,0,0,
100000000,0,0,0,
1000000000,0,0,0,
1410065408,2,0,0,
1215752192,23,0,0,
3567587328,232,0,0,
1316134912,2328,0,0,
276447232,23283,0,0,
2764472320,232830,0,0,
1874919424,2328306,0,0,
1569325056,23283064,0,0,
2808348672,232830643,0,0,
2313682944,2328306436,0,0,
1661992960,1808227885,5,0,
3735027712,902409669,54,0,
2990538752,434162106,542,0,
4135583744,46653770,5421,0,
2701131776,466537709,54210,0,
1241513984,370409800,542101,0,
3825205248,3704098002,5421010,0,
3892314112,2681241660,54210108,0,
268435456,1042612833,542101086,0,
2684354560,1836193738,1126043566,1,
1073741824,1182068202,2670501072,12,
2147483648,3230747430,935206946,126,
0,2242703233,762134875,1262,
0,952195850,3326381459,12621,
0,932023908,3199043520,126217,
0,730304488,1925664130,1262177,
0,3008077584,2076772117,12621774,
0,16004768,3587851993,126217744,
0,160047680,1518781562,1262177448,
0, 0, 0, 0};
inline int _log2(unsigned int r)
{
__asm
{
bsr eax,r
}
}
inline int log2( UINT128 n)
{
if (n.d != 0) return (96 + _log2(n.d));
if (n.d != 0) return (64 + _log2(n.d));
if (n.d != 0) return (32 + _log2(n.d));
return (_log2(n.d));
}
inline int compare( const void * a, const void * b )
{
unsigned int * l, * r;
l = (unsigned int *)a; r = (unsigned int *)b;
if (*(l+3) != *(r + 3)) return (*(l + 3) > *(r+3) ? 1 : -1);
if (*(l+2) != *(r + 2)) return (*(l + 2) > *(r+2) ? 1 : -1);
if (*(l+1) != *(r + 1)) return (*(l + 1) > *(r+1) ? 1 : -1);
return (* l > * r ? 1 : (* l == * r ? 0 : -1));
}
inline int log_10(UINT128 n)
{
int i = log2(n), j = CompTable;
if (CompTable == 0) return (j);
if (compare(&n, &pow10) >= 0) return (j + 1); else return j;
}
int main(int argc, char* argv[])
{
int count,result,i,j, k;
UINT128 data;
unsigned int l2;
unsigned int l10;
UINT128 r;
scanf("%d",&count);
result=0;
i = 0;
while (i < count) {
scanf("%u", &data.d);
scanf("%u", &data.d);
scanf("%u", &data.d);
scanf("%u", &data.d);
i++;
}
qsort( (void *)data, (size_t)count, 16, compare );
for (i = 0; i < count; i ++)
{
l10 = log_10(data);
l2 = log2(data);
}
for (i= count - 1; i > 0; i --)
{
k = l2;
if (CompTable == 0)
{
j = i - 1;
while ((l2 == k) && (j >= 0))
{
r.d = data.d ^ data.d;
r.d = data.d ^ data.d;
r.d = data.d ^ data.d;
r.d = data.d ^ data.d;
result += log_10(r);
j --;
}
if (j >= 0)
result += l10 * (j + 1);
}
else
for (j = i - 1; j >= 0; j --)
{
r.d = data.d ^ data.d;
r.d = data.d ^ data.d;
r.d = data.d ^ data.d;
r.d = data.d ^ data.d;
result += log_10(r);
}
}
printf("%u",result*2);
return 0;
}
0.203
__declspec(naked)
int log2(UINT128 * n)
{
__asm
{
mov edx,
bsr eax,
bsr ecx,
add ecx, 32
cmp , 0
cmovne eax, ecx
bsr ecx,
add ecx, 64
cmp , 0
cmovne eax, ecx
bsr ecx,
add ecx, 96
cmp , 0
cmovne eax, ecx
ret
}
}
128位求2的对数非跳转版本！！
C中内嵌汇编，:L
我将我的101楼代码的阅读权限调低了。现在只有积分达到200分，就可以看我101楼的代码
147# OK了
下面汇编化 log10和log10xor
呵呵