位操作，位重排

Question

位操作，位重排

4

我正在尝试制作一个循环，遍历所有不同的整数，其中最后40位中恰好有10个高位和其余低位。原因是我有一个包含40个不同值的映射表，并且我想要将这些值中的任意10个相乘的所有不同方式求和。（这只是出于好奇心，所以真正重要的是“ bitmanip”循环，而不是总和本身。）

如果我要用例如4位中的2位来做到这一点，那么手动设置所有内容就很容易。

但是在40个数字中，我无法找到一种有效的方法来生成10个数字。我尝试从1023（=二进制中的1111111111）开始，寻找一种好的操作方式，但是没有成功。我一直在尝试用C++来完成这个任务，但实际上我更关心的是通用的方法（如果有的话）。我进行了一些谷歌搜索，但效果不佳，如果有人有好的链接，当然会很感激。

- triktae

5个回答

3

您可以简单地使用next_permutation。这里是一个示例，可以复制您的4个中取2个的情况（顺序略有变化）：

#include <iostream>
#include <algorithm>
using namespace std;
int main () {
 int bits[] = {0,0,1,1};

 do {
  for (int i = 0; i < 4; ++i) cout << bits[i] << " ";
  cout << endl;
 } while ( next_permutation (bits,bits+4) );
 return 0;
}

- Frank

这意味着每个“位”实际上是一个int，因此实际上有四个int被洗牌，而不是一个int内的四个位。这可能是一个很好的解决方案，但并不完全是我想要的。 - triktae

bitset会不会比bit[]更好呢？ - yesraaj

3

这个方法稍微复杂一些，但完全通过位运算实现。以你的例子为例：

#define WIDTH 4
#define BITS 2

void printbits(long pattern) {
  long bit;
  for (bit = 1L << WIDTH - 1; bit; bit >>= 1)
    putchar(pattern & bit ? 49 : 48);
  putchar('\n');
}

void movebits(pattern, bit) {
  long mask = 3L << bit;
  while (((pattern ^= mask) & mask) && (mask < 1L << WIDTH)) {
    mask <<= 1;
    printbits(pattern);
    if (bit)
      movebits(pattern, bit - 1);
  }
}

int main() {
  long pattern = (1L << BITS) - 1L, mask;
  printbits(pattern);
  movebits(pattern, BITS - 1);
}

您的真实应用程序：

#define WIDTH 40
#define BITS 10

同时，正如polygenelubricants所言，准备等待一段时间 :) 当然，你将用对你更加有用的内容替换printbits...

(因测试不充分而进行编辑 :/ 该死的打字错误...)

- Amadan

完美。或者至少非常接近。(只需要使用更长的整数。) 现在我只需要坐下来真正理解while循环的条件。实际上看起来很酷，观察那些1向左飞行。 :D - triktae

好的，这个想法是：我想将1向左移动，直到它碰到另一个1或者左边缘。因此，我假设有一个模式“...01...”，我会将其转换为“...10...”。最简单的方法是在适当的位置有一个掩码“11”，然后将其与模式进行异或操作（pattern ^= mask）。如果我已经撞到了另一个1，那么模式就会变成“...11...”，异或操作会得到“...00...”。因此，如果异或操作的位（通过AND忽略任何其他位）都是零，则满足我的其中一个结束条件（（pattern ^= mask）& mask）。 - Amadan

另一个条件(mask < 1 << WIDTH)仅设置最高位的边界，因为它没有任何东西可以碰撞，所以我检查掩码是否超过第4（或40）位。希望这有所帮助... - Amadan

确实很有帮助。我本来也会自己解决（希望如此），但看到解释可以加快过程。所以感谢您抽出时间。 - triktae

3

有一种非常不明显的高效方法：使用Gosper方法找到下一个具有相同数量1位的更高整数，来自HAKMEM项目175。

lowest_1_bit = prev_combo & -prev_combo;
tmp = prev_combo + lowest_1_bit;
new_combo = (((prev_combo ^ tmp) >> 2) / lowest_1_bit) | tmp;

第一行找到最右边的1位；
第二行将最右边的一串1位变成0，并将这串的左侧0变成1；
第三行在字的底部替换第二行中丢失的1位。

现在（假设您使用的是64位整数类型），您可以从1023开始反复应用此过程（直到结果超过1<<40）。

- Matthew Slattery

这个很顺利。我尝试阅读HAKMEM论文，但至少对我来说，C++语法更容易，所以感谢您的精美翻译。 - triktae

1

如果您将其重写为一组指示位位置的嵌套循环，那么这将更容易：

也就是说，第一个位的位置P1从0到3-1，第二个位的位置P2从P1+1到3重复运行。将其转化为通用递归函数留作练习。

- MSalters

谢谢。锻炼总是有益的。还要感谢您的编辑，那是我自己的愚蠢错误。 - triktae

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- polygenelubricants · Accepted Answer

您可以使用任何标准的选择/组合算法。基本上，您要从40个位中选择10个位，将它们设置为1。

话虽如此，40个里选10个有847,660,528种可能。并且这个数字将乘以不在前40位的任何可能的“尾”位数。假设尾部位没有受到任何规则的限制，因此如果有k位，则会再增加一个2^k的因子。

即使您实现了这个算法，它也会非常慢。最好考虑更好的方法来解决您所面临的问题。

位操作，位重排

相关问题