BitAlign
Given two strings of bits, find how to best align them so that they have the most bits in common.
Installation: pip install bitalign
Examples
The following snippets show a conceptual string of 16 bits A = "0001001011111111"
needs to shifted to the right by 5 in order to best line up with
the string of 16 bits B = "1111100010010111", at
which point they have 11 bits in common:
A = 0001001011111111
B = 1111100010010111
The only differences are how we decide to encode the bits into a list of integer.
>>> from bitalign import *
>>> # We can can treat bytes objects like b'\x12\xff' as bit arrays
>>> A = bytes([0b0001_0010, 0b1111_1111])
>>> B = bytes([0b1111_1000, 0b1001_0111])
>>> bitalign_8_msb(A, B)
(5, 11)
>>> # Reversing the bits in each byte --> use "lsb" method instead
>>> A = bytes([0b0100_1000, 0b1111_1111])
>>> B = bytes([0b0001_1111, 0b1110_1001])
>>> bitalign_8_lsb(A, B)
(5, 11)
>>> # numpy arrays also work, just make sure they have an appropriate dtype.
>>> import numpy as np
>>> A = np.array([0b0001001011111111], dtype=np.uint16)
>>> B = np.array([0b1111100010010111], dtype=np.uint16)
>>> bitalign_16_msb(A, B)
(5, 11)
>>> # Reverse bits in each uint64 --> use "lsb" method instead
>>> A = np.array([0b1111111101001000], dtype=np.uint16)
>>> B = np.array([0b1110100100011111], dtype=np.uint16)
>>> bitalign_16_lsb(A, B)
(5, 11)
>>> # Works on general pairs of c-contiguous buffer objects
>>> # numpy.array, array.array, bytes, bytearray, memoryview, etc.
>>> import array
>>> A = array.array('H', [0b0001001011111111])
>>> B = array.array('H', [0b1111100010010111])
>>> bitalign_16_msb(A, B)
(5, 11)API
This bitalign package exposes 8 methods:
from bitalign import (
bitalign_8_lsb,
bitalign_16_lsb,
bitalign_32_lsb,
bitalign_64_lsb,
bitalign_8_msb,
bitalign_16_msb,
bitalign_32_msb,
bitalign_64_msb,
) bitalign_#_?sb(arr1, arr2) --> (shift_by, num_common_bits);
Return a tuple (x, y) such that when arr1 is shifted by x bits,
the number of bits in common between arr1 and arr2 is y.
Positive shifts indicate that arr1 needs to be shifted toward the back:
arr1 = --> 0001001011111111 -->
arr2 = 1111100010010111
gives (shift_by=5, num_common_bits=11)
Negative shifts indicate that arr1 needs to be shifted toward the front:
arr1 = <-- 1111100010010111 <--
arr2 = 0001001011111111
gives (shift_by=-5, num_common_bits=11)
The number (8, 16, 32, or 64) in the function name the number of bits
that must be in each array entry. 'lsb'/'msb' indicates whether the
0th bit of each logical bit-array is to be stored in the least or most
significant bit of arr[0].
If more than one shift is optimal, the negative-most shift is used.
If there are no bits in common (i.e., all zeros with all ones),
then (-num_bits, 0) is returned.
