我一直在想，使用最佳的汇编指令是否能使程序更快。所以我尝试了三种实现方式，并得到了1000万次迭代的以下结果：
您的实现（Dr.Kameleon）1.77秒
log2()实现（icepack）2.17秒
我的汇编实现（我自己）0.16秒
输出：
bits version:
Function started at 0
ended at 177
spent 177 (1.770000 seconds)
c version:
Function started at 177
ended at 394
spent 217 (2.170000 seconds)
c version:
Function started at 394
ended at 410
spent 16 (0.160000 seconds)
关于C/C++，静态编译实际上是将其编译成一系列CPU指令（这并不是我所期望的！）。相反地，可以在一个匿名命名空间中使用函数外的数组来达到预期效果。尽管在汇编中可以使用.long（或其他大小），然后使用%rip从IP引用数据。
注意：一旦编译完成，我在汇编版本中没有看到大小（n）被使用，因此我不太确定返回的数组是否有效。除此之外，代码本身成为了5个汇编指令的循环，因此速度略微提高（约为x10）。
log2（）运行缓慢的原因是它将数字转换为xmm寄存器，然后调用另一个函数。然后将xmm寄存器转换回常规寄存器。
#include <stdlib.h>
#include <stdio.h>
#include <inttypes.h>
#include <unistd.h>
#include <sys/times.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
namespace
{
const int index64[64] = {
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5 };
const uint64_t debruijn64 = 0x07EDD5E59A4E28C2ULL;
}
int firstBit(uint64_t bitboard)
{
return index64[((bitboard & -bitboard) * debruijn64) >> 58];
}
vector<int> bits(uint64_t bitboard)
{
vector<int> res;
res.reserve(64);
while(bitboard)
{
int first = firstBit(bitboard);
res.push_back(first);
bitboard &= ~(1ULL << first);
}
return res;
}
vector<int> bits_c(uint64_t bitboard)
{
int n;
vector<int> res;
res.reserve(64);
for (n = 0; bitboard != 0; n++, bitboard &= (bitboard - 1))
{
res.push_back(log2(bitboard & ~(bitboard - 1)));
}
return res;
}
vector<int> bits_asm(uint64_t bitboard)
{
int64_t n(0);
int res[64];
asm(
"bsf %[b], %%rax\n\t"
"je exit\n\t"
".align 16\n"
"loop:\n\t"
"mov %%eax, (%[r],%[n],4)\n\t"
"btr %%rax, %[b]\n\t"
"inc %[n]\n\t"
"bsf %[b], %%rax\n\t"
"je loop\n"
"exit:\n\t"
: "=r" (n)
: [n] "r" (n), [r] "r" (res), [b] "r" (bitboard)
: "eax", "cc"
);
return vector<int>(res, res + n);
}
class run_timer
{
public:
run_timer()
{
}
void start()
{
times(&f_start);
}
void stop()
{
times(&f_stop);
}
void report(const char *msg)
{
printf("%s:\n"
"Function started at %ld\n"
" ended at %ld\n"
" spent %ld (%f seconds)\n",
msg,
f_start.tms_utime,
f_stop.tms_utime,
f_stop.tms_utime - f_start.tms_utime,
(double)(f_stop.tms_utime - f_start.tms_utime)/(double)sysconf(_SC_CLK_TCK));
}
struct tms f_start;
struct tms f_stop;
};
int main(int argc, char *argv[])
{
run_timer t;
t.start();
for(int i(0); i < 10000000; ++i)
{
bits(rand());
}
t.stop();
t.report("bits version");
t.start();
for(int i(0); i < 10000000; ++i)
{
bits_c(rand());
}
t.stop();
t.report("c version");
t.start();
for(int i(0); i < 10000000; ++i)
{
bits_asm(rand());
}
t.stop();
t.report("c version");
return 0;
}
使用以下命令行编译的g++：
c++ -msse4.2 -O2 -o bits -c bits.cpp
尽管您可能认为-msse4.2可能是log2（）版本的问题，但我尝试了没有它，log2（）仍然比较慢。顺便说一下，我不建议使用这种方法，因为它不可移植。只有基于英特尔的计算机才能理解这些指令。
