BIT OPERATORS

INTRODUCTION

All John Von Neumann's architecture computers work only with bits(b) and bytes(B).
Bits could be: one(1) or zero(0), and bytes are usually aggregations of eight bits. And all computer will
work with are operations of: storing, moving and performing some transformations on those bits.

In this article we will keep our focus on those bit operators: not( ~ ), and( & ), or( | ) and xor( ^ ).
However, we will mention left-shift( << ) and right-shift( >> ) as well.

DEFINITIONS

The only unary operator we are going to really use is negation( ~ ). From technical point, this operator
will turn one into zero, and zero into one.
Even do, this might not sound magical, this operator does appear in many more complex expressions.
Beside, this binary operator we have: all-zeros, all-ones and identical operator.

X <all-zero> <identical> <not> <all-ones>

1 0 1 0 1
0 0 0 1 1

EXAMPLE:
all-ones = ~0,
all-zeros = ~1.

For binary operators, the story gets up-bit more complex, because we would need to have two
operators, usually noted as x and y(other notations could be seen as well).
The result of and operation is true(1) only if both operands are equal to one.

X 1 1 0 0
Y 1 0 1 0
X&Y 1 0 0 0

EXAMPLE:

x & y,
x &= 15;

Next, common operation is or, which will be equal to false(0) only if both operands are equal to zero.
This operation is usually noted in this way: x or y.

X 1 1 0 0
Y 1 0 1 0
X|Y 1 1 1 0

EXAMPLE:

usigned int uiResult = x | y;

x |= 16;

Next interesting operation is known as exclusive or(xor). As it could be concluded from it's name, the
result of this operator will be true if and only if one of operands is true.

X 1 1 0 0
Y 1 0 1 0
X^Y 0 1 1 0

There are: Sheffer's and Lukasiewic'z operators as well. This two operators are interesting from
theoretical point of view, however you might create functions or macros for them as an exercise.
And there are some more operators like: nand, nor, xnor, etc...

EXAMPLES:

#1 In order to illustrate how binary operators work, we will create next program.

#include <stdio.h>
#include <stdlib.h>

#define OPERAND_X 12
#define OPERAND_Y 10

int
main( void )
{

unsigned short int the_result = 0;

system("clear");

the_result = OPERAND_X & OPERAND_Y;

printf("%d AND %d =%d \n", OPERAND_X, OPERAND_Y, the_result );

the_result = OPERAND_X | OPERAND_Y;

printf("%d OR %d =%d \n", OPERAND_X, OPERAND_Y, the_result );

the_result = OPERAND_X ^ OPERAND_Y;

printf("%d XOR %d =%d \n", OPERAND_X, OPERAND_Y, the_result );

return EXIT_SUCCESS;
}

In order to understand this example we would need to know that:

( 12 ) = 0000 1100
( 10 ) = 0000 1010.

The OPERAND_X = 12, and the OPERAND_Y = 10, will serve as a example numbers.

The expected output would be:

12 AND 10 = 8
12 OR 10 = 14
12 XOR 10 = 6

I hope that you will understand the meaning: 8 (0000 1000)2, 14 = (0000 1110)2, 6 = (0000 0110)2.
In order to have better output, via binary numbers, one could create the function that will present the
binary numbers from the decimal ones.

#2 In this example, we will see how unary operator NOT works and also how left-shift and right-shift
operators could be used.

#include <stdio.h>
#include <stdlib.h>

#define ALL_ZEROS 0
#define ONE_AT_THE_END 1

