algorithm - 是否可以计算O(1)中Number中的Set位数？

Question

This question already has answers here:

How to count the number of set bits in a 32-bit integer?
（53个答案）
Count bits in the number [duplicate]
（3个答案）
我在一次面试中被问到了上述问题，面试官非常肯定答案但我不确定。有人能帮我吗？

最佳答案

当然。显而易见的brute force方法只是一个大查找表，对于输入数字的每个可能值都有一个条目。如果这个数字很大，那就不太实际，但仍然足以证明这是可能的。
编辑：有人认为这完全是胡说八道，任何算法都是如此。
在有限的程度上，这是一个公平的声明——但是限制是如此严重，以至于对于大多数算法来说，它仍然毫无意义。
我最初的观点（至少我记得是这样）是，人口计数和我们通常认为是o（1）的加减运算差不多。
在硬件层面，单周期POPCNT指令的电路可能比单周期ADD指令的电路容易。仅举一个例子，对于任何实际大小的数据字，我们可以并行地对4位块使用表查找，然后将这些块的结果相加即使使用相当不可能的最坏情况假设（例如，为每个表单独存储），这在现代CPU中仍然很容易实现——事实上，它可能至少比上面提到的单周期加法或减法简单一些。
这与许多其他算法形成了明显的对比。举个明显的例子，让我们考虑排序即使是大多数人能想象到的最琐碎的事情——2个项目，8个比特，我们已经在一个64千字节的查找表上，以获得不断的复杂性。很久以前，我们甚至可以做一个相当琐碎的排序（例如，100项），我们需要一个查找表，其中包含的数据项远远多于宇宙中的原子。
从相反的方向来看，在某个点上，本质上没有什么是o（1）了，这是肯定的。让我们考虑可能的最琐碎的操作对于N位CPU，按位OR通常被并行地实现为一组NOR门与加法不同的是，一个位和另一个位之间没有交互，所以对于任何实际大小的CPU，这很容易在一条指令中执行。
然而，如果我指定一个稍微明智的cc，其中每一个操作数是100个字节，那么就没有一个接近实际的方法来完成复杂的任务。使用通常的并行OR门的方法，我们最终得到了（除其他外）300千兆位的输入和输出线——这个数字甚至使最大CPU上的管脚数都相形见绌。
在合理的硬件上，对100 PB的操作数执行按位OR操作需要一段时间（更不用说相当大的硬盘空间了）如果我们将其增加到200 PB的操作数，时间可能会（大约）翻倍——因此从这个角度来看，这是一个O（N）操作显然，对于其他“琐碎”操作，如加法、减法、按位OR、按位AND，等等，也是如此。
尽管如此，除非你有非常明确的指示，你将要处理完全巨大的操作数，你通常会把每一个都视为一个不断复杂的操作。从这些术语来看，popcnt指令一方面介于按位XOR/AND/OR之间，另一方面介于加减之间，因为在固定时间内执行起来很困难。
一。您可能想知道，在执行一些其他操作之后，如果它实际上包含一个XOR，那么它怎么可能比add简单如果是的话，库多斯——这是个很好的问题。
答案是因为它只需要一个小得多的加法器。例如，64位CPU需要一个半加器和63个全加器。在简单的实现中，按位执行加法——即，将一个操作数的位-0与另一个操作数的位-0相加它产生一个输出位和一个进位。该进位成为下一对位的加法的输入。有一些技巧可以在某种程度上与之相类似，但野兽的本性（可以说）是有点连续的。
对于popcnt指令，我们在进行单独的表查找之后有一个加法，但是我们的结果仅限于输入字的大小。给定相同大小的输入（64位），我们的最终结果不能大于64位。这意味着我们只需要6位加法器而不是64位加法器。
如上所述，加法基本上是位串行的，这意味着add指令末尾的加法基本上比普通加法快得多。具体来说，它在操作数大小上是对数的，而简单加法在操作数大小上大致是线性的。

关于algorithm - 是否可以计算O(1)中Number中的Set位数？ ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10344022/

上一篇：algorithm - 高功率和 double

下一篇：c - 在 C 中通过指针为结构中的变量赋值

Answer 1

当然。显而易见的brute force方法只是一个大查找表，对于输入数字的每个可能值都有一个条目。如果这个数字很大，那就不太实际，但仍然足以证明这是可能的。
编辑：有人认为这完全是胡说八道，任何算法都是如此。
在有限的程度上，这是一个公平的声明——但是限制是如此严重，以至于对于大多数算法来说，它仍然毫无意义。
我最初的观点（至少我记得是这样）是，人口计数和我们通常认为是o（1）的加减运算差不多。
在硬件层面，单周期POPCNT指令的电路可能比单周期ADD指令的电路容易。仅举一个例子，对于任何实际大小的数据字，我们可以并行地对4位块使用表查找，然后将这些块的结果相加即使使用相当不可能的最坏情况假设（例如，为每个表单独存储），这在现代CPU中仍然很容易实现——事实上，它可能至少比上面提到的单周期加法或减法简单一些。
这与许多其他算法形成了明显的对比。举个明显的例子，让我们考虑排序即使是大多数人能想象到的最琐碎的事情——2个项目，8个比特，我们已经在一个64千字节的查找表上，以获得不断的复杂性。很久以前，我们甚至可以做一个相当琐碎的排序（例如，100项），我们需要一个查找表，其中包含的数据项远远多于宇宙中的原子。
从相反的方向来看，在某个点上，本质上没有什么是o（1）了，这是肯定的。让我们考虑可能的最琐碎的操作对于N位CPU，按位OR通常被并行地实现为一组NOR门与加法不同的是，一个位和另一个位之间没有交互，所以对于任何实际大小的CPU，这很容易在一条指令中执行。
然而，如果我指定一个稍微明智的cc，其中每一个操作数是100个字节，那么就没有一个接近实际的方法来完成复杂的任务。使用通常的并行OR门的方法，我们最终得到了（除其他外）300千兆位的输入和输出线——这个数字甚至使最大CPU上的管脚数都相形见绌。
在合理的硬件上，对100 PB的操作数执行按位OR操作需要一段时间（更不用说相当大的硬盘空间了）如果我们将其增加到200 PB的操作数，时间可能会（大约）翻倍——因此从这个角度来看，这是一个O（N）操作显然，对于其他“琐碎”操作，如加法、减法、按位OR、按位AND，等等，也是如此。
尽管如此，除非你有非常明确的指示，你将要处理完全巨大的操作数，你通常会把每一个都视为一个不断复杂的操作。从这些术语来看，popcnt指令一方面介于按位XOR/AND/OR之间，另一方面介于加减之间，因为在固定时间内执行起来很困难。
一。您可能想知道，在执行一些其他操作之后，如果它实际上包含一个XOR，那么它怎么可能比add简单如果是的话，库多斯——这是个很好的问题。
答案是因为它只需要一个小得多的加法器。例如，64位CPU需要一个半加器和63个全加器。在简单的实现中，按位执行加法——即，将一个操作数的位-0与另一个操作数的位-0相加它产生一个输出位和一个进位。该进位成为下一对位的加法的输入。有一些技巧可以在某种程度上与之相类似，但野兽的本性（可以说）是有点连续的。
对于popcnt指令，我们在进行单独的表查找之后有一个加法，但是我们的结果仅限于输入字的大小。给定相同大小的输入（64位），我们的最终结果不能大于64位。这意味着我们只需要6位加法器而不是64位加法器。
如上所述，加法基本上是位串行的，这意味着add指令末尾的加法基本上比普通加法快得多。具体来说，它在操作数大小上是对数的，而简单加法在操作数大小上大致是线性的。