[Tutor] Shifting arrays as though they are a 'word'

[Alan Gauld]

On 05/10/18 21:17, Chip Wachob wrote:
>
> I have an array of bytes.  Up to 64, which makes for 512 bits.
> 
> I am reading these bytes in serially, and once I have a collection of
> them, I want to shift them by 'n' bits.  The size of the array and the
> number of bits are both variable up to the limit of 64/512.

bit trwiddling like this is always way more difficult than it sounds.
You need to define very specifically how each operation will work,
especially if you are shifting bytes in the middle of a larger
sequence. For example, what happens to the bits that "fall off
the end" - do they push the other surrounding bits up/down?
Or do they get lost? Or are they combined in some way?

Writing down the detailed specification for each operation
usually takers longer than writing the code.

In Python things are made more complex by the fact that
most data containers are bigger than a byte and often have
a lot of extra cruft attached. This makes it harder to know
exactly what you are looking at. Often the best option is
to use bit-masks to pull out exactly the bits you are
interested in, otherwise carry bits and complement bits
can confuse things.

> Now, I've played around with looping through the bytes and taking the
> LSByte and shifting it by 'n' bits using >> or << and that works for
> the first byte.  But then I need to take the next byte in the sequence
> and shift it in the opposite direction by 8-n bits using << or >>
> (opposite the LSByte direction), respectively.  Then I OR the two
> bytes and save them into the location of the LSByte 

I'd try to avoid that approach. Save the results into
a new byte array if at all possible. Otherwise it becomes
impossible to debug really quickly.

> the next byte in the sequence and so on.  While this works most of the
> time, I sometimes get strange behavior at the 'fringes' of the bytes.

Dfine "strange behaviour" - give a concrete example.

> Sometimes I end up with zero, or the shift seems to 'roll over'.

Define "roll over" - show us an example

> I'm thinking that maybe there's a way to treat the array / list and
> shift allowing the bits to transfer from byte to byte as needed.

Can you show us what you want.

For example here are three bytes:

0000000001111111100000000

Now, if you shift the middle byte to the left by 3 bits
what should the end result be?

a) 000001111111100000000000
Shift left, overwrite previous data, fill with zeros

b) 000000001111100000000000
Shift left, preserve previous data, fill with zeros
(and is that fill coming by dragging the right hand byte
left and filling *it* with zeros or by preserving the
right hand byte and filling the centre with zeros?)

c) 000001111111111100000000
Shift left, overwrite previous data, fill with ones


It's complicated and there are several other
permutations beyond the 3 shown. You need to decide,
there is no "correct" answer..

> Maybe by concatenating the bytes into one huge word and then breaking
> it apart again?

Maybe, but it all depends what you are trying to do.

> I'm thinking that you folks out there know of a built-in function, or,
> an easier and more predictable way to accomplish the same.

Without a more detailed spec, no.
Python is not really best suited to bitwise operations
so it only has the most basic features: bitwise operators,
multi base output/conversion and slicing.


-- 
Alan G
Author of the Learn to Program web site
http://www.alan-g.me.uk/
http://www.amazon.com/author/alan_gauld
Follow my photo-blog on Flickr at:
http://www.flickr.com/photos/alangauldphotos