Boolean Math and Boolean Algebra Refresher

Boolean Math & Boolean Algebra Refresher:

You're counting in binary - you only have 2 digits - 0 [zero] and 1 [one]. Each binary digit is referred to as a "bit", with "bit" being an improper contraction of "binary digit". Everytime a digit position fills up, you have to roll over to a new digit column, thus adding a bit to the left hand side of the binary number. Zeros to the left of the most significant digit are not themselves significant, unless they serve as a placeholder reminding you of the maximum # of bits of storage that are available to contain the number. On most computers, you're dealing with 32 bits of storage for an integer value unless you specifically code to use a different storage size.

Each binary digit has a value equal to 2 raised to the Nth power, where N is the bit's positional value starting from 0 on the right and working upwards as you go to the left.

Here's a bit of the decimal/binary conversion table:

decimal = binary

0 = 0
1 = 1
2 = 10
3 = 11
4 = 100
5 = 101
6 = 110
7 = 111
8 = 1000
9 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111
16 = 10000

So, to convert 1010 [binary] into 10 [decimal], we have to take the values of the bits with 1's in them and add those values together. The lefthand bit has a positional value of 3 which becomes the exponent, thus the bit has a value of 2^3 = 8. The other bit that's on is in position 1, having a value of 2^1 = 2. Adding, we get 8 + 2 = 10.

Now, in Boolean Algebra, an OR operation is an additive type of operation, meaning you'll never get a result with less bits than you started with, but it's not pure addition, either.

Given 2 binary numbers, say, 0010 [2] and 1000 [8], we can OR them together, which simply means we combine their bit values as if overlaying them on each other, with a 1 always replacing a zero and two 1's always resulting in a 1.

0 OR 0 = 0 0 OR 1 = 1 1 OR 0 = 1 1 OR 1 = 1

So, 1000 OR 0010 = 1010, and for another example, 1010 OR 0010 = 1010.

An AND operation works differently, requiring both bits to have value of 1 before the result will be 1, as is shown in the following table:

0 AND 0 = 0 0 AND 1 = 0 1 AND 0 = 0 1 AND 1 = 1

Thus, 1111 OR 0001 = 0001, 1111 AND 1010 = 1010, and 1010 AND 0101 = 0000.

There's also the NOT operator, which inverts the value.

NOT 0 = 1 NOT 1 = 0

One application of the NOT operator is to invert a binary number's digits, and it's especially useful in the application of bit masks. For example, let's apply the NOT operator to a binary number and not just a single bit.

NOT 1010 = 0101 NOT 0000 = 1111 NOT 1111 = 0000 NOT 0101 = 1010

So, given, say, a desire to test if a particular bit is enabled in a number, you simply use the AND operation with an appropriate mask value and then test if the result is non-zero.

We have the # 1101, and we want to know if bit #1 [the zero valued bit] is on or off, we have to AND the # with 10 [or zero fill to 0010] and see if the result is zero or one.

1101 AND 0010 = 0000

In this case, the result is zero so we know the bit wasn't on.

If we're interested in testing for multiple bits, then the mask has to have 1's for each bit being tested. If we wanted to test for bit #'s 1 and 2, the mask would be 110 [or 0110 if zero filled].

1101 AND 0110 = 0100

In thise case, the result is non-zero, so we know that at least one of the bits in the mask was on.

We might also want to use a mask to turn a particular bit on or off. Turning bits on involves using OR, while turning bits off involves a combination of using NOT and AND.

Given the # 1101, and wanting to turn on bit #1, we use the following:

1101 OR 0010 = 1111

Given the # 1111, and wanting to turn off bit #1, we use the following:

1111 AND (NOT 0010) = 1111 AND 1101 = 1101

Now, when you combine this with decimal #'s, it gets more arcane looking because you have to do the underlying conversions in your head or just have them memorized. It also gets confusing when you're dealing with 32 bits and each bit has a value that combines to make some rather large decimal #'s that don't immediately get interpreted in your mind as being a combination of bits.

The last example above is realy 15 AND (NOT 2), which is 15 AND 13, with a result of 13. The result may not seem intuitively obvious when you see the expression in decimal, but in binary or even hexadecimal it's easy to see how and why the result is obtained.

There's lots of other stuff in Boolean Algebra that's not being discussed here, such as negated OR and negated AND operations known as NOR and NAND, nor is there a proper discussion of 1's complements, 2's complements when performing bitwise inversion with NOT. However, this ought to be enough to get a novice heading in the right direction for a basic understanding of binary operations.

Article ID:   W16782

File Created: 2015:08:03:08:50:04

Last Updated: 2015:08:03:08:50:04

Database Search

TechHome

Boolean Math and Boolean Algebra Refresher