Bit manipulation

In other languages: English | Afrikaans | Albanian | Arabic | Brazilian | Bulgarian | Catalan | Chinese | Croatian | Czech | Danish | Dutch | Esperanto | Estonian | Filipino | Finnish | Flemish | French | German | Greek | Hebrew | Hindi | Hungarian | Indonesian | Italian | Japanese | Latvian | Lithuanian | Macedonian | Malay | Malayalam | Norwegian (Bokmål) | Norwegian (Nynorsk) | Persian | Polish | Portuguese | Romanian | Russian | Serbian | Slovak | Slovenian | Spanish | Swedish | Turkish | Ukrainian | Urdu

Using bitwise operators

This article is about the manipulation of individual bits in a datatype through bit manipulation algorithms. NOTE: Not as complex as I make it out to be.

The Almighty Bit and Byte

A bit is represented by a 0 or 1. As you may know, this is extremely relative to the binary (base 2) numerical system being as each number can only contain two values, 0 or 1. Though binary may scare you and sound complex, it's actually a relatively easy concept and even fun. For instance, you can count up to 31 on one hand.

A byte is a series of bits, normally contain around 8 bits. This isn't always the case but in modern day and common processor architectures, you will almost always find that a byte is 8 bits and is safe to assume that when someone talks about a byte, it consists of 8 bits. A byte can physically look like 0000 0000. The reason for the space in between the byte is because you can picture a byte as a two sets of four bits called nibbles. If you don't like the idea of this, it is also okay to think of it as just 8 bits and be on your way. A cool fact is that the byte is named after bite. It represented how much data the earlier computers could bite (transfer) at once.

Purpose of Bitwise Operations

The purpose of explaining this is to help you visualize the use of the byte and bit. A bit can often be used as a boolean, 0 being false, and 1 being true. Since current modern day boolean types take up much more memory than this and can be messy, developers came up with something called flags which is basically a series of bits that are then interpreted to give a certain reaction.

For instance, say we have a byte, 0000 0000. We can use this in many ways. For instance, say we set the byte to 1010 1110. This could mean a few things but is essentially a series of a yes or no answers when you look at it from our perspective. The first bit of 1 might mean that someone has support for IPv6 and the next bit might mean that he doesn't use SSL. They could really mean anything and it's up to you to interpret them how you want.

The problem with this is that there is no way to directly access bits other than bit manipulation which is a set of algorithms that allow you to determine a bits value or perhaps compare a bit to something else. These algorithms in general are complex but when written on paper, it's simply a bunch of math.

If you set a bit number set as 1 to 0, that means that he does NOT have the right number of vouches. If you set bit number 8 to 1, that means that he IS from us.

Let's start examining the technical issues. First of all you have to be smart to know when to use bit manipulations and when you should not. Keep in mind that accessing a bit is a hard job for the processor. Rather than saving memory, the compiler may optimize your code in a way that will make your program run slower and consume more memory than it should. BE CAREFUL.

We should mention that

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

that means OR can represent 1 if one or both of the operands are 1.

while:

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

AND only represents 1 if both operands are 1.

1 XOR 0 = 1
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 1 = 1

XOR (eXclusive OR) returns 1 only if one of the two bits is set to 1 and the other to 0, but NOT if they are both 1.

To access a bit in a byte, you have to define a mask Constance represents the location of the bit you want to access. This mask contains 1 for the bit you want to access and 0 for all other bits that you don't want to access. By selecting the right mask you can AND it with the variable that contains the sited bits and check to see wheher this location contains 1 or 0 for example.

If you access the location 2, then the mask should look like:

0 0 0 0 0 0 1 0

when it gets ANDed with the variable:

0 0 0 0 0 0 1 0 AND

0 1 1 0 1 0 1 1
_______________

0 0 0 0 0 0 1 0

Whatever the value represents it represents a non-zero variable which indicates true.

How about setting the bits in variable? By ORing the variable using the very same masks you have defined you can OR the variable for instance setting the third bit to 1 use the mask that selects the third bit and OR it with the variable

0 0 0 0 0 1 0 0 OR

1 1 0 0 0 0 0 0
_______________

1 1 0 0 0 1 0 0

How to unset the bit? Simply use the XOR algorithm.

0 1 0 0 0 0 0 0 XOR

1 1 0 0 0 0 0 0
_______________

1 0 0 0 0 0 0 0

Examples Using Bitwise Operations

Checking if a bit is set:

    int is_set(int number, int position)
    {
         return ((number&(1<<position))!=0);
    }

Set a bit:

    int set(int number, int position)
    {
         return (number|(1<<position));
    }

Count the number of bits set (i.e. number of '1's) in a value:

    int bitcount(int number)
    {
         int ones=0;
         while (number!=0)
         {
              ones++;
              number&=(number-1);
         }
         return ones;
    }