int
main( void )
{
system("clear");
unsigned char the_operand = ONE_AT_THE_END,
the_result = ~ONE_AT_THE_END;
unsigned short int the_counter,
the_limes = 16;

printf(" 0000 0001= %d \n 1111 1110= %d \n", the_operand, the_result );

for( the_counter = ONE_AT_THE_END;

the_limes >>= 1;
the_counter <<= 1 )
{
printf(" %d \n", the_counter);

return EXIT_SUCCESS;
}

*The first thing we have in the main function, after the terminal is cleared, is the definitions of some
variables. Two of them are of the unsigned char and two are of unsigned short int. The initial values for
the first variable will have all leading zeros and one 1 at the end, the second one will have all leading
1's and the last bit will be equal to zero.
The counter is used in for loop and the_limes is for upper limes in our for loop.

*Then we present the results when negation is applied.

The expected results are: 1 and 254.

* The last output is produced from for loop. In order to understand this, I will say that upper limit is
calculated with the_limes >>= 1.
We also have the_counter <<= 1, this will multiple the_counter by two, this happens because when we
shift binary number for one place left, it will increase the number by multiple of two. Yeah, we have
binary base.
The expected output is: 1, 2, 4, and 8.

#3 In this example code, we will see, how we could count how many ones in the binary representation
of the binary number there is.

#include <stdio.h>
#include <stdlib.h>

#define NUMBER_1 254

#define NUMBER_2 255
#define NUMBER_3 256

unsigned short int

count_ones_binary( unsigned short int number )
{
unsigned short ones = 0,
last_bit = 0,
mask = 1;
while( number )
{
last_bit = ( mask & number );
 number >>= 1;
ones += last_bit;
}

return ones;
}

int
main( void )
{

unsigned short how_many_ones = 0;

how_many_ones = count_ones_binary( NUMBER_1 );

printf("The number %d has %d ones in its binary representation\n", NUMBER_1, how_many_ones );

how_many_ones = count_ones_binary( NUMBER_2 );

printf("The number %d has %d ones in its binary representation\n", NUMBER_2, how_many_ones );

how_many_ones = count_ones_binary( NUMBER_3 );

printf("The number %d has %d ones in its binary representation\n", NUMBER_3, how_many_ones );

return EXIT_SUCCESS;
}

The main function has tree calls, with different arguments: 254, 255 and 256. Then the number of ones
is presented to the user.

In the function count_binary_ones, we have some local variables, and we will be looping till number
reaches zero. Beside this, we have mask to check the last bit of the number, then we shift-right the
number to lose one bit on the front and to prepare the number for test of the last cypher, then we need
to increase the count of ones by one or not, depending whether if we have the last bit equal to 1 or 0.

EXAMPLES OF PRACTICAL APPLICATIONS

In order to get the negative number from the positive one, it is possible to use operator(-), but this will
do the same job ~x+1; as well.

Next example will check if the number x is odd or even: x & 1.

In order to do more practical work, try to test if the number is positive or negative. This property of
integers can be tested, if we check whether the one is leading bit for negative numbers and leading zero
will be sign of the positive number.
For further exercise, try to test if we have 1 at certain location of the binary representation as well.
In order to test if we have 1 at one of two bits, we could use something like this:

x = 1100 ( 12 )
y = 1010 ( 10 )

r = x | y;

In order to encrypt some text, it is possible to use xor.

For example:

(10) 1 0 1 0 ( original code )

( 6 ) 0 1 1 0 ( key )
--------------
^ 1 1 0 0 ( encrypted code-12 )
0 1 1 0 ( key )
--------------
^ 1 0 1 0 ( original code )

As we could see, we have started with 10 and applied the key 6 and we have 12 as a result. Now, when
we would like to decrypt the text, we need to use the same key ( 6 ) one more time.

Beside, usual application of multiplication or division by two for right-shift could be used in for loops
like this:

for( i = 0; … ; ...)
{
some_code;
}

and for representing some sets with combination with operator or.

EXAMPLES OF OPTIMIZATION

Intention of this section is not to provide complete manual for professional programmer, but rather to
rise the awareness of small things that could add up.
However, it must be mentioned that some of those tricks will be optimized by the compiler. Do, some
of them are still useful. Even do one switch will optimize it one way, it is still useful.

So, there are few interesting examples:

The first example is very important, because it will work with logical expressions as well.
( x and y ) or ( x and not(y) ) = x

As we could observe there are: two variables on the left side( x and y) and there is four operators( and,
or, and not). On the right side there is just one operator and no operation.

Now let's see how math will differ from actual programming.
I hope that you have heard about De Morgran, if you have and you know what I will be talking in the
next few lines you might skip this part.

So, let's observe well known mathematical fact:

not( a and b ) = not(a) or not(b)

In this example two sides of this equation are equal, but from programming side of the story there is
way more to it.
The left side has two operations: not and and. The right side has three of of them: not, or and not.
And is more likely to be false, so as soon as a is equal to false we could say that part ( a and b ) is equal
to false and there is no more need to calculate the rest of the expression.

Now, if we observe similar rule:

not( a or b ) = not(a) and not(b)

We would be tempted to use the same logic. On the left side there are two operations and on the right
side there are tree operations. Usually, it is better to use lower number of operations.
However, in this case it is more likely to have true as a result for application of operator or and as soon
as a is equal to true we would be able to stop any further calculations. So, we would need to know the
nature of the process as well, in order to apply the best estimation.

This gets more and more interesting, when we have more general cases:

not(x1 or x2 or x3 … or xn) = not(x1) and not(x2) and … not(xn)

or

not(x1 and x2 and x3 … and xn) = not(x1) or not(x2) or … not(xn)

Here is one more example:

not ( not(x) or not(y) ) = x or y

I will leave this analysis for the reader.

Next example is bit more complicated, because it has three variables : x, y and z.

( x and y and z ) or ( x and y and (not z) ) or ( x and y and z) or ( (not x) and y and z )

it could be optimized into:

( x and y) or ( y and z )

Now, we could ask us selfs, could we have more optimized expression …

After this, I will state two formulas:

p = x and y;
z = ( (not x) and y ) or ( x and (not y) );

and leave that for some exercise, you can create the function or the macro.

SCENARIOS IN WHICH WE MIGHT NEED TO USE OPERATORS

Beside optimization, binary operators could be used in order to develop drivers. Yeah, we all have
heard about drivers and it's usage in order to bridge the gap of assembler oriented programming and
procedural oriented programming as we usually use in C, and later object oriented programming in
C++.

Hope that you have heard about Arduino project. If you have not heard about it, look at their site and
analyze the code, it is very C alike.
So, is digitalWrite any interesting, and how about pinMode etc...

One very interesting fact is that most hardware devices have some registers that store some data, and
that info could be useful in our programs. There are some wrapped functions that get delivered with our
C compiler, but underneath it all, we have some bit operators.

Now, I will state one well known function that is used in order to figure out, if the character is upper
case.

int
isupper( char c )
{
return ((( c >= 'A' ) && ( c <= 'Z'))? 1 : 0);
}

So, I am out of my ideas, but there are few important infos you could use:
the ASCII code for 'A' is 65 and 'Z' is 90, and if you prefer hexadecimal form 'A' is 41 and 'Z' is 5A.
For exercise, try to use bit operators in order to avoid ternary operator.

There are also interesting applications for pixels that have colors.

USING BINARY OPERATORS IN PROFESSIONAL STYLE PROGRAMMING

In one of our earlier articles we have shown how to use variadic functions, and as we have said that
could lead us toward programs like: ls, diff, dd(hope it is not short for “destroy disc”) etc...

So, what is common to all of them?

Well, among other things they all use switches: -a, -p, -x etc...

And in order to incorporate that, we will analyze one simple example.

Let's say that we would like to sort the numbers in one array, for that the most logical name would be
sort.
Now, you would have two options: to sort array in ascending or descending order. Later, you would
also add option to have that array with or without repetitions.

But let's start with ascending sort. For that, we would have:

#define ASC 1
#define DES 2

and in order to check if the user has picked ASC or DES order, we could have it implemented like this:

if( ASC & pic)

{
sort_array_ascending();
}
else if( DES & pic )
{
sort_array_descending();
}

Now, if you would like to have it fuzzed, you could use something like:

#define FUS 4

if( FUS & pic )

{
perform_fuzzion( );
}
Next thing to do, could be application of switch in order to generate faster code.
And, don't forget to use: arc and argc in order to get those switches you need, in this particular case sort
would have: -a, -d, and -f.