Source code for qubiter.BitVector


[docs]class BitVector: """ This class uses an int called dec_rep as a vector of self.len many bits, where self.len <= self.max_len. The class wraps some common bitwise operations, and some less common ones too (like Gray coding that is needed by Qubiter). In some cases, the bitwise manipulation might be more succinct than the corresponding function in this wrapper, but the wrapper function's name spells out in words what is wanted. Attributes ---------- dec_rep : int decimal representation, the int whose binary representation carries a bit vector of length self.len len : int the length of the bit vector max_len : int maximum self.len allowed """
[docs] def __init__(self, length, dec_rep): """ Constructor Parameters ---------- length : int dec_rep : int Returns ------- """ self.len = length self.dec_rep = dec_rep self.max_len = 16 assert length <= self.max_len, "bit vector is too long" assert length > 0, "bit vector len must be >=1"
[docs] @staticmethod def copy(bvec): """ Copy constructor, returns a new BitVector which is a copy of the BitVector bvec. Parameters ---------- bvec : BitVector Returns ------- BitVector """ return BitVector(bvec.len, bvec.dec_rep)
[docs] def bit_is_T(self, bpos): """ Returns True iff bit at position bpos is 1 (True) Parameters ---------- bpos : int bit position Returns ------- bool """ assert bpos < self.len, "bit position is too large" mask = (1 << bpos) return (self.dec_rep & mask) == mask
[docs] def set_bit_T(self, bpos): """ Sets to 1 (True) the bit of self at position bpos. Parameters ---------- bpos : int bit position Returns ------- None """ assert bpos < self.len, "bit position is too large" self.dec_rep |= (1 << bpos)
[docs] def set_bit_F(self, bpos): """ Sets to 0 (False) the bit of self at position bpos. Parameters ---------- bpos : int bit position Returns ------- None """ assert bpos < self.len, "bit position is too large" self.dec_rep &= ~(1 << bpos)
[docs] def set_all_bits_T(self): """ Sets to 1 (True) the bits of self at position bpos from 0 to len-1 inclusive. Returns ------- None """ # example: len = 3, dec_rep becomes 15 = b0111 self.dec_rep = (1 << self.len + 1) - 1
[docs] def set_all_bits_F(self): """ Sets to 0 (False) the bits of self at positions bpos from 0 to len-1 inclusive. Returns ------- None """ self.dec_rep = 0
[docs] def get_num_T_bits(self): """ Returns the number of 1 (True) bits at positions bpos from 0 to len-1 inclusive. Returns ------- int """ count = 0 for bpos in range(self.len): if self.bit_is_T(bpos): count += 1 return count
[docs] def find_T_bit_to_right_of(self, bpos): """ Returns position of 1 (True) bit immediately to the right of position bpos. Returns -1 if there is no such bit. Parameters ---------- bpos : int bit position Returns ------- int """ if bpos <= 0: return -1 right_T_bit = bpos mask = (1 << right_T_bit) found_it = False while True: right_T_bit -= 1 mask >>= 1 found_it = ((self.dec_rep & mask) == mask) if right_T_bit == 0 or found_it: break if found_it: return right_T_bit else: return -1
[docs] def find_T_bit_to_left_of(self, bpos): """ Returns position of 1 (True) bit immediately to the left of position bpos. Returns -1 if there is no such bit. Parameters ---------- bpos : int bit position Returns ------- int """ if bpos >= self.len-1: return -1 left_T_bit = bpos mask = (1 << left_T_bit) found_it = False while True: left_T_bit += 1 mask <<= 1 found_it = ((self.dec_rep & mask) == mask) if left_T_bit == self.len-1 or found_it: break if found_it: return left_T_bit else: return -1
[docs] def find_leftmost_T_bit(self): """ Out of all 1 (True) bits, returns position of the leftmost one of those to the the left of position bpos. Returns -1 if there is no such bit. Returns ------- int """ if self.bit_is_T(self.len-1): return self.len-1 else: return self.find_T_bit_to_right_of(self.len - 1)
[docs] def find_rightmost_T_bit(self): """ Out of all 1 (True) bits, returns position of the rightmost one of those to the the right of position bpos. Returns -1 if there is no such bit. Returns ------- int """ if self.bit_is_T(0): return 0 else: return self.find_T_bit_to_left_of(0)
[docs] def get_bit_string(self): """ Returns self represented as string of length self.len of ones and zeros. If bit_str is the output, [int(x) for x in bit_str] will turn result to list of ints. Returns ------- str """ bit_str = '' for beta in range(self.len-1, -1, -1): if self.bit_is_T(beta): bit_str += '1' else: bit_str += '0' return bit_str
[docs] def __str__(self): """ Readable representation of self Returns ------- str """ return self.get_bit_string() + '=' + str(self.dec_rep)
[docs] @staticmethod def new_with_T_on_diff(bvec1, bvec2): """ Given two BitVectors bevc1 and bvec2, this return a BitVector which is a bitwise xor (mod 2 sum) of the bits of bvec1 and bvec2. Parameters ---------- bvec1 : BitVector bvec2 : BitVector Returns ------- BitVector """ assert bvec1.len == bvec2.len return BitVector(bvec1.len, bvec1.dec_rep ^ bvec2.dec_rep)
[docs] @staticmethod def get_lazy_from_normal(bit_len, normal): """ Throughout Qubiter, we will often refer to "Gray Code" as "lazy ordering". In lazy ordering with bit_len many bits, one gives a sequence of bit vectors of length bit_len, so that two adjacent items of the sequence differ by just one bit. For example 000=0, 100=4, 110=6, 010=2, 011=3, 111=7, 101=5, 001=1. Each element of this sequence represented as an int will be called lazy, and each int in the sequence 0, 1, 2, 3, 4, 5, 6, 7 will be called normal. Normal ordering is usually called dictionary ordering. Normal and lazy sequences both start at 0. Suppose bit_len = 3. The lazy sequence 000, 100, 110, 010, 011, 111, 101, 001 is easily obtained from the "standard" lazy sequence 000, 001, 011, 010, 110, 111, 101, 100 by "reflecting" each sequence term. We will use the second sequence because it is more common in the literature. References ---------- 1. Martin Gardener, "Knotted DoughNuts and Other Mathematical Entertainments", chapt. 2, "The Binary Gray Code" 2. "Numerical Recipies in C" 3. Many books on Discrete Mathematics for CompSci types 4. On the web, in Eric's Treasure Trove/Math/Gray Codes Parameters ---------- bit_len : int normal : int Function returns the lazy int that corresponds to this normal int. Returns ------- int """ lazy_bvec = BitVector(bit_len, normal) lazy = lazy_bvec.dec_rep if bit_len > 1: for m in range(bit_len-2, -1, -1): # Look at bpos = m+1, if it's ON, then flip bpos=m. # Remember that ^ is same as a mod2 sum. lazy ^= (((normal >> m+1) & 1) << m) return lazy
[docs] @staticmethod def lazy_advance(old_normal, old_lazy): """ This method takes int "old_lazy" (which corresponds to bit vector "old_normal"), and changes it to the next lazy int, "new_lazy" ( which corresponds to "new_normal"). example: lazy sequence: 000, 001, 011, 010, 110, 111, 101, 100 old_lazy = 011 old_normal = 2 = 010 new_normal = 3 = 011 mask = (new_normal & ~old_normal) = 011 & 101 = 001 new_lazy = new_normal ^ mask = 011 ^ 001 = 010 Parameters ---------- old_normal : int old_lazy : int Returns ------- int, int """ new_normal = old_normal + 1 new_lazy = old_lazy ^ (new_normal & ~(new_normal-1)) return new_normal, new_lazy
if __name__ == "__main__": def main(): for length in [3, 4]: print('\nlength=', length) print('normal, lazy, lazy in binary:') max_normal = (1 << length) - 1 normal = 0 lazy = 0 while normal <= max_normal: lazy_bvec = BitVector(length, lazy) print(normal, lazy, BitVector.get_bit_string(lazy_bvec)) normal, lazy = BitVector.lazy_advance(normal, lazy) main()