python中按位操作的时间复杂度是多少？

Question

通常我们认为，由于大多数平台内置硬件支持，逐位运算具有o> EEM>（1）最坏情况下的时间复杂度。由于pythonint可以表示无限范围内的数字，这些数字通常不适合CPU字，因此我想知道一般情况下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是此类数组的总大小。或者，如果我们想用所涉及整数的值n来表示，它就是O（logn）