java - 位移时间复杂度

Question

我想知道右移位运算符的时间复杂度是多少 >>，最好是在 Java 中，如果可能的话，还有其他语言，如 C、Python 等。是 O(n) 还是 O(1)，其中“n”是移位的位数。我不是在寻找一般性答案，因为我知道实现细节各不相同。我想知道哪些常数需要时间 O(1)，哪些需要 O(n) 时间。

Answer 1

在 Java 中，原始整数类型具有固定宽度，即 64、32、16 位。比特数的移位是比特数的模。因此，出于实际目的，您可以假设位移是常数时间，即使对于 1L << 63 也是如此。你必须做 63 个单独的类次。

这同样适用于语言类型可映射到机器类型的任何语言/CPU 组合。

Java 也有 BigInteger 类型，其他语言也有任意大小的整数类型，其中数字实际上可以有任意位数。我的猜测是这种情况下的移位是 O(n)，其中 n 是 BigInteger 中的位数。