Inserting a '0' bit into the middle of a bitsequence in python

May 2, 2022

This should be fairly simple, but I’ve yet to see a viable solution.

If I have a bit sequence (represented as an integer), how would I insert a 0 at index n?

For example:

insert(0b100101010101,4) -> 0b1001001010101

insert(0b101,3) -> 0b1010

insert(0b10001,2) -> 0b100001

EDIT: To clarify, I would like to do this without using vectors or strings (only bitwise operators)

>Solution :

You would need to isolate the bits to the left and to the right of the insertion point, then shift the left part one position, and combine both parts again:

def insert(n, bit):
    length = n.bit_length()
    if bit > length:
        raise ValueError("argument out of range")
    right = n & ((1 << length - bit) - 1)
    return ((n - right) << 1) + right