[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