矩阵迭代的逐位移位？

Question

好的一些背景知识

我一直在从事这个项目，这是我在大学时就开始的（不再在学校，但想扩展它以帮助我提高对 C++ 的理解）。我离题了……问题是通过矩阵找到最佳路径。我生成一个矩阵，其中填充了一组整数值，比方说 9。然后我沿着外边缘（第 0 行，第 1 列长度）创建一条路径，以便沿着它的所有值都是 1.

目标是我的程序将运行遍历所有可能的路径并确定最佳路径。为了简化问题，我决定只计算路径 SUM，然后将其与应用程序计算的 SUM 进行比较。

(题目是小姐领导S=单线程P=多线程)

好的，我的问题。

在一个部分中，算法会进行一些简单的逐位移位以得出迭代的界限。我的问题是这些移位究竟是如何工作的，以便完全遍历整个矩阵（或 MxN 数组）？

void AltitudeMapPath::bestPath(unsigned int threadCount, unsigned int threadIndex) {
    unsigned int tempPathCode;
    unsigned int toPathSum, toRow, toCol;
    unsigned int fromPathSum, fromRow, fromCol;

    Coordinates startCoord, endCoord, toCoord, fromCoord;

    // To and From split matrix in half along the diagonal
    unsigned int currentPathCode = threadIndex;
    unsigned int maxPathCode = ((unsigned int)1 << (numRows - 1));
    while (currentPathCode < maxPathCode) {
        tempPathCode = currentPathCode;

        // Setup to path iteration
        startCoord = pathedMap(0, 0);
        toPathSum = startCoord.z;
        toRow = 0;
        toCol = 0;

        // Setup from path iteration 
        endCoord = pathedMap(numRows - 1, numCols - 1);
        fromPathSum = endCoord.z;
        fromRow = numRows - 1;
        fromCol = numCols - 1;

        for (unsigned int index = 0; index < numRows - 1; index++) {
            if (tempPathCode % 2 == 0) {
                toCol++;
                fromCol--;
            }
            else {
                toRow++;
                fromRow--;
            }
            toCoord = pathedMap(toRow, toCol);
            toPathSum += toCoord.z;
            fromCoord = pathedMap(fromRow, fromCol);
            fromPathSum += fromCoord.z;
            tempPathCode = tempPathCode >> 1;
        }

        if (toPathSum < bestToPathSum[threadIndex][toRow]) {
            bestToPathSum[threadIndex][toRow] = toPathSum;
            bestToPathCode[threadIndex][toRow] = currentPathCode;
        }

        if (fromPathSum < bestFromPathSum[threadIndex][fromRow]) {
            bestFromPathSum[threadIndex][fromRow] = fromPathSum;
            bestFromPathCode[threadIndex][fromRow] = currentPathCode;
        }
        currentPathCode += threadCount;
    }
}

我简化了代码，因为所有额外的东西只会分散问题的注意力。另外，如果人们想知道我编写了大部分应用程序，但使用按位运算符的想法是我过去的讲师教给我的。

编辑：

我添加了每个线程执行的整个算法。整个项目仍在进行中，但如果有人感兴趣，这里是整个项目的源代码 [GITHUB]

Answer 1

右移一位相当于将移位的位数除以2次方。即 1 >> 2 = 1 / (2 ^ 2) = 1 / 4

向左移位相当于移位位数乘以2的幂。即 1 << 2 = 1 * 2 ^ 2 = 1 * 4

我不完全确定该算法的作用以及为什么它需要乘以 2^（行数 - 1）然后逐渐除以 2。

矩阵迭代的逐位移位？

Bit-wise shift for Matrix iteration?

c++

matrix

bit-shift

bitwise-operators

好的一些背景知识

好的，我的问题。

编辑：