相关疑难解决方法(0)

我一直在寻找最快的方法来处理popcount大数据.我遇到了一个很奇怪的效果:改变从循环变量unsigned至uint64_t50%在我的电脑上所做的性能下降.

基准

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

    using namespace std;
    if (argc != 2) {
       cerr << "usage: array_size in MB" << endl;
       return -1;
    }

    uint64_t size = atol(argv[1])<<20;
    uint64_t* buffer = new uint64_t[size/8];
    char* charbuffer = reinterpret_cast<char*>(buffer);
    for (unsigned i=0; i<size; ++i)
        charbuffer[i] = rand()%256;

    uint64_t count,duration;
    chrono::time_point<chrono::system_clock> startP,endP;
    {
        startP = chrono::system_clock::now();
        count = 0;
        for( unsigned k = 0; k < …

如果我有一个整数n,并且我想知道最高位的位置(也就是说,如果最低有效位在右边,我想知道最左边位的位置是1),找出最快捷/最有效的方法是什么？

我知道POSIX支持ffs()strings.h中的一个方法来查找第一个设置位,但似乎没有相应的fls()方法.

是否有一些非常明显的方法可以解决这个问题？

如果你不能使用POSIX功能来实现可移植性呢？

编辑:如何在32位和64位架构上运行的解决方案(许多代码清单似乎只能在32位整数上运行).

以下所有说明都做同样的事情:设置%eax为零.哪种方式最佳(需要最少的机器周期)？

xorl   %eax, %eax
mov    $0, %eax
andl   $0, %eax

我需要找到大于或等于给定值的2的最小幂.到目前为止,我有这个:

int value = 3221; // 3221 is just an example, could be any number
int result = 1;

while (result < value) result <<= 1;

它工作正常,但感觉有点幼稚.这个问题有更好的算法吗？

编辑.有一些很好的Assembler建议,所以我将这些标签添加到问题中.

只是说我的类型值uint64_t被视为八位字节序列(1个八位字节= 8位).uint64_t已知该值仅包含MSB位置的一个设置位.因此,该uint64_t值可以是以下二进制表示之一:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000  pos = 7
00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000  pos = 15
00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000  pos = 23
00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000  pos = 31
00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000  pos = 39
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000  pos = 47
00000000 10000000 00000000 00000000 …

我正在为游戏编写一些决策AI,我已经提出了以下代码.

if(pushedLeft && leftFree && leftExists)
    GoLeft();
else if(pushedRight && rightFree && rightExists)
    GoRight();
else if(leftFree && leftExists)
    GoLeft();
else if(rightFree && rightExists)
    GoRight();
else if(pushedLeft && leftExists)
    GoLeft();
else if(pushedRight && rightExists)
    GoRight();
else if(leftExists)
    GoLeft();
else if(rightExists)
    GoRight();
// else do nothing...

这是一个相当长的if语句流,具有类似的条件!

请注意,它使这个很好的模式:

L1 L2 L3  -> L
R1 R2 R3  -> R
   L2 L3  -> L
   R2 R3  -> R
L1    L3  -> L
R1    R3  -> R
      L3  -> L
      R3  -> R …

我有一个功能:

inline uint32_t ShiftOf(uint32_t v)
{
    for (uint32_t s = 0; s < 32; ++s)
    {
        if (v == 1 << s)
            return s;
    }
    return -1;
}

有没有办法优化它？

我正在编写我的第一个游戏,我还有最后一个问题需要解决.我需要一个算法来检查我是否可以将选定的球移动到选定的位置.

看这张图片:

规则是,如果我在白色背景上拾取蓝色球(在正中间),我可以将它移动到所有绿色空间,我无法将其移动到紫色球,因为它们被其他人围起来球.我自然不能把它移到其他球的地方.球只能向上,向下,向左和向右移动.

现在我知道有两个已经存在的算法:A*和Dijkstra的算法可能会有所帮助,但它们看起来太复杂了我需要的东西(都使用我没有教过的矢量或东西,我很新编程,这是我的学期项目).我不需要找到最短路,我只需要知道所选目的地是否被其他球围起来.

我在游戏中的主板是9x9阵列,如果它是一个空的地方,只需填充'/',如果它被采取,则为7个字母中的一个.

有没有办法可以用简单的方法编写算法代码？

[我去了洪水填充,它工作得很好,谢谢你的帮助,如果有人有类似的问题 - 我建议使用洪水填充,它真的很简单快捷]

int a = 12;

例如:12的二进制是1100,所以当设置右边的第3位时,答案应为3.

我想要最后一个位置的位置a.谁能告诉我怎么能这样做呢.

注意:我只想要位置,这里我不想设置或重置位.所以它不是stackoverflow上任何问题的重复.

什么是从最低有效位(LSB)到ulong(C#)中的最高有效位(MSB)的第一个设置(1)位位置的最快(或至少非常快)的方法？对于ulong i = 18; (10010),将为2(如果我们从0开始计算位置,则为1).

MS C++编译器具有 _BitScanForward64用于此任务的内在函数,但C#编译器没有模拟.