位移时间复杂度
Bitshift time complexity
我想知道右移位运算符 >> 的时间复杂度是多少，最好是 java，如果可能的话还有其他语言，如 C、Python ... 等等。是 O(n) 还是 O(1)，其中 'n' 是移位的位数。我不是在寻找一般性答案，因为我知道实施细节各不相同。我想知道哪些是常数需要时间 O(1)，哪些需要 O(n) 时间。
在Java中，原始整数类型是固定宽度的，即64、32、16位。比特数的移位是比特数的模。因此，出于实际目的，您可以假设位移是常数时间，即使对于 1L << 63 您必须进行 63 次单独的位移。
这同样适用于语言类型可映射到机器类型的任何 language/CPU 组合。
Java 也有一个 BigInteger 类型，其他语言也有任意大小的整数类型，其中数字实际上可以有任意位数。我的猜测是这种情况下的移位是 O(n)，其中 n 是 BigInteger 中的位数。
我想知道右移位运算符 >> 的时间复杂度是多少，最好是 java，如果可能的话还有其他语言，如 C、Python ... 等等。是 O(n) 还是 O(1)，其中 'n' 是移位的位数。我不是在寻找一般性答案，因为我知道实施细节各不相同。我想知道哪些是常数需要时间 O(1)，哪些需要 O(n) 时间。
在Java中，原始整数类型是固定宽度的，即64、32、16位。比特数的移位是比特数的模。因此，出于实际目的，您可以假设位移是常数时间，即使对于 1L << 63 您必须进行 63 次单独的位移。
这同样适用于语言类型可映射到机器类型的任何 language/CPU 组合。
Java 也有一个 BigInteger 类型，其他语言也有任意大小的整数类型，其中数字实际上可以有任意位数。我的猜测是这种情况下的移位是 O(n)，其中 n 是 BigInteger 中的位数。