Lan*_*ard 6 javascript arrays algorithm math binary
你如何取一个代表项目列表的数字，并将其划分为块，其中块的数量是 2 的幂，并且每个块也有项目的 2 的幂（大小去最多为 2 的最大幂，所以 1、2、4、8、16、32、32 是最大值）？这甚至可能吗？
因此，例如，8 个项目可以分为 1 个桶（两个桶的幂）和 8 个项目（两个项目的幂）：
[8]
9个项目可能是：
[8, 1]
这是有效的，因为两个数字都是 2 的幂，并且数组的大小是 2（也是 2 的幂）。
让我们试试 11：
[8, 2, 1]
不，那不起作用。因为数组的大小是 3，它不是 2 的幂，即使它加上 11。这个怎么样？
[4, 4, 2, 1]
那个有效！它是 4 个元素，是 2 的幂。
[2, 2, 2, 1, 1, 1, 1, 1]
这也有效，因为有 8 个桶（8 是 2 的幂），每个桶有 1 或 2 个项目（每个是 2 的幂）。但[4, 4, 2, 1]更好，因为它更短。
我想一个更好的（在收到评论后）会是这个，虽然我第一次没有看到它：
[8, 1, 1, 1]
那个很短，也是从最大的数字开始的。
因此，按照这种模式，这里有一些其他数字：
13：
[8, 1, 1, 1, 1, 1] // no, 6 not power of 2
[8, 2, 1, 1, 1] // no, 5 not power of 2
[8, 2, 2, 1] // yes, 4 is power of 2
[8, 4, 1] // no, 3 not power of 2
14：
[8, 2, 2, 2]
15：
[8, 4, 2, 1]
16：
[16]
18：
[16, 2]
200：
[32, 32, 32, 32, 32, 32, 4, 4]
当桶树中第一层桶的大小增长到超过 32 时，则进行嵌套。所以以数字 1234 为例。这可以用 38 个 32 后接 16 个再接 4 来表示。
[32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 16, 4]
但是现在桶的大小是 40 个项目，这不是 2 的幂并且它大于 32。所以它应该嵌套！我无法在脑海中完全想象这一点，很抱歉，如果这不是一个完美的例子，我想你可以理解我的意思。
// the parent "x" is 2 in length
x = [a, b]
// child "a" is 32 in length
a = [32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32,
32, 32, 32, 32, 32, 32, 32, 32]
// child "b" is 8 in length
b = [32, 32, 32, 32, 32, 32, 16, 4]
再上一层，假设我们有一个非常大的数字（我不知道最小的大数字是多少），需要另一层嵌套。关于这一层，我们可以说的是，x长度为 32，但我们也会有一个y至少为 1 的。
_x_ = [a, b, c, d, e, f, g, h,
i, j, k, l, m, n, o, p,
q, r, s, t, u, v, w, x,
y, z, a2, b2, c2, d2, e2, f2]
_y_ = [a3]
a = [32, 32, 32, ..., ?]
...
f2 = [32, ..., ?]
然后，一旦我们有_x_，_y_，_z_，... 32总的这些，我们建立在顶部的另一个层。
什么是算法/方程，它将采用一个数字并将其划分为这个桶/项目大小的树，这些树的大小都是 2 的幂，最大为 32（在本例中为 32）？
一个子目标是最小化级别的数量。没有特定的限制，但我想象在整个运行时不超过 100 万个或最多 10 亿个节点，所以看起来你可能只有 3 或 4 个级别，我不知道具体如何来计算它。
这将用于数组查找。从本质上讲，我将一个单一的、大的、任意大小的“连续”数组分解为大小为 2 的幂的小连续块，长度可达 32。这平衡了查找性能（即适合 cpu 缓存）与内存碎片。
更新：
我认为尝试以某种方式合并它以构建我试图描述的嵌套树会有所帮助。现在缺少的最后一件事是使嵌套数组的大小正确地调整为二的幂值......
到目前为止我能做的最好的是：
这是一个可能的算法：
\n检查输入数字n的最低5位，并在数组中生成相应的2的幂。例如对于n = 13，我们得到 [1, 4, 8]
\n除n除以32，忽略上述位（下限）。
\n将n 模 32的值添加到上面的数组中。例如，对于输入 = 77，我们得到 [1, 4, 8, 32, 32]
\n大多数情况下，该数组的长度不会超过 32，但最多可达 36：[1, 2, 4, 8, 16, 32, ..., 32]。如果发生这种情况，请从数组末尾提取 16 个值并将它们存储在“进位”中：此进位将在稍后处理。因此，不考虑这种潜在的进位，我们确保最终得到的数组不长于 32。
\n然后将数组中的最大值分成两半（从而使数组增加一个单位），直到数组的长度为 2 的幂。例如，对于 77 的情况，我们将有几个进行这样的迭代以获得 [1, 4, 8, 8, 8, 16, 16, 16]
\n除n32，忽略余数（下限）。
\n再次考虑n 模 32。如果它不为零，我们就找到了 32*32 的被加数，因此我们为每个被加数创建一个新数组 [32, ..., 32]，并将其与之前建立的数组组合成一个新树。例如对于 1037，我们可以得到
\n[\n [1,4,4,4],\n [32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32]\n]\n如果有空间添加潜在进位（即顶层数组的长度不是 32），则这样做。
\n如果数组的长度还不是 2 的幂，请应用与前面提到的类似的算法，尽管现在分成两半涉及数组而不是原始值。
\n重复除以 32 以确定更高的嵌套被加数，因此这些是完整的 32*32*32 树，然后在下一次迭代中，这些是完整的 32 4树，依此类推，直到所有n都被计算在内。
\n最后，检查进位是否仍然存在并且无法添加到某处：如果是这种情况，请向树（顶部）添加一个额外的级别，以将实现的结果与此进位组合起来，因此它们是兄弟姐妹2 的数组。
\n这是一个交互式片段：输入一个数字，生成的树将实时显示。请注意，嵌套树实际上是在此实现中创建的，并且会消耗相当多的内存，因此为了保持 JavaScript 中可接受的响应时间，我将允许的输入限制为 7 位数字，但理论上唯一的限制是内存和浮动点精度（在此脚本中保证高达 2 53）。
\n[\n [1,4,4,4],\n [32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32]\n]\n// Utility functions\nconst sum = arr => arr.reduce((a, b) => a+b, 0);\nconst powersOf2andZero = [0,1,2,4,8,16,32];\nconst clone = tree => JSON.parse(JSON.stringify(tree));\n\nfunction createTree(n) {\n let tree = [];\n let carry = null;\n // Isolate 5 least significant bits\n for (let pow of [1, 2, 4, 8, 16]) if (n & pow) tree.push(pow);\n n = Math.floor(n / 32);\n for (let i = n % 32; i > 0; i--) tree.push(32);\n // This array could have more than 32 values, up to 36.\n // If that happens: remove 16 occurrences of 32, and consider this as carry-over for later treatment.\n if (tree.length > 32) carry = tree.splice(-16); // pop off 16 x 32s.\n // Make the array length a power of 2 by splitting the greatest value (repeatedly)\n let j = tree.length;\n while (!powersOf2andZero.includes(tree.length)) {\n if (j >= tree.length) j = tree.indexOf(tree[tree.length - 1]); // first occurrence of greatest\n // Split greatest value into 2; keep list sorted\n tree.splice(j, 1, tree[j] / 2, tree[j] / 2); // delete, and insert twice the half at same spot\n j += 2;\n }\n // Isolate and count factors of 32, 32\xc2\xb2, 32\xc2\xb3, ...etc. \n // Add a superiour level in the tree for each power of 32 that is found:\n n = Math.floor(n / 32);\n let template = 32;\n while (n) {\n if (tree.length > 1) tree = [tree]; // nest\n if (n % 32 < 31 && carry !== null) { // we have room to dump the carry here\n tree.push(carry);\n carry = null;\n }\n template = Array(32).fill(template); // nest the template tree, "multiplying" by 32.\n for (let i = n % 32; i > 0; i--) tree.push(clone(template));\n if (tree.length === 1 && typeof tree[0] !== "number") tree = tree[0]; // Eliminate useless array wrapper\n // Turn this top level into a length that is a power of 2 by splitting the longest array (repeatedly)\n let j = tree.length;\n while (!powersOf2andZero.includes(tree.length)) {\n if (j >= tree.length) j = tree.findIndex(elem => elem.length === tree[tree.length - 1].length);\n // Split longest array into 2; keep list sorted\n let size = tree[j].length / 2;\n tree.splice(j, 1, tree[j].slice(0, size), tree[j].slice(size)); // delete, and insert twice the half\n j += 2;\n }\n n = Math.floor(n / 32);\n }\n // Is the carry still there? Then we cannot avoid adding a level for it\n if (carry) return [tree, carry];\n return tree;\n}\n\n// I/O handling\nlet input = document.querySelector("input");\nlet output = document.querySelector("pre");\n\n(input.oninput = function () {\n let n = +input.value;\n if (isNaN(n) || n % 1 !== 0 || n < 1 || n > 9999999) {\n output.textContent = "Please enter an integer between 1 and 9999999";\n } else {\n let tree = createTree(n);\n output.textContent = pretty(tree);\n }\n})();\n\nfunction pretty(tree) {\n return JSON.stringify(tree, null, 2)\n .replace(/\\[\\s*\\d+\\s*(,\\s*\\d+\\s*)*\\]/g, m => m.replace(/\\s+/g, ""))\n .replace(/\\b\\d\\b/g, " $&");\n}pre { font-size: 8px }