Bitwise Programming in C
This article explains Bitwise Programming in C, a common practice in most programming languages. While bitwise operations might seem like a dark art at first, it really isn’t that scary. You simply need to know when to apply these operations and for what reasons to use them.
The article discusses bits (calculation, workings) in section one previous to the actual operators so that an understanding is made on how bits operate.
About Bits
To understand how bitwise operations work, we must first understand how bits work and what bits are. Bits are usually explained as being either a number one ( 1 ) or a number zero ( 0 ), which translates into a logical TRUE or FALSE, or ON or OFF.
Bits tell the CPU (Central Processing Unit, or processor) to be either in a state of ON or OFF for a specific time-frame. This time-frame is defined by the speed of your processor and can be pseudo-calculated like so:
If the processor is 33MHz, 33,000,000 individual bits can be processed in a single second since 1Mhz = 1,000,000Hz and 1 bit = 1Hz. This means that a modern machine of 3.0 GHz is capable of processing 3,000,000,000 (three billion) bits per second. Keep in mind that this does not mean that every single bit is a processor instruction, instructions depend entirely on the processor’s architecture.
Number Representation
Binary numbers, or Base 2 notation, can only represent their numbers in sets of ones and zeros as we found out before. The number one (1) represented in binary code like so (32 bits, spacing for readability):
00000000 00000000 00000000 00000001
But numbers are normally represented in sequences of eight or four numbers, if there is too much zero-padding, which is a what this article will continue to practice.
0001
Base 10 to Base 2
Since (most) humans are taught to think in Base 10, binary does not come naturally. Often a conversion or calculation to the appropriate Base is required. Converting a Base 10 number (123 in this case) into Base 2 goes as follows:
123 ÷ 2 ≡ 61 r 1
61 ÷ 2 ≡ 30 r 1
30 ÷ 2 ≡ 15 r 0
15 ÷ 2 ≡ 7 r 1
7 ÷ 2 ≡ 3 r 1
3 ÷ 2 ≡ 1 r 1
1 ÷ 2 ≡ 0 r 1
Even though it’s calculated like this, the binary number for 123 is not 1101111 but 1111011 which is the number read from the last calculation to the first. At the first calculation we notice that 123 ÷ 2 ≡ 61 r 1 instead of 61.5. The notation 61 r 1 simply denotes that the number divided was not a round number and we received a remainder of 1. To calculate the remainder:
1 ≡ 123 % 2
or
1 ≡ 123 mod 2
Base 2 to Base 10
The following calculation is used to convert a Base 2 number into a Base 10 number:
1 × (2 ^ 6) ≡ 64 +
1 × (2 ^ 5) ≡ 96 +
1 × (2 ^ 4) ≡ 112 +
1 × (2 ^ 3) ≡ 120 +
0 × (2 ^ 2) ≡ 120 +
1 × (2 ^ 1) ≡ 122 +
1 × (2 ^ 0) ≡ 123
When to use Bitwise Operations
So far we’ve established that a computer uses a Base 2 system for calculation but haven’t explored why this is important to a programmer. The simplest usage example would be the usage of flags which will be the example used throughout this article.
#define SETTING_ONE 1 // 0001
#define SETTING_TWO 2 // 0010
#define SETTING_THREE 4 // 0100
// etcetera
In several APIs these settings are combined with the bitwise OR operator like so:
unsigned int uiflags = SETTING_ONE | SETTING_TWO | SETTING_THREE;
This usage allows the combining of settings into one single variable, to see how this works exactly, read the next sections.
Bitwise Comparing
Bitwise OR
Bitwise OR in C is expressed as a single pipe, |, not to be confused with the boolean or, ||, takes two or more integer values and combines their bits. For example the sample code:
#define SETTING_ONE 1 // 0001
#define SETTING_TWO 2 // 0010
#define SETTING_THREE 4 // 0100
int main ( void )
{
unsigned int uiflags = SETTING_ONE | SETTING_TWO | SETTING_THREE;
return 0;
}
Would result in the variable uiflags to contain 0111, or in Base 10 notation: 7. Because:
0001
0010 OR
0100 OR
---- ≡
0111
You might wonder what the difference would be compared to:
unsigned int uiflags = SETTING_ONE + SETTING_TWO + SETTING_THREE;
To show the difference, imagine the following program:
#define SETTING_ONE 1 // 0001
#define SETTING_XXXXX 3 // 0011
int main ( void )
{
unsigned int uiflags = SETTING_ONE | SETTING_XXXXX;
return 0;
}
The progam does not return the Base 10 number 4 as would be expected with the + operator, but the value 3. This because:
0001
0011 OR
---- ≡
0011
This means that the OR operator combines two binary values, but does not add them together arithmetically. Remember that with bitwise OR, 0001 OR 0001 does not equal 2 but 1.
The return value of OR will only be zero if both compared bits are zero: 0000 OR 0000 equals 0.
Bitwise AND
The bitwise AND operator in C, &, makes everything a bit more interesting. Also, this is not the same operator as && which is a logical operator. This operator allows you to check if a bit has been set in a certain place in two variables, for example:
0100
0111 AND
---- ≡
0100
Which returns a non-zero value which can be view upon as TRUE if a comparison is being made.
1010
0101 AND
---- ≡
0000
Returns false since none of the bits’ locations correspond to each other. If we take our code from the OR sample, and combine it like so:
#include <stdio.h> // for EXIT_* definition codes
#define SETTING_ONE 1 // 0001
#define SETTING_XXXXX 3 // 0011
int main ( void )
{
unsigned int uiflags = SETTING_ONE | SETTING_XXXXX;
if ( uiflags & SETTING_XXXXX ) // does uiflags contain the flag?
{
return EXIT_SUCCESS; // uiflags contains the flag
}
else
{
return EXIT_FAILURE; // does not contain the flag
}
}
Bitwise NOT
The NOT operator in C, ~, is a simple one which requires less explanation than any other operator. The NOT operator simple negates the bits set. Example:
NOT 0001
-------- ≡
1110
Which in Base 10 notation would be NOT 1 ≡ 8 This allows you to retrieve the exact opposite settings of the values given.
int main ( void )
{
#define FAST 1; // 0001
#define QUANTITY 2; // 0010
#define SLOW 4; // 0100
#define QUALITY 8; // 1000
unsigned int highSettings = FAST | QUANTITY; // 0011
unsigned int lowSettings = ~highSettings; // 1100, SLOW | QUALITY
return 0;
}
Bitwise XOR
The XOR operator, ^ in C, is another interesting operator which compares two sets of bits. Unlike the other operators, XOR checks if the bits in the position are the same and returns zero. If they are not the same, it returns one. This process is called “exclusive or”, meaning that it excludes equal values and includes differing values.
0110
1101 XOR
---- ≡
1011
This means that if you compare two values which are equal, the result could be cast as a boolean false.
1011
1011 XOR
---- ≡
0000
Or in C code:
int main ( void )
{
#define FAST 1; // 0001
#define QUANTITY 2; // 0010
#define SLOW 4; // 0100
#define QUALITY 8; // 1000
unsigned int highSettings = FAST | QUANTITY; // 0011
unsigned int lowSettings = SLOW | QUALITY; // 1100
unsigned int difference1 = highSettings ^ lowSettings; // 1111
unsigned int difference2 = highSettings ^ highSettings; // 0000
return 0;
}
Using XOR on a value of itself will always return a boolean cast FALSE.
