# 抛砖引玉 - 位运算优化续解决方法

www.MyException.Cn  网友分享于：2013-03-02  浏览：19次

int bitposition_loop(UINT64 s)
{
for (int c = 0; c < 40; c++)
if (s == 1ULL << c)
return c;
}

int bitposition_count(UINT64 s)
{
return bitcount(s - 1);
}
s-1可生成c个连续的1.对其计数即可.

int bitposition_rem(UINT64 s)
{
static const BYTE T[53] = { // 余数-指数表, c == (1 << t[c]) % 53
-1, 0, 1, 17, 2, 47, 18, 14, 3, 34, 48, 6, 19, 24, 15, 12, 4, 10,
35, 37, 49, 31, 7, 39, 20, 42, 25, 51, 16, 46, 13, 33, 5, 23, 11, 9,
36, 30, 38, 41, 50, 45, 32, 22, 8, 29, 40, 44, 21, 28, 43, 27, 26};
return T[(UINT(s>>32) * 42 + UINT(s)) % 53];
}

s = a * 0x100000000 + b;

s % 53 = (a * 0x100000000 + b) % 53
= (a * (81037118 * 53 + 42) + b) % 53;
= (a * 81037118 * 53 + a * 42 + b) % 53
= (a * 81037118) * 53 % 53 + (a * 42 + b) % 53
= (a * 42 + b) % 53;

int bitposition_float(UINT64 s)
{
float f = (float)(INT64)s;
return ((int&)f >> 23) - 127;
}

int bitposition_double(UINT64 s)
{
double d = (double)(INT64)s;
return UINT((UINT64&)d >> 52) - 1023;
}

IEEE754规定,浮点数由符号,阶码,尾数3部分组成.
float是32位浮点数,其中符号占1位,阶码占7位,尾数占23位.
double是64位浮点数,其中符号占1位,阶码占11位,尾数占52位.
long double是80位浮点数,什么占多少位忘记了.

(UINT64&)d同理.
(double)(INT64)s看似奇怪,但没有(INT64)不行,编译器会说不能把UINT64转化为float.

int bitposition_bin(UINT64 s) //23834

int c, a;
if (UINT(s))
{
c = 0;
a = UINT(s);
}
else
{
c = 32;
a = UINT(s>>32);
}
if (a & 0xffff0000) c += 16;
if (a & 0xff00ff00) c += 8;
if (a & 0xf0f0f0f0) c += 4;
if (a & 0xcccccccc) c += 2;
if (a & 0xaaaaaaaa) c += 1;
return c;
}
2分查找法.指令较多,但都是快速指令.速度还凑合.

int bitposition_mul(UINT64 s)
{
static const BYTE T[32] = {
0, 1, 2, 6, 3, 16, 7, 21, 4, 19, 17, 11, 13, 8, 22, 26,
31, 5, 15, 20, 18, 10, 12, 25, 30, 14, 9, 24, 29, 23, 28, 27};
if ((UINT)s)
return T[(UINT)s * 0x046B29DF >> 27];
else
return T[UINT(s>>32) * 0x046B29DF >> 27] + 32;
}
0x046B29DF,这个神奇的数,他的2进制可表示为00000100011010110010100111011111

0x046B29DF * s >> 27 = 0x046B29DF * (1 << c) >> 27 = 0x046B29DF >> 27 - c;

int bitposition_bsf(UINT64 s)
{
if ((UINT)s)
{
__asm bsf eax, s
}
else
{
__asm bsf ecx, [s+4]
__asm lea eax, [ecx+32]
}
}