Pythonic bit twiddling

[David Bolen]

Jim Richardson <warlock at eskimo.com> writes:

> I have an application that does a calculation on a single byte of data,
> after breaking it into an upper and lower nibble of four bits. How can I
> do this in python? To clarify.

As others have mentioned the actual bit twiddling is fairly straight
forward (| for or, & for and, and so on) and since this is just a byte
you shouldn't run into some of the more subtle issues with 32-bit
unsigned values (since Python integers are 32-bit signed).

But one thing I haven't seen mentioned is that you will probably want
to make use of the ord() and chr() functions to convert between a
single character string and an integer value and vice versa.

That is, assume you have a string buffer that contains bytes you read
from a serial port or something, and you want to flip the two nibbles.
For example:

    >>> value = '\x12\x34\x56\x78'
    >>> print map(hex,map(ord,value))
    ['0x12', '0x34', '0x56', '0x67']
    >>> result = ''
    >>> for char in value:
    ...   byte = ord(char)
    ...   byte = ((byte & 0xF) << 4) | ((byte & 0xF0) >> 4)
    ...   result = result + chr(byte)
    ...
    >>> print map(hex,map(ord,result))
    ['0x21', '0x43', '0x65', '0x76']

Obviously this particular example isn't very efficient in building a
result string, but I went for clarity rather than performance.
Building up a list of converted values and then joining them at the
end is a clear optimization.  For larger buffers, using map(ord,value)
as in the print to first convert to a list of integers, mutate it, and
then map(chr,result) and string.join to put it back into strings would
probably be the most efficient at the expense of some extra memory.

The other suggestion of a translation table also works really well if
the mapping is fixed and amenable to generating such a table up front.

For example, here's a small excerpt from a script I used to process a
file and invert the bits on each "word" in the file (16-bit/2 byte
words by default).  I chose to use a single byte translation table and
just reverse the bytes in each word with reverse(), since that seemed
a reasonable tradeoff in terms of space (e.g., if the word size was
set to 32-bit) and performance.

    # Create a byte translation table for efficiency
    xlate = {}
    for byte in range(256):
        key = byte
        rbyte = 0
        for bit in range(8):
            rbyte = rbyte << 1
            rbyte = rbyte | (byte & 1)
            byte  = byte >> 1
        xlate[key] = rbyte

    while 1:
        buffer = input.read(wordsize)
        if not buffer: break

        bytes = map(ord,buffer)
        bytes.reverse()

        reversed = string.join(map(lambda x,xlate=xlate:chr(xlate[x]),
                                   bytes),'')

        output.write(reversed)

--
-- David
-- 
/-----------------------------------------------------------------------\
 \               David Bolen            \   E-mail: db3l at fitlinxx.com  /
  |             FitLinxx, Inc.            \  Phone: (203) 708-5192    |
 /  860 Canal Street, Stamford, CT  06902   \  Fax: (203) 316-5150     \
\-----------------------------------------------------------------------/