why would i ever work at the bit level?

while it may seem a bit onerous to work at the bit level, the fact of the matter is that it's very useful.

 

here, i am providing an example of encryption with the bitwise XOR operator. an example of hashing at the bit level can also be very informative.

 

 

an example of bitwise operators

implemented in c++

If you don't ever foresee yourself EVER working at the bit level, you need to find more interesting things to work on.

If you believe that your programs are not as 'high and tight' as you'd like, perhaps you could squeeze in some bit operators. This is where computers are REALLY efficient and fast!

For full disclosure: we actually never work on an individual bit. Even the bit operators only work on individual bytes (8 bits).

OK. let's start digging into the good stuff: base 2. (Why is everything base 10 in our world?)

00001000 represents 8 (here, there are 8 bits for a byte of information)

00000001 represents 1
00000010 represents 2
00000011 represents 3
00000100 represents 4
... ad infinitum

Now, if we use the leftshift operator in c or c++ '<<' what will happen is that every bit gets shifted to the left the specified amount of spaces. So, the following will result:

00000010 << 2;
= 00001000

and this is simply 8, as seen above. Now, what the left shift operator does is multiply the operand by two! and it does it faster than calling a routine which does some sort of arithmetic (actually, i'm not sure about this. the routine that is called may very well be the left shift operator)

 

now, let's look at the bitwise OR

The bitwise OR operator, operator| works like the logic gate, OR. What that means is that when you give it two inputs (which themselves can each be either a 1 or a 0) the output will be a 1 if either of the inputs was a 1:

00101100 | 10110000;
= 10111100

perhaps easier to see this as the following:

00101100 |
10110000 =
-----------
10111100

where the bit is a 1 if the corresponding bit was a 1 in either of the two operands (inputs).

 

now, let's look at the bitwise Exclusive-OR

XOR

The Exclusive-OR operator, ^ in c and c++, works similarly to the standard OR, but that it will only output a 1 if one and only one of the input bits is a 1. So, one OR the other, but not both. Let's see this:

00101100 ^
10110000 =
------------
10011100

great... now watch this:

one of the fantastic properties of the XOR operator is the following: Say you have a byte of information, well let's just keep it to a bit for now. Let's say you have a bit A, and another bit B. If you take A XOR B and then you XOR again with B, you get A back! (think about it)

so, you may not see it yet, but this property is pretty powerful!

here's a classic programming scenario: we have two integers and we want to swap their values.
(say x=9 and y=76)
how can we swap their values without using a temporary variable??

think about it... i'm about to tell you so stop scrolling down until you figure it out

got it?

int x = 9, y = 76;

and to switch their values i simply do the following:

x = x ^ y;

and now you're thinking... well, there it goes. you shoulda made the temporary. BUT, remember that if we do the XOR operator again, we will get back our original, as follows:

y = x ^ y;

right? now the first statement left y unchanged. so i was free to use it again. and as explicitly stated above, when I do XOR twice with the same operand on the right hand side, i will get the original left hand side back. so, now my y is my original left hand side: x.

x = x ^ y;

now, what happened there? i took our A XOR B and i did another XOR with A (since y now is our B). what did this do? it gave us back our B: y now has the original value of x.

cout << x << ", " << y << endl;

this will now print out:

76, 9

VOILA!

 

now, the big daddy.. encryption

Exclusive-OR encryption

now for the real fun stuff

so, this isn't the Rivest, Shamir, and reluctant Adleman (reluctant according to Steven Levy) algorithm that we have all grown to love and hold so dear, yet it is a fairly robust little way of encryption and fun to implement.

So, as explained above, the XOR will only output a 1 if one and only one of the inputs was a 1. Thus, even if you have the output that A XOR B = 1, you don't know if A or B was 1. this is actually powerful, since we can recover the value of A if we know the value of B. Thus, if we encrypt A by taking the XOR operator with the key B, we can get A back by the XOR operator again with the key.

let's see this in action. we will write a small script and use a key to encrypt it using the XOR bitwise operator.

we will loop through each byte in our string of characters, using the XOR and our key:

#include
using namespace std;

int main()
{
   char document[13] = "it was brian";
  char key[13] = "ABCDEFGHIJKL";
  for(int i=0; i < 12; ++i){
   document[i] = document[i] ^ key[i];
   cout << document[i];
  }
  return 0;
}

and this will print out our encrypted document as the following:

(6c3$5g*;#*"

and nobody will be able to lay their eyes on my document. unless of course they have the key, which will simply reverse the operation and return our original document.

#include
using namespace std;

int main()
{
   char document[13] = "it was brian";
  char key[13] = "ABCDEFGHIJKL";
  for(int i=0; i < 12; ++i){
   document[i] = document[i] ^ key[i];
   cout << document[i];
  }
  for(int i=0; i < 12; ++i){
   document[i] = document[i] ^ key[i];
   cout << document[i];
  }
  return 0;
}

and, as you guessed, this will print out the incrimination:

it was brian

 

 

Appendix

why do we use base 10?

Well, we're fairly stupid beings and we need to be able to count on our hands. Voila! base ten.

to be sure:
the Maya used a base 5 inside of a base 20 numeral system, and NOT because 360 is a rough estimate for the number of days in a solar year -they had that estimated to five decimal places:
365.2422 days!

This is my "intellectual" property.

The views and opinions expressed on this page are strictly those of the page author. The contents of this page have not been reviewed or approved by Colorado State University. If you would like to use anything from this site, it is best practice to ask permission. I teach my son to share, so the probability is almost surely one that I will oblige.