multibit_manipulation.py

"""Bit integer manipulation, both single bit and multi-bit list-like
   slicing functions ( get, set, insert, remove ) implemented with
   builtin bitwise operations.

See:
https://high-python-ext-3-algorithms.readthedocs.io/ko/latest/chapter5.html#insert-bit
https://en.wikipedia.org/wiki/Bit_manipulation#Bit_manipulation_operations
https://github.com/billbreit/BitWiseApps

All parameters must be must be int >= 0, referred to as a 'bit integer'.

 bint:int
   The bit integer to be accessed or returned as modified.

 index:int
   The offset into the bit position from right,
      0b010111 -> list [1,1,1,0,1,0]. big-endian -> little-endian
   For inserts, index is the position to the right of index,
      index 0 -> right of rightmost bit.
   For gets, sets and removes, it is the position of the bit itself.

 value:int
   Either [0,1] for single bit, or int value for multibit,
      bit_length(value) <= bitlen.

 bitlen:int
   The effective mask length, spec. leading zeros
      ( bitlen 4 value 1 -> 0001 )

The bitwise expressions may look convoluted, but basically, there are
just three parts: left-hand side, value, right-hand side.

For example, say you want to insert two ones in the middle of 0b101101,
that is ->  0b10111101.  Index is 2 ( 0 ,1, 2 from the right ) and the
value is 3 (0b11) with a bit length of 2.

- Shift >> index right to produce 0b101
- Shift left << bit length to produce 0b10100.
- OR in the ones producing 0b10111.
- Left shift << index producing 0b10111000.
- Using a bit mask (1 << index)-1 -> 0b111, AND with the original bint,
  ( 0b101101 & 0b111 ) -> 0b101.
- OR that into the working 0b10111000, that is, ( 0b10111000 | 0b101 )
  -> 0b10111101.

To remove the center two bits of 0b101101 -> 0b1001, the process is mostly
the same.

- The initial right shift is index(2) + bit_length(2), taking out the two
  middle bits and producing 0b10.
- The left shift of index produces 0b1000.
- The original bint is ANDed with bitmask 0b11 producing 0b01 which is
  ORed with 0b1000 yielding the target 0b1001.

It's not so bad once you get the hang of it.

Various bit insert/remove solutions exist using bin() string functions
and slicing, but this bitwise implementation is significantly faster
(about 3x) on Python for big ints (2^100).

See https://github.com/billbreit/BitWiseApps/blob/main/dev/time_ops.py

"""

bit_length = int.bit_length

"""The only consistent error checking is for bint < 0 or index < 0 etc.,
   and for bit_length(value) > bit_len, which can cause silent errors.
   Anything like int(None) is going to cause a loud error. """


def bit_get(bint: int, index: int) -> int | None:
    """Get value of bit at index in bint.

    >>> bit_get(15, 0)
    1
    >>> bit_get(15, 4)
    0
    >>> bit_get(0, 4)
    0
    >>> bit_get(-1, 2) is None
    True
    >>> bit_get(0, -1) is None
    True
    """

    return multibit_get(bint, index, 1)


def bit_set(bint: int, index: int, value: int = 1) -> int | None:
    """Set bit at index to value 1 or 0, like set() or unset().

    >>> bit_set(15, 0, 0)
    14
    >>> bit_set(15, 4, 1)
    31
    >>> bit_set(31, 6, 0)
    31
    >>> bit_set(31, 6, 3) is None
    True
    """

    if value not in [0, 1]:
        return None  # error

    return multibit_set(bint, index, 1, value)


def bit_insert(bint: int, index: int, value: int = 1) -> int | None:
    """Insert bit value before index.

    >>> bit_insert(15, 0, 0)
    30
    >>> bit_insert(15, 0, 1)
    31
    >>> bit_insert(15, 4, 1)
    31
    >>> bit_insert(31, 6, 0)
    31
    """

    if value not in [0, 1]:
        return None  # error

    return multibit_insert(bint, index, 1, value)


def bit_remove(bint: int, index: int) -> int | None:
    """Remove the bit at index from bint.

    >>> bit_remove(15, 0)
    7
    >>> bit_remove(15, 1)
    7
    >>> bit_remove(31, 4)
    15
    >>> bit_remove(31, 6)
    31
    """

    return multibit_remove(bint, index, 1)


def multibit_get(bint: int, index: int, bit_len: int) -> int | None:
    """Get bit_len number of bits starting from index.
       819 = 1100110011.

    >>> multibit_get(0, 1, 1)
    0
    >>> multibit_get(15, 0, 3)
    7
    >>> multibit_get(819, 2, 4)
    12
    >>> multibit_get(819, 4, 6)
    51
    """

    if bint < 0 or index < 0 or bit_len < 0:
        return None  # error

    return (bint >> index) & ((1 << bit_len) - 1)


def multibit_set(bint: int, index: int, bit_len: int, value: int) -> int | None:
    """Overlay bint at index with value for bit_len bits.

    >>> multibit_set(0, 1, 1, 0)
    0
    >>> multibit_set(15, 0, 2, 0)
    12
    >>> multibit_set(22, 0, 1, 1)
    23
    >>> multibit_set(22, 2, 1, 0)
    18
    >>> multibit_set(22, 2, 1, 3) is None
    True
    """

    if bint < 0 or index < 0 or bit_len < 0 or value < 0:
        return None  # error
    if bit_length(value) > bit_len:
        return None

    return ((((bint >> (index + bit_len)) << bit_len) | value) << index) | (
        bint & (1 << index) - 1
    )


def multibit_insert(bint: int, index: int, bit_len: int, value: int) -> int | None:
    """Insert before index-th slot

    >>> multibit_insert(0, 1, 1, 1)
    2
    >>> multibit_insert(15, 1, 2, 0)
    57
    >>> multibit_insert(22, 0, 1, 1)
    45
    >>> multibit_insert(22, 2, 1, 0)
    42
    >>> multibit_insert(22, 2, 1, 3) is None
    True
    """

    if bint < 0 or index < 0 or bit_len < 0 or value < 0:
        return None  # error
    if bit_length(value) > bit_len:
        return None

    return ((((bint >> index) << bit_len) | value) << index) | bint & ((1 << index) - 1)


def multibit_remove(bint: int, index: int, bit_len: int) -> int | None:
    """Remove bits in bint from index to index+bit_len.

    >>> multibit_remove(3, 1, 1)
    1
    >>> multibit_remove(15, 1, 2)
    3
    >>> multibit_remove(22, 0, 1)
    11
    >>> multibit_remove(22, 2, 2)
    6
    >>> multibit_remove(22, 2, 6)
    2
    """

    if bint < 0 or index < 0 or bit_len < 0:
        return None  # error

    return ((bint >> index + bit_len) << index) | bint & ((1 << index) - 1)


if __name__ == "__main__":
    import doctest

    doctest.testmod()