以精确数量获取项目的算法

Question

我已经在两款游戏中发现了这种算法/功能，但我一直想知道它背后的逻辑是什么。基本上，有一个项目列表，每个项目都有一个 id。例如：item_1 的 ID：1item_2 的 ID：2item_3 的 ID：4item_4 有 id：8item_5 的 ID：16等等每个新项目都会将 id 乘以 2。然后有一个数字，比方说 4，表示当前项目是什么。这种情况是item_3，但棘手的部分是数字也可以一次选择多个项目，例如 7 是 4 + 2 + 1 ( item_3, item_2, item_1) 或 17 是 16 + 1 ( item_5, item_1)。如果您有一个长列表并且对于多个选择仍然非常准确，它可以像 16384 一样非常高。我该如何解决这个问题？

Answer 1

您描述的算法基本上是输出 1 在数字的二进制表示中的位置。

对于 7，它的二进制表示是111。有三个1：分别在左起第一、第二、第三个位置，所以是第1、2、3项。注意我们是从左边数的。

另一个例子：

对于 10，它的二进制表示是1010。有两个 1：在左起第二个和第四个位置，因此输出将是第 2 项和第 4 项。

这是 C# 中的一个实现。

public static List<int> FindOnes(int number) {

    var list = new List<int>();

    var binaryString = Convert.ToString(number, 2);

    for (int i = 0 ; i < binaryString.Length ; i++) {

        if (binaryString[binaryString.Length - i - 1] == '1') {

            list.Add(i + 1);

        }

    }

    return list;

}

// usage:

FindOnes(7) // [1,2,3]

Answer 2

不知道你正在谈论的游戏是如何实现它的，但如果这是我，我会使用数字的二进制表达式中的位来实现它（java 中的示例代码）。

public boolean isItemSelected(final int number, final int itemId) {

    return (number & (1 << (itemId - 1))) != 0;

}

这里的技巧是数字的二进制表示（从右到左）已经表示是否需要 1、2、4、8、16 等，以便仅使用 2 的幂来生成数字。左移只是使一个数字（二进制）全为 0，除了“itemId - 1”中的 1。如果该位1在给定的number. 然后检查结果是否简单 0地将其转换为boolean.

显然，如果你想构建所有匹配的“itemIds”的数组/列表，你可以将它与一些循环或其他任何东西结合起来。

Answer 3

在 Javascript 中，您可以获取数字，将其转换为二进制值，获取位，将其反转并获取值（索引加一）或零以过滤真值。

var value = 13,

    items = [...value.toString(2)].reverse().map((v, i) => +v && (i + 1)).filter(Boolean);

console.log(items);