Template:Noble Boolean functions/Python half rows

half rows

There are two ways to derive one half from the other.

Let $L$ be the left (evil) and $R$ be the right (odious) half.
Let $p=2^{(2^{n}-1)}$ be the unique power of two, and $q=2^{2^{n}}-2$ be the highest entry. (They are the first and last entries of $R$ .)
Let $j$ be the mirrored index of $i$ . ( $j$ is as far from the right as $i$ is from the left.)

Then $R_{i}~=~L_{i}+p~=~q-L_{j}$ . (Bitwise XOR can be used instead of plus and minus.)

The following Python code illustrates this for rows 1 to 3:

left_and_right_half = {
    1: [
        [0], 
        [2]
    ],
    2: [
        [0,  6], 
        [8, 14]
    ],
    3: [
        [  0,  30,  40,  54,  72,  86,  96, 126], 
        [128, 158, 168, 182, 200, 214, 224, 254]
    ]
}

for n, (left, right) in left_and_right_half.items():
    length = 2 ** (2 ** (n - 1) - 1)
    p = 2 ** (2 ** n - 1)
    q = 2 ** (2 ** n) - 2
    for i in range(length):
        j = length - i - 1
        assert right[i] == left[i] + p == q - left[j]
        assert right[i] == left[i] ^ p == q ^ left[j]

Template:Noble Boolean functions/Python half rows

Navigation menu

Search