System-Level Programming and Base 2

Date: 05/03/2001 at 17:47:57
From: Eric Brasher
Subject: Working with exponents with base of 2

I am starting to learn computer programming and have run into a 
problem. 

I have a result that contains serveral values. But the values are 
always a power of 2 (2^2, 2^3, 2^4).

Say my value is 2^3, 2^4, 2^6   "304"

How can I tell if 2^3 exists in "304" ?
Remember that the value is always sums of the power of 2. There can 
be any number of sums calculated, but usually only 3 to 7.

This is dealing with the status of logon accounts to a server.
   if the account is disabled then the value = 2^1
   if the account is locked out then the value = 2^3
   if the account can not change its password then value = 2^5
   if the account is normal then value = 2^7

So if I query the value and the account is disabled, normal, and 
locked, then the value is 530. I only want to know if the account is 
locked (value = 16), so how do I run a formula to find if 2^3 is one 
of the values in 528?

Date: 05/04/2001 at 14:08:43
From: Doctor TWE
Subject: Re: working with exponents with base of 2

Hi Eric - thanks for writing to Dr. Math.

I'm not sure how you're getting the values 304, 530 or 528.

      2^3 + 2^4 + 2^6 = 8 + 16 + 64 =  88
      2^1 + 2^7 + 2^3 = 2 + 128 + 8 = 138
     (dis) (nrm) (lck)

Powers of 2 are simply the "place values" (or weights) in the binary 
number system. Are you familiar with binary? You really should be if 
you want to do this type of "system level" programming. If you're not 
familiar with binary, you can start by checking out our Number Bases 
FAQ at:

   http://mathforum.org/dr.math/faq/faq.bases.html   

For the following explanation, you should also be familiar with the 
AND logic operation. If you're not familiar with it, see:

   Truth Tables of Boolean Variables
   http://mathforum.org/dr.math/problems/green.03.09.01.html   

   Truth Tables and Computer Circuits
   http://mathforum.org/dr.math/problems/vanetten.1.17.00.html   

The following archive entry explains the "bitwise" operation. Although 
it uses the XOR operation instead of the AND operation, the concept 
applies to the AND operation as well:

   . XOR Operation
   http://mathforum.org/dr.math/problems/james.01.23.01.html   )


What you need is a "masking function" that isolates one bit in the 
account status byte. The account status byte as you describe it looks 
like this:

   2^7  2^6  2^5  2^4  2^3  2^2  2^1  2^0
   128   64   32   16   8    4    2    1
   ---  ---  ---  ---  ---  ---  ---  ---
    X    X    X    X    X    X    X    X   (base 2)
    ^         ^         ^         ^
     \         \         \         \______ Account disabled
      \         \         \_______________ Account locked out
       \         \________________________ Acct can't change password
        \_________________________________ Account is normal

Masking functions are more easily done using logic operations than by 
arithmetic operations. To check whether a particular bit is set ("on") 
or cleared ("off"), AND the byte with a mask byte created as follows: 
place a 1 in the bit position to be tested, and place 0's in all other 
bit positions.

For example, suppose I want to see whether an account is locked out. I 
construct my mask byte by placing a 1 in the 2^3 = 8 bit position and 
0's in the rest of the bits. So my mask byte is:

     2^7  2^6  2^5  2^4  2^3  2^2  2^1  2^0
     128   64   32   16   8    4    2    1
     ---  ---  ---  ---  ---  ---  ---  ---
      0    0    0    0    1    0    0    0   (base 2) = 8 (base 10)

Now I AND this value with the account status byte. Suppose the account 
status byte is 00101011 (base 2) = 43 (base 10). The AND masking 
operation would do:

        Binary     Dec
       00101011  =  43   (Account status byte)
     ^ 00001000  =   8   (Mask byte)
       --------    ---
       00001000      8   (Result)

If the result is 0, the bit under test is cleared (0), but if the 
result is not equal to 0, the bit under test is set (1). In our 
example, the result of 8 is not equal to 0, so the "locked out" bit is 
set in the account status byte.

Suppose, on the other hand, that the account status byte is 11100010 
(base 2) = 226 (base 10). The AND masking operation would do:

        Binary     Dec
       11100010  = 226   (Account status byte)
     ^ 00001000  =   8   (Mask byte)
       --------    ---
       00000000      0   (Result)

Since the result is 0, the "locked out" bit is set in the account 
status byte is cleared.

Most programming languages allow you to use logic operations like the 
AND operation, and some even allow you to specify your mask byte in 
binary (or hexadecimal) instead of having to convert it to decimal. 
Attempting to do this using arithmetic operations requires several 
steps that "strip off" the higher order bits, then check to see if the 
result of dividing the remaining value by 2^n is greater than or equal 
to 1, which is much messier.

I hope this helps. If you have any more questions, write back.

- Doctor TWE, The Math Forum
  http://mathforum.org/dr.math/