python中按位运算的时间复杂度是多少？

Question

通常我们认为按位运算具有 O(1) 最坏情况时间复杂度，因为大多数平台都有内置硬件支持。由于 python ints 可以表示无限范围内的数字，通常不适合 CPU-word，我想知道最坏情况下的时间复杂度是多少int 上的不同按位运算，以及实际上适合 cpu 字的 int 的具体运算。

Answer 1

你真的给出了答案的所有成分。

引用自a blog by Victor Skvortsov：

Everything related to the representation of Python integers can be found in Include/longintrepr.h. Technically, Python integers are instances of PyLongObject, which is defined in Include/longobject.h, but PyLongObject is actually a typedef for struct _longobject that is defined in Include/longintrepr.h:
struct _longobject {
    PyVarObject ob_base; // expansion of PyObject_VAR_HEAD macro
    digit ob_digit[1];
};
This struct extends PyVarObject, which in turn extends PyObject:
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
So, besides a reference count and a type that all Python objects have, an integer object has two other members:

ob_size that comes from PyVarObject; and

ob_digit that is defined in struct _longobject.

The ob_digit member is a pointer to an array of digits. On 64-bit platforms, each digit is a 30-bit integer that takes values between 0 and 2^30-1 and is stored as an unsigned 32-bit int (digit is a typedef for uint32_t). On 32-bit platforms, each digit is a 15-bit integer that takes values between 0 and 2^15-1 and is stored as an unsigned 16-bit int (digit is a typedef for unsigned short).

这证实了您所写的内容，即 Python 整数表示为固定大小的单词数组。

所以位操作的时间复杂度是 O(k) 其中 k 是这样的数组的总大小（s ).或者，如果我们想用涉及的整数的 value n 来表达，那就是 O(logn) .

python中按位运算的时间复杂度是多少？

What is the time complexity of bitwise operations in python?

python

integer

time-complexity

bitwise-operators

built-in-types