Python dynamic bit manipulation example

Question

I am currently writing a python program requires bit manipulation.

The input is a sequence of integer array, say

1, 2, 3, 4, 5, 6, 7, 8

The output is to check if each of the integer equal or greater than 3. If yes, then 1, else, then 0. The output is an binary integer:

00111111

How can I do this?

If a new number came in, say 9. I need to remove the first number in the sequence, say 1 in the sequence. So my new sequence will be:

2,3,4,5,6,7,8,9

Then the result should be 01111111. But I want to use left shift operation to this from my old integer 00111111. How Can I do this? Thank you!

Answer 1

You could use a function like the following:

# Assumes msb first, lsb last, bits is iterable of integers in [0,1]
def bits2int(bits):
    v = 0
    for b in bits:
        v <<= 1
        v += b
    return v

Then, given your input array arr, call it with:

arr = [1, 2, 3, 4, 5, 6, 7, 8]
val = bits2int([i >= 3 for i in arr])

print(val)                   # 63
print("{:08b}".format(val))  # 00111111

Same thing for your other input array, you could call it with:

arr = [2,3,4,5,6,7,8,9]
val = bits2int([i >= 3 for i in arr])

print(val)                  # 127
print("{:08b}".format(val)  # 01111111

Edit: From the last part of your question, it looks like you want to "update" val given some new integer.

This can be done using the above approach (update arr, call bits2int again on the updated arr), or "manually", with:

arr = [1, 2, 3, 4, 5, 6, 7, 8]
val = bits2int([i >= 3 for i in arr])
# Now, val = 63 = 0b00111111

# Handle additional integer
new_int = 9             # Give the additional integer a name, to make it clear
val <<= 1               # Shift up all bits
val |= (new_int >= 3)   # Set lowest bit according to some logic
                        #   (here, if new_int >= 3)
print(val)
print("{:08b}".format(val))

At the end, val is the same as the output from the second bits2int call above:

127
01111111

Note that the <<= operator is in-place/augmented left-shift operator and the |= operator is the in-place/augmented bitwise-or operator.

---

Update

Per the discussion in comments, you not only want to keep track of the value, but also the number of bits. This is more complicated than the simple function above. Here's a basic class you could use:

class BitArray(object):
    @classmethod
    def from_array(cls, bits=None):
        self = cls()
        if bits is None: bits = []
        self.val = 0
        for b in bits:
            self.val <<= 1
            self.val += b
        self.nbits = len(bits)
        return self

    @classmethod
    def from_int(cls, val, nbits=None):
        self = cls()
        if nbits is None: nbits = val.bit_length()
        self.val = val
        self.nbits = nbits
        return self

    # Define equality
    def __eq__(self,  other):
        if self.val   != other.val:   return False
        if self.nbits != other.nbits: return False
        return True

    # Better representation of BitArray object
    def __repr__(self):
        return "BitArray(nbits=%d, val=%d)" % (self.nbits, self.val)

    # Output a binary string of nbits width, or width if specified (width must be >= nbits)
    def binstr(self, width=None):
        if width is None: width = self.nbits
        assert width >= self.nbits
        return "{:b}".format(self.val).zfill(width)

    # Conversion to int e.g. int(BitArrayInstance)
    def __int__(self):
        return self.val

    # "in-line" left shift
    def __ilshift__(self, n):
        self.val <<= n
        self.nbits += 1
        return self

    # "in-line" bitwise or
    def __ior__(self, v):
        self.val |= v
        return self

    # Helper function to generate a bit mask
    def _mask(self):
        return (1 << self.nbits) - 1

    # Trim n bits off the left side (truncate n most significant bits)
    def ltrim(self, n):
        self.nbits = max(0, (self.nbits - n))
        self.val &= self._mask()

    # "Pops" off msb, shifts all bits up 1, sets lsb to v
    def rotate_in(self, v):
        v = int(v)
        assert v in [0,1]
        self.ltrim(1)
        self.__ilshift__(1)
        self.__ior__(v)
        return self

Now, after you perform the same <<= and |= operations, you can remove the left-most bit / msb with the ltrim method:

arr = [1, 2, 3, 4, 5, 6, 7, 8]
b1 = BitArray.from_array([i >= 3 for i in arr])
print(b1)
new_int = 9
b1 <<= 1
b1 |= (new_int >= 3)
b1.ltrim(1)
print(b1)

This outputs:

BitArray(nbits=8, val=63)
BitArray(nbits=8, val=127)

Note that the nbits values are the same in the two print functions. <<= 1 will increase nbits by 1, then ltrim(1) will decrease it by 1, back to 8. It does by "throwing out" the left-most bit like you asked.

I also threw in a convenience function for these 3 operations, rotate_in(bit_val). You could use this by:

arr = [1, 2, 3, 4, 5, 6, 7, 8]
b2 = BitArray.from_array([i >= 3 for i in arr])
print(b2)
new_int = 9
b2.rotate_in(new_int >= 3)
print(b2)

This outputs (same as above):

BitArray(nbits=8, val=63)
BitArray(nbits=8, val=127)

We can verify these two BitArrays are equivalent with

# Ensure b1 equals b2
print(b1 == b2)  # True

Lastly, just to verify this will work just as well for input arrays of length 600, we create a 600-element list of 1s, turn it into a BitArray, then compare the resulting value (with int(BitArrayInstance)) to what we expect it to be:

# Test 600 element array :)
arr = [1] * 600
b3 = BitArray.from_array(arr)
print(int(b3) == ((2**600) - 1))  # True