基于整数向量执行比特置换的有效方法？

Question

我有一组64位的整数，我需要对其应用一定数量的“对称操作”。对称操作只是一系列比特排列，存储在整数向量中作为{i0，i1，i2，..}，其中bit->biti0，bit1->biti1，等等...实际上，我只使用前N位，其中N是在运行时确定的，但原则上可以达到64位。

例如，我正在使用N=4，输入是整数3或0011，并且我有4个对称操作存储在向量symmetry_ops的向量中

symmetry_ops[0] = {0,1,2,3};
symmetry_ops[1] = {1,2,3,0};
symmetry_ops[2] = {2,3,0,1};
symmetry_ops[4] = {3,0,1,2};

我想要一个函数，它返回通过将这些运算应用于3而获得的4个整数，即0011,0110,1100和1001。这个例子很简单，但在实践中，排列可能比仅仅向左移动复杂得多。

我写了以下简单的代码(天真?)代码：

std::vector<unsigned long> apply_symmetries(const std::vector<std::vector<unsigned> > &symmetry_ops, unsigned long state)
{
   unsigned N = symmetry_ops[0].size();
   std::vector<unsigned long> s_moved(symmetry_ops.size(),0);
   for (unsigned i = 0; i < N; i++) {
     unsigned long s_i = (state&(1UL<<i))>>i; // extracts bit i in state
     for (unsigned op = 0; op != symmetry_ops.size(); op++)
       s_moved[op] = s_moved[op]|(s_i<<symmetry_ops[op][i]);
   }
   return s_moved;
}

它对整数"state“执行所有的对称操作。我只是简单地在i上的循环中一位接一位地执行，首先将其存储在s_i中，然后为每个对称操作移动它。

我知道，这是我的程序中耗费时间最多的部分之一，因为典型的大小是~100-200个对称操作，应用于~10^10个整数，其中N大约是40。代码工作正常，但是我想知道这个函数是否可以优化？

提前谢谢。

Answer 1

首先，如果您在代码中添加注释来解释什么是什么，这将会有所帮助。另外，选择描述性变量名称，不要选择's_i‘或's_moved’作为变量名称，这会使代码不可读。“symmetry_ops”是一个很好的名字，“state”也是，其他的都不是。

无论如何，为了加速你的代码:如果你有一个对称的op，它将位i发送到x位，下一个对称op将x位发送到y位，将这两个op组合在一起，就相当于在单个op中将i位发送到y位。

因此，首先只对操作进行循环。

对于每个对称op，将其应用于前一个，然后在循环中使用新的对称op作为前一个。然后你就可以为整个东西构造一个单一的对称op。我正在编写伪代码来清楚地说明这一点。

identity_op = {0, 1, 2, 3, 4, 5, 6, 7} //vector of int, maps each bit to same bit
previous_op = identity_op
for each op { //op is vector of ints, op[i] maps bit i to op[i]
    //combine op with prev_op to make a new prev_op
    for each i in op { 
        prev_op[i] = op[prev_op[i]] //bit i is mapped by prev_op and then mapped again by op, giving new value for prev_op
    }
} 
combined_op = previous_op
apply combined_op to the bits, this is only place you need to to bit shifting

您的C++代码看起来很好，只需重写以使用此新算法。