A fun challenge for programmers who have never attempted before is to write an algorithm
which reverses the bit order of a series of bytes (or any data type for that matter).
As usual, there are multiple ways to accomplish this task. I show just one here.
First off, if you are not already familiar with them, make sure to read up on your bitwise
operators such as the and, or, xor, and bit shifting operators. For my method, I use the
bit shifting operators and the bitwise "and" operator.
With the aforementioned operators, one can easily reverse bit order by comparing each bit
in the byte with 1 and storing in a new variable in reverse order.
To shift the bits to the right by one bit, we can use:
bits >>= 1;
Storing the bits in reverse order is as easy as shifting the new variable to the left by one
and setting its bit to 1 (if necessary).
reverse <<= 1;
reverse += 1;
We can tell if it is necessary to store a 1 by doing a bitwise "and" operation on the current
bit with the number 1. For example:
01010101
00000001
Comparing the two with the & operator returns
00000001
because the right-most bit is the only one that is set to 1 in both series of bits.
With this information we can develop an algorithm to check each bit in a byte and store
the bits in reverse order.
Let's look at some code that exemplifies this.
//headers
#include <iostream>
#include <ctime>
//namespace
using namespace std;
//function prototypes
unsigned char Reverse(unsigned char bits);
void PrintBits(unsigned char bits);
//MAIN FUNCTION
int main(){
//seed random generator and get random number
srand( (unsigned int)time(NULL) );
unsigned char byte = rand()%256;
//show bit order
PrintBits(byte);
cout << endl;
//reverse bit order
byte = Reverse(byte);
//show reversed bit order
PrintBits(byte);
cout << endl;
//end main
return 0;
}
//reverse bit order of a byte
unsigned char Reverse(unsigned char bits){
//local variable to hold reversed bits
unsigned char reverse = 0;
//loop 8 times (8 bits in a byte)
for(int i=0; i<8; i++){
//shift bits to the right by one starting at second bit
if(i > 0)
bits >>= 1;
//shift reverse order to the left by one
reverse <<= 1;
//if current bit is 1, make current bit in reverse 1
if((bits&1) == 1)
reverse += 1;
}
//return reversed bits
return reverse;
}
//print an unsigned char to console in bit form
void PrintBits(unsigned char bits){
//loop 8 times (8 bits in a byte)
for(int i=0; i<8; i++){
//shift bits right by one starting at second bit
if(i > 0)
bits >>= 1;
//if current bit is 1, print 1 to console
if((bits & 1) == 1)
cout << 1;
else //otherwise print 0 to console
cout << 0;
}
}
|
