My Notes on Bit Manipulation…

June 16, 2010 at 12:03 pm (Bit Manipulation, Programming)

Hey,

Recently I have been doing some research into Bit Manipulation, mainly because I don’t really understand it! I wanted to fix this, so the research began… 🙂 What is a “bit”? Well a bit is what a byte is made up of, to be exact 8 bits make a byte. A bit is the most basic unit of computer memory we can deal with, it has two states, “on” or “off”, or “true” or “false” and probably many more but these are the ones I will stick to using. A byte can hold any number from 0 to 255. How can this be possible when 1 byte is made up of 8 bits you ask? Well, there needs to be order in the bits 🙂 It works from left to right like so:

7 6 5 4 3 2 1 0

Which equates to: bit 7, bit 6, bit 5, bit 4 … bit 0. A byte with the value of 0 would look like this:

00000000

And a byte with the value of 255 would look like this:

11111111.

OK, so how do we work out the numbers in between these two points (0 and 255). Well there is a simple formula we can use:

    bit 0 = 20 = 1 
bit 1 = 21 = 2
bit 2 = 22 = 4
bit 3 = 23 = 8
bit 4 = 24 = 16
bit 5 = 25 = 32
bit 6 = 26 = 64
bit 7 = 27 = 128

So looking at the above table, say we have the binary number: 00000010, lets put it into the table and figure out what number this represents in decimal:

    bit 0 = OFF: 0 = 1
bit 1 = ON: 1 = 2
bit 2 = OFF: 0 = 4
bit 3 = OFF: 0 = 8
bit 4 = OFF: 0 = 16
bit 5 = OFF: 0 = 32
bit 6 = OFF: 0 = 64
bit 7 = OFF: 0 = 128

As you can clearly see the value is represented as 2 in decimal. What about a more complicated binary number, such as:

10101010

So let’s place this in the table and figure it out:

    bit 0 = OFF: 0 = 1
bit 1 = ON: 1 = 2
bit 2 = OFF: 0 = 4
bit 3 = ON: 1 = 8
bit 4 = OFF: 0 = 16
bit 5 = ON: 1 = 32
bit 6 = OFF: 0 = 64
bit 7 = ON: 1 = 128
---------------------------------- Total: 170

As you can see, you put the number in the table, and add up all the “ON” bits… it’s as simple as that 🙂 Something to remember here is, I draw the tables starting at bit 1, remember the decimal numbers if you read them left to right start off at bit 7 and go down to bit 0. Since each bit has a unique value (128, 64, 32, 16, 8, 4, 2, 1) we are able to figure out the states of each of the bits, whether they are on or off. Rather than doing this the hard way there is a simple method called, boolean logic. There are a handful of boolean logic operators, such as:

OR (inclusive or), XOR (exclusive or), NOT, AND.

Using the above functions we are able to clear, set and test each of the bits that make up any byte. For instance the NOT function is an operation that performs logical negation which means that it switches the bits, for example:

NOT 0110 (decimal: 6)
=   1001 (decimal: 9)

A bitwise OR takes two bit patterns of equal length and produces another one of the same length by matching up the corresponding bits. It will then perform a logical inclusive OR operation on each pairing of bits. For example:

OR 1010 (decimal: 10)
    0110 (decimal: 6)
----------
=   1110 (decimal: 14)

A bitwise exclusive OR (XOR) also takes two patterns of equal length and performs a logical XOR operation on each pairing of bits. If the two bits are different you will get a 1, if they are the same you will get a 0, like so:

XOR 1101 (decimal: 13)
    0011 (decimal: 3)
-----------
=   1110 (decimal: 14)

The bitwise AND operator takes two binary representations of equal length and performs the bitwise AND operation. If the two bits are the same, e.g. 1 and 1 you get 1 otherwise 0 is the outcome. For example:

AND 1100 (decimal: 12)
    0101 (decimal: 5)
------------
=   0110 (decimal: 6)

That’s is it for me on bit manipulation for now. I will continue posting about the topic as there is plenty more to talk about, so until the next time…

Permalink Leave a Comment