N位二进制数包含L个1

Question

有没有快速的算法可以存储所有包含L个1位元的N位元数？需要提供N和L参数。这是为了在课堂上破解加密系统，我注意到通过两次计时攻击可以找到比特长度（N）和1位元的数量（L）。

与其暴力测试下限和上限之间的所有值，我宁愿将需要测试的元素数量最小化。因此，我考虑使用一个向量来包含所有可能符合我从2次计时攻击获得的信息的元素。

非常感谢任何提示。

我使用的是C ++。

- adilip

---

N和L的范围是多少？有N!/(N-L)!/L!个数字，这可能很容易变成一个相当大的数字。 - Daniel Brückner

有N个选择L个可能性，如果L = N/2，那么比2^N少得不算太多（大约是2^N/sqrt(N)的数量级）。还有其他的侧信道吗？ - David Eisenstat

没有其他的副通道，N 的最大大小为 160 位。我希望这样会更可行一些。 - adilip

Answer 1

位操作技巧页面展示了如何使用每个生成的数字 O(1) 的工作量，列举所有恰好设置 n 位的二进制数。他们的解决方案在此处重印：

Suppose we have a pattern of N bits set to 1 in an integer and we want the next permutation of N 1 bits in a lexicographical sense. For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 00010101, 00010110, 00011001,00011010, 00011100, 00100011, and so forth. The following is a fast way to compute the next permutation.

unsigned int v; // current permutation of bits
unsigned int w; // next permutation of bits

unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1

// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

The __builtin_ctz(v) GNU C compiler intrinsic for x86 CPUs returns the number of trailing zeros. If you are using Microsoft compilers for x86, the intrinsic is _BitScanForward. These both emit a bsf instruction, but equivalents may be available for other architectures. If not, then consider using one of the methods for counting the consecutive zero bits mentioned earlier. Here is another version that tends to be slower because of its division operator, but it does not require counting the trailing zeros.

unsigned int t = (v | (v - 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

从所有数字都是0，除了最后L位都是1的数字开始，您可以使用这个数字来枚举您想要的所有数字。

希望这有所帮助！

- templatetypedef

---

谢谢！我相信那会有所帮助。 - adilip

Answer 2

该回答已经有了比我好的templatetypedef。我编写了一个递归算法来生成它们。这可能不是你想要的方式，但它似乎可以工作（免责声明：测试最少！）。

即使这可能不是完成此操作的最佳方法，我也会把它留在这里以供后人参考。与其他答案不同，这个答案将为您留下一个包含所有可能组合的向量。如果您有成千上万/数十亿的组合，则显然这不是理想的方法！但是，我想写一个算法来做到这一点，所以任务完成了。

#include <bitset>
#include <vector>
using namespace std;

const int N = 4;

void addValues(int to_add, int start_pos, bitset<N> const& working, vector<bitset<N>>& values)
{
  // Take all of our possible spots
  for (int i = start_pos; i < N && i <= N - to_add; ++i) {
    auto working_copy(working);
    working_copy[i] = 1;

    // We have more bits to set...
    if (to_add > 1) {
      addValues(to_add - 1, i + 1, working_copy, values);
    } 
    // We've set all the bits, so this is a working combination
    else {
      values.push_back(working_copy);
    }
  }
}

int main(int argc, char* argv)
{
  int L = 2;

  vector<bitset<N>> values;
  bitset<N> working;
  addValues(L, 0, working, values);

  return EXIT_SUCCESS;
}

- aardvarkk