[Tutor] << operator ? [left bitwise shifting]

alan.gauld@bt.com alan.gauld@bt.com
Fri, 12 Apr 2002 11:32:17 +0100


> > And it turns out that when we left shift a number, it effectively
> > "doubles".
> Having seen the bitwise shift operator but having no idea 
> what it was for, I appreciate this ...
> But now I'm just curious what it's for...
> double numbers?  And if that's the case, then what's the 
> right bitwise shift operator for?

To half numbers!

Seriously bit shifting is often used as a more efficient way 
of dividing or multiplying by powers of two. But it really 
shouldn't be unless you have to for performance reasons, 
and in Python that should mean never since if performanmce 
is that desparate rewrite in C!

Bit shifting is primarily for manipularting bit patterns.
This ois often important when dealing with low level network 
protocols where specific bits of information are contained 
within a few bits within abn octet.

Thus is some fictitious protocol:

Bit 0 - Data(1) or signalling(0)
Bit 1 - data 1/msg ID #1 
Bit 2 - data 2/msg ID #2 
Bit 3 - data 3/msg ID #3 - 3 msg bits allows 8 messages 
Bit 3 - data 4/msg data 1
Bit 5 - data 5/msg data 2
Bit 6 - data 6/msg data 3
Bit 7 - parity bit/ status indicator

Here the first bit tells the receiver that the octet 
is either a data octet or a signalling octet.
The subsequent bits depend on the first to indicate 
their meaning, if data then we have 6 data contrent 
bits plus a parity bit

If its a signalling octet then the second 3 bits 
contain the message ID and the next 3 bits again 
the message data(which could be a length to say 
that say the next 4 octets contain the real 
message data etc...

Now the receiver checks the valkue of the first 
bit by doing a bitwise AND with a bitmask or 00000001
to determine which kind of octet is being received.

if octet & 0x01: # its data
else: # its a signal

He can now extract the data bits if itsa a data octent 
using another bitmask:

data = octet & 0x7E  # 01111110

But to use them needs to shift the bits one place right:

data = data >> 1

now data contains the 6 data bits in the lowest bit 
positions of the data variable as you would expect 
in a normal variable value.

If OTOH its a signalling octet we must extract both 
the message ID and messaage data.

We could use two masks(and personally I would!) but 
another technique is to use a single mask and multiple 
shifts:

msgmask = 0x07   # 00000111

octet = octet >> 1   # lose the type bit
msg = octet & msgmask  # extract the bottom 3 bits

octet = octet >> 3   # lose ID and put data in the bottom bits
msgdata = octet & msgmask

So now we can pass the info onto our message 
handling routines:

handleMessage(msg, msgdata)

Of course we still have to extract and check our parity 
bit in the case of pure data but I leave that as an 
excercise for the reader!

At the sender we use similar techniques but left shifting 
to put the data into the octet for transmission.

octet = 0  # initialise empty octet
msgID = 5 << 1  # put ID in right place
msg data = 3 << 4 # put data in right place

# now bitwise all those together to get the octet ready to send
octet = octet & msgID & msgdata & getParity(msgdata)

Note I assume a parity checking function to produce 
the right parity bit value...

Hopefully that serves as an example of how bitmasks can 
be used outside of binary arithmetic. In fact its how 
I use them almost exclusively, if I'm doing arithmetic 
I like to make that obvious and use arithmetic operators!
If I'm doing bit twiddling I use bit twiddling operators.

Alan g.
Author of the 'Learning to Program' web site
http://www.freenetpages.co.uk/hp/alan.gauld