What is the time complexity of bitwise operations in python?

Question

Usually we consider bitwise operations to have O(1) worst-case time complexity because of built-in hardware support in most platforms. Since python ints can represent numbers in an unlimited range, which do not in general fit into a CPU-word, I would like to know what are the worst-case time complexities of the different bitwise operations on ints in general, and also specifically for ints that actually do fit in a cpu-word.

Answer 1

You really give all the ingredients for the answer.

Quoting from 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).

This confirms what you wrote, i.e. that Python integers are represented as an array of fixed sized words.

So bit operations will have a time complexity that is O(k) where k is the total size of such array(s). Or, if we want to express this in terms of the value n of the integer involved, it is O(logn).