[Tutor] bitwise operations

[Blake Winton (Screaming)]

> > Could anyone tell me all there is to know about bit 
> > manipulation; 
> No, I doubt it. I don'ty think anyone has figured 
> that out yet... Some things you might like to do 
> a search on the net for are 'Boolean Algenra' 
> and 'Bitmasks'

Okay, but surely we could give Craig a short overview...
(See the bottom of the message for descriptions of
 setting bits, clearing bits, and checking if bits are
 set.)

> > why a person would want to be fiddling with bits. 
> Bits are a compact way of storing a lot of data which 
> is boolean by nature.

[ some good examples snipped... ]

> But there are myriad other uses for these, 
> usually in a low level systems context and 
> often in situations where storage space is 
> expensive - like networking protocols etc.

I also saw a neat application of them in a financial
application I'm looking at.  Basically, you can set
up Pre-Authorized Cash Transfers to happen once or
twice a month, on any days you choose.  As a compact
(and easy?) way of representing those pieces of
information, the coders chose to use an integer, as
a bit mask.  So, if we look at some examples of the
individual bits, we can see what's going on.

If you wanted the transfers to occur on the 3rd and
the 7th, you would set those bits to one, and leave
the rest as 0, to get:
   01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 ...
    0  0  1  0  0  0  1  0  0  0  0  0  0  0  0 ...
(which I've wrote backwards, so we'll flip it to
 be 1000100 (base 2) which equals 68 (base 10).)

Or, if you only wanted stuff transfered on the 5th
of each month, you you set the 5th bit to one, and
the rest to 0, to get:
   01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 ...
    0  0  0  0  1  0  0  0  0  0  0  0  0  0  0 ...
(which I've wrote backwards, so we'll flip it to
 be 10000 (base 2) which equals 16 (base 10).)

Then, to see if a current day has any scheduled
transfers, all the calling program has to do is
take that day number, and check if the bit is set.

> I'll leave explaining how to use "bit masks"
> to read/write individual bits within a block 
> of storage to someone else... :-)

I'll try it...

First, we'll need a short course in hexadecimal numbers,
because they're easier to print out.

If you take a binary number, like 100100 (which equals
36), we can break the digits of it up into groups of 4,
to get 10 0100, and add a couple of 0s at the front to
make 4 digits, and we get 0010 0100.  Now, each of these
groups can be turned into a number with the following
chart:
0000 = 0       1000 = 8
0001 = 1       1001 = 9
0010 = 2       1010 = A (10)
0011 = 3       1011 = B (11)
0100 = 4       1100 = C (12)
0101 = 5       1101 = D (13)
0110 = 6       1110 = E (14)
0111 = 7       1111 = F (15)

These are the hexadecimal numbers.  And if we look them
up, we find that our number 0010 0100 turns into 24 (hex).
To make it easy for us to tell the difference between 24
(decimal) and 24 (hex), we stick a "0x" onto the front of
the hex number, to get "0x24".  And if we start python,
we can see that it works.
>>> print hex(36)
0x24

So, from here on in, I'm just going to print out the hex
numbers.  If you want to know the binary, you can look it
up...

I should probably also tell you about the << operator.
It takes a number, and shifts it left by another number.
So, if we have 1 << 4, in binary, it makes 1 turn into
10000 (think of adding 4 0s onto the end of the number
in binary).  This gives us an easy way of selecting the
4th bit, just use 1<<3.  (Because 1<<0 is the first bit.)
Now, on to the actual stuff...

To set a bit in a bit mask, you use the "or" operator,
(written "|").  But then we need to assign it back to
the variable we're testing.  So, lets start with an x 
of 0, and set some bits in it.

Jython 2.0 on java1.2.2 (JIT: symcjit)
Type "copyright", "credits" or "license" for more information.
>>> x = 0
>>> print hex(x)
0x0
>>> x = x | 1 << 4
>>> print hex(x)
0x10
>>> # in binary 0001 0000, so the 5th bit is set.
>>> x = x | 1 << 2
>>> print hex(x)
0x14
>>> # in binary 0001 0100, so the 5th and 3rd bits are set.

It sort of looks like we're just adding here, but if
we try to set the second bit again, we get:
>>> x = x | 1 << 2
>>> print hex(x)
0x14

If we want to clear a bit, it's a little more complicated.
We want to use the "and" operator, written "&", but with
all the bits set except for the one we want.  To get that,
we need the "not" operator, written "~".  So, to clear the
3rd bit, we use x = x & ~(1 << 2)
>>> x = x & ~(1 << 2)
>>> print hex(x)
0x10
>>> # And we're back to 0001 0000, so the 5th bit is set.

Finally, to test if the 5th bit is set, we again use the
"and" operator ("&"), but this time, we check that the
result is not equal to 0.
>>> print (x & (1<<4)) != 0
1

It's probably useful to you to make three functions.
def setBit( x, bitNum ):
  return x | 1 << bitNum
def clearBit( x, bitNum ):
  return x & ~( 1 << bitNum )
def checkBit( x, bitNum ):
  return (x & (1<<bitNum)) != 0

Then, as long as you remember to start your bitNums 
from 0, you can just use the three functions, and
everyone will know what you are doing.

So, clear as mud?  ;)

Seriously, if you have any questions, just ask, and I'll
see what I can do.  I would like to explain more in this
email, but I've got a deadline coming up, and I've
probably spent too much time on this email as it is.
I can answer more specific questions, if you have them,
but I've really got to cut this particular explanation
off here.

Later,
Blake.