Java - bitCount() 的大O复杂度是什么？

Question

bit count的时间复杂度是什么？我不确定这个方法如何工作，但我认为它应该在O(logn)时间内完成。

具体来说，对于这段代码（其中x = 4，y = 1）：

return Integer.bitCount(x^y);

- data_pi

---

你的 O(log n) 中的 n 是什么？整数中的总位数吗？在谈论大 O 时，我们将某些任意操作的成本设置为1，并且可以合理地假设 bitCount 的成本为1。 - Mephy

实际上，我认为它是O(1)，参见例如：https://dev59.com/2HM_5IYBdhLWcg3wQQpd - jonrsharpe

Answer 1

根据其实施方式，该方法由六个O(1)语句按顺序执行组成，因此它是O(1)。

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

- RedXIII

---

JVM可以自由地实现与JDK源代码中所见不同的方式，事实上它确实这样做，因为它是一个“已知函数”。通常，在支持它的平台上（大多数有趣的平台），它会编译成单个popcnt指令。虽然这并不真正改变结论（尽管这意味着Integer.bitCount()和Long.bitCount()通常需要相同的时间 - 如果您查看源代码，这将不是您的结论）。 - BeeOnRope

Answer 2

它是O(1)，以下是针对JDK 1.5+的实现：

public static int bitCount(int i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

- syntagma

---

是的，你必须深入研究JVM的C++源代码。要查看方法是否被内置，请查看您所使用JVM版本的vmSymbols.hpp并查找函数名称。在这种情况下，您会发现一行类似于do_intrinsic(_bitCount_i, java_lang_Integer, bitCount_name, int_int_signature, F_S)的代码，这表明该函数_可能_是内置函数。 - BeeOnRope

...既然我要详尽地说明，另一种方法是将JDK复制并重命名函数，然后对比原始副本和精确副本的基准测试。如果它不是内在代码，你应该得到相同的时间。我现在尝试了一下，在Integer.bitCount()中，我每秒获得了约20亿次调用bitCount，而对于JDK代码的精确副本，我只获得了4亿次/秒。 - BeeOnRope

@BeeOnRope 我不知道JVM可以取代现有的源代码实现。这个概念是否在JLS中有涉及？此外，内部方法和本地方法之间到底有什么区别？ - shmosel

据我所知，所有内置方法也都有JDK实现，这实际上是一般规则。实现需要存在，因为(a)并非所有平台都支持内置版本，(b)有时不使用内置版本（例如在解释器中）或调试时，以及(c)原则上JDK源代码可移植到不将东西内置到JVM实现的情况下。你在JLS中找不到任何提及此事的地方 - 它在更低的级别上。即使是JVM规范也不会提到它。这就像C++编译器识别memcpy并经常替换它一样。 - BeeOnRope

@shmosel - native 方法非常不同。这是 JVM 规范的一部分（可能 JLS 中也简要提到了 native 关键字），用于实现 JNI 方法。基本上，你有一个 C 类似的函数在某些二进制文件中，该函数被调用并执行其工作，然后返回。有关如何传递参数和其他各种事项的规则。它应该在任何平台上都可以工作，等等 - 尽管当然你需要为不同的体系结构包含不同的库。 - BeeOnRope

Answer 3

任何处理有限大小输入的算法复杂度都是O(1)。

bitCount适用于有限大小的输入。

因此，bitCount的复杂度为O(1)。

- talex