这对我来说一直是一个挑战。
给定两个表示二进制数的数组，A 和 C，具有相同的大小，由数字 0 或 1 表示的位组成，使得 C > A，并且两者都有相同的 X 个 1 位，那么计算存在多少个二进制文件 B 的最有效方法，使得 A < B < C，并且每个 B 也有 X 个 1 位？
示例:对于 A={0,1,0,0,1} C={1,0,1,0,0} X=2
所有 B 均为 {0,1,0,1,0},{0,1,1,0,0},{1,0,0,0,1},{1,0,0,1,0 }，这将给我答案 4。在 01001 和 10100 之间有 4 个带有 2 个“1”位的二进制文件。
我有一个算法可以在给定一些 A 的情况下生成下一个 B，但我觉得继续生成下一个 B 并检查我是否已经命中 C 二进制文件效率不高。
有什么方法可以计算A和C之间B的确切数量而不生成B吗？
最佳答案
不知道您是否对https://math.stackexchange.com/有答案，但让我尝试一下。
在下面的所有讨论中，我们只对 X 的数字感兴趣1 位。为了简单起见，我不会一直这么说。
因此，假设我们可以计算低于给定值 A 的数字计数:smaller(A) 。查找 A 之间的数字计数和C ，我们可以计算为 smaller(C) - smaller(A) - 1 .
让我们定义一个函数，计算 Y 位空间中存在多少个 X 位数字，count(X, Y) ，例如count(1, 3) = 3 ( 001 、 010 、 100 )和 count(2, 3) = 3 (011、101、110)。这是标准的组合数学，即从袋子中拉出编号为 1 到 Y 的 X 个球的组合数。
count(X, Y) = Y! / ((Y-X)! * X!)
哪里X!是 factorial(X) .
现在我将展示下一部分，如何计算smaller(A) ，使用一个例子。让A = 010010100 .
首先，数一下右边的 0 (2)。那么有count(1, 2)以下数字 A其中最右边的 1 位向右移动( 010010010 、 010010001 )。
提示:使用 count = Integer.numberOfTrailingZeros(A)
删除该 1 位，留下 A = 010010000 .
提示:使用 A = A ^ (1 << count)
重复，即计数 0 (4)，但这次我们需要计数 2 位组合，即 count(2, 4) .
剩下 A = 010000000 ，这导致 count(3, 7) .
因此，由于 1 位位于第 2、4 和 7 位，因此我们可以计算:
smaller(A) = count(1, 2) + count(2, 4) + count(3, 7)
现在，有了 count(X, Y) 的高效实现，计算 A 和 C 之间的数字计数应该不会太糟糕，即使对于高位数也是如此。
无论如何，这是一种方法，但是数学方面的天才可能有更好的算法。
关于java - 计算两个给定的具有相同属性的二进制数之间存在多少个具有 X 个 1 位的二进制数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/43359986/