是否可以计算O（1）中数字中的Set位数？[重复]

Question

我在一次面试中被问到上述问题，面试官对答案非常肯定。但是我不确定。有人能帮我吗？

Answer 1

有些处理器可以在一条指令中完成，显然是针对有限大小的整数。查找POPCNT助记符以了解更多详细信息。

对于无限大小的整数，显然你需要读取整个输入，所以下限是O(n)。

面试官的意思可能是比特计数技巧（下面是第一个谷歌结果）：http://www.gamedev.net/topic/547102-bit-counting-trick---new-to-me/

Answer 2

如果位大小是固定的（例如，32位或64位机器的自然字大小），您只需迭代这些位，并在O（1）时间内直接计数（尽管肯定有更快的方法）。对于任意精度的数字（BigInt等），答案必须是否定的。

Answer 3

当然可以。显而易见的强力方法只是一个大的查找表，对于输入数字的每个可能值都有一个条目。如果数字很大，这就不太实际了，但仍然足以证明这是可能的。

编辑:有人认为这完全是胡说八道，基本上任何算法都是如此。

在有限的程度上，这是一个公平的说法 - 但限制是如此严重，以至于对于大多数算法来说，它仍然完全没有意义。

我最初的观点（至少和我记得的一样）是，人口计数大约等同于许多其他运算，如我们通常假设的加法和减法是O（1）。

在硬件级别，单周期< code>POPCNT指令的电路可能比单周期< code>ADD指令的电路简单。仅举一个例子，对于任何实际大小的数据字，我们可以在4位块上并行使用表查找，然后将这些块的结果相加。即使使用相当不可能的最坏情况假设(例如，每个表都有单独的存储)，这在现代CPU中仍然很容易实现——事实上，它可能至少比上面提到的单周期加法或减法简单一些。

这与许多其他算法形成鲜明对比。对于一个明显的例子，让我们考虑排序。即使是大多数人能想象到的最微不足道的排序——2个项目，每个8位，我们已经在一个64千字节的查找表中获得了恒定的复杂性。早在我们能做一个相当微不足道的排序（例如，100个项目）之前，我们就需要一个查找表，它包含的数据项远远超过宇宙中的原子。

从相反的方向看，在某些时候，基本上没有什么是O（1）了，这是真的。让我们考虑一下最微不足道的操作。对于 N 位 CPU，按位 OR 通常作为一组并行的 N 个 OR 门实现。与加法不同，一个位和另一个位之间没有交互，因此对于任何实际大小的 CPU，这很容易在单个指令中执行。

尽管如此，如果我指定一个按位OR，其中每个操作数为100 PB，那么甚至没有任何实用的方法可以以恒定的复杂性完成这项工作。使用并行OR门的通常方法，我们最终得到（除其他外）价值300 PB的输入和输出行——这个数字甚至完全使最大CPU上的引脚数量相形见绌。

在合理的硬件上，对100千兆位操作数执行按位OR需要一段时间（更不用说相当大的硬盘空间了）。如果我们将其增加到200千兆位操作数，时间可能会增加一倍——所以从这个角度来看，这是一个O（N）操作。显然，其他“琐碎”操作也是如此，如加法、减法、按位AND、按位XOR等等。

尽管如此，除非你有非常具体的指令说你将要处理非常巨大的操作数，你通常会把其中的每一个都当作一个恒定复杂度的操作。从这些方面来看，就在固定时间内执行的难度而言，POPCNT指令一方面处于按位< code > AND /< code > OR /< code > XOR 之间，另一方面处于加法/减法之间。

< sub>1。您可能想知道它怎么可能比< code>add更简单，因为它在完成一些其他操作后实际上包含了一个< code>add。如果是这样的话，这是一个很好的问题。

< sub >答案是因为它只需要一个小得多的加法器。例如，64位CPU需要一个半加法器和63个全加器。在简单的实现中，您按位执行加法，也就是说，您将一个操作数的位0加到另一个操作数的位0。其产生输出位和进位位。该进位比特成为下一对比特的加法的输入。有一些技巧可以在某种程度上实现并行化，但是这种野兽的本性(可以这么说)是位串行的。

< sub >使用POPCNT指令，我们在执行单个表查找后有一个加法，但是我们的结果受限于输入字的大小。给定相同大小的输入(64位)，我们的最终结果不会大于64。这意味着我们只需要一个6位加法器，而不是64位加法器。

_{由于如上所述，加法基本上是位串行的，这意味着POPCNT指令末尾的加法基本上比普通加法快得多。具体来说，它在操作数大小上是对数的，而简单加法在操作数大小上大致是线性的。}