计算给定的两个属性相同的二进制数之间有多少个1位为X的二进制数
Calculate how many binary numbers with X number of 1 bits exist between two given binary numbers with the same property
一段时间以来，这对我来说一直是一个挑战。
给定两个表示二进制数的数组，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 二进制文件效率不高。
有没有办法在不生成 B 的情况下计算 A 和 C 之间 B 的确切数量？
不知道您是否在 https://math.stackexchange.com/ 上找到了答案，但让我试一试。
在下面的所有讨论中，我们只对 X 1 位的数字感兴趣。为了简单起见，我不会一直这么说。
因此，假设我们可以计算低于给定值 A 的数字的计数：smaller(A)。要找到 A 和 C 之间的数字计数，我们可以将其计算为 smaller(C) - smaller(A) - 1.
让我们定义一个函数来计算在 Y 位 space、count(X, Y) 中存在多少个具有 X 位的数字，例如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)。然后 A 下面有 count(1, 2) 个数字，其中最右边的 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 之间的数字计数应该不会太糟糕，即使对于高位计数也是如此。
无论如何，这是一种方法，但数学方面的天才可能有更好的算法。
一段时间以来，这对我来说一直是一个挑战。
给定两个表示二进制数的数组，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 二进制文件效率不高。
有没有办法在不生成 B 的情况下计算 A 和 C 之间 B 的确切数量？
不知道您是否在 https://math.stackexchange.com/ 上找到了答案，但让我试一试。
在下面的所有讨论中，我们只对 X 1 位的数字感兴趣。为了简单起见，我不会一直这么说。
因此，假设我们可以计算低于给定值 A 的数字的计数：smaller(A)。要找到 A 和 C 之间的数字计数，我们可以将其计算为 smaller(C) - smaller(A) - 1.
让我们定义一个函数来计算在 Y 位 space、count(X, Y) 中存在多少个具有 X 位的数字，例如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)。然后 A 下面有 count(1, 2) 个数字，其中最右边的 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 之间的数字计数应该不会太糟糕，即使对于高位计数也是如此。
无论如何，这是一种方法，但数学方面的天才可能有更好的算法。