2

我有以下代码实现线性反馈移位寄存器的移位动作：

public int DoShift()
{
    //Find new top bit
    int feedback = Contents & tapSequence;
    int newBit = 0;
    for(int i = 1; i <= length; i++)
    {
        newBit = 1 & (newBit ^ feedback);
        feedback >>= 1;
    }
    //Remember falloff, shift register, add new bit
    int result = Contents & 1;
    Contents >>= 1;
    Contents += newBit << (length - 1);
    return result;
}

在哪里

  • Contents 是寄存器的当前内容
  • tapSequence 是 XOR 抽头序列，其中 1 代表已抽头位，0 代表未抽头位。
  • 长度是寄存器的位数。

但是，在运行 CPU 使用率测试后，这个函数占用了我运行时间的 60%（我认为这是一个相当轻量级的方法）。有没有更有效的方法来写这个？有没有办法用自己的位对 int 的内容进行异或（以便取消 for 循环）？

4

2 回答 2

1

已采用以下解决方案：

public int DoShift()
{
    //Remember falloff, shift register, add new bit
    int result = Contents & 1;
    Contents = (Contents >> 1) ^ 
        ((CountBits(Contents & tapSequence) % 2) << (length - 1));
    return result;
}

//Brian Kernighan method of counting bits
public static int CountBits(int value)
{
    int count = 0;
    while (value != 0)
    {
        count++;
        value &= value - 1;
    }
    return count;
}

此外，我还可能尝试一些并行运行更广泛程序的元素。

于 2015-11-25T10:44:52.417 回答
1

尝试这个：

public int DoShift()
{
    int newBit = 1 << (length - 1); // you can save it as class member
    int result = Contents & 1;
    int feedback = Contents & tapSequence;
    Contents >>= 1;
    while(feedback != 0) {
      feedback &= feedback - 1;
      Contents ^= newBit;
    }
    return result;
}

此外，存在更有效的方法，称为“反向 LSFR”。这是一个想法 - 如果结果为 1，则仅将 tapSequence 应用于整个寄存器一次。

参见示例：https ://en.wikipedia.org/wiki/Linear_feedback_shift_register

于 2015-11-24T18:27:25.240 回答