Advance Bit Manipulation

Bitwise Operators

C includes operators to manipulate memory at the bit level. This is useful for writing low level hardware or operating system code where the ordinary abstractions of numbers, characters, pointers, etc… are insufficient — an increasingly rare need. Bit manipulation code tends to be less “portable”. Code is “portable” if with no programmer intervention it compiles and runs correctly on different types of computer. The bitwise operations are 10
Typically used with unsigned types. In particular, the shift operations are guaranteed to shift 0 bits into the newly vacated positions when used on unsigned values.

~	Bitwise Negation (unary) – flip 0 to 1 and 1 to 0 throughout
&	Bitwise And
|	Bitwise Or
^	Bitwise Exclusive Or
>>	Right Shift by right hand side (RHS) (divide by 2)
<<	Left Shift by RHS (multiply by 2)

Do not confuse the Bitwise operators with the logical operators. The bitwise connectives are one character wide (&, |) while the Boolean connectives are two characters wide (&&, ||). The bitwise operators have higher precedence than the Boolean operators. The compiler will never help you out with a type error if you use & when you meant &&. As far as the type checker is concerned, they are identical– they both take and produce integers since there is no distinct Boolean type.

Multiply a given value with 8 without using * or +

Sounds impossible? It’s not!

Y * 8 = X
Y << 3 = X
2^3 = 8

Remember this:

2E+4	2E+3	2E+2	2E+1	2E+0
16	8	4	2	1

Sure you do, think back to when you first learned how to convert from decimal to binary…

Can anybody give me a more mathematical explanation?

What else can I do with bit manipulation?

Bit manipulation can be used to store true/false (Boolean values) in less bits than by just using standard bool values.

Let me explain:

Bool	1 Byte	8 Bits	Can store 1 true/false value
Char	1 Byte	8 Bits	Can store 8 true/false values

How is this possible? Well, with bit manipulation!

Example:

To raise bit:

Char field = 0 ;
Field |= 0x001 ;

To check if bit is raised:

If ( Field & 0x001 )
MessageBox( NULL, “Raised”, “Raised”, 0 ) ; // Check if bit is raised…

DWORD mask[] = {
0×000000001, //0 1
0×000000002, //1 2
0×000000004, //2 4
0×000000008, //3 8
0×000000010, //4 16
0×000000020, //5 32
0×000000040, //6 64
0×000000080, //7 128
0×000000100, //8 254
0×000000200, //9 512
0×000000400, //10 1024
0×000000800, //11 2048
0×000001000, //12 4096
0×000002000, //13 8192
0×000004000, //14 1024
0×000008000, //15 2048
0×000010000, //16 4028
} ;

class BitBool
{
public:
DWORD field ;

BitBool( void )
{
field = 0 ;
} ;
BitBool( DWORD val )
{
field = val ;
} ;

bool Get( int idx ) ;
void Set( int idx, bool val ) ;

BitBool &operator=( BitBool &val ) ;
BitBool &operator=( DWORD val ) ;
} ;

bool BitBool::Get( int idx )
{
if ( idx < 0 || idx > 31 ) return false ;
return ( ( field & mask[ idx ] ) > 0 ) ;
}

void BitBool::Set( int idx, bool val )
{
if ( idx < 0 || idx > 31 ) return ;
if ( val )
field |= mask[ idx ] ;
}

BitBool &BitBool::operator=( BitBool &val )
{
field = val.field ;
return *this ;
}

BitBool &BitBool::operator=( DWORD val )
{
field = val ;
return *this ;
}

Why would one like to do this?

With today’s computers it is almost never needed but imagine you have 1024 Boolean values to send over a standard telephone line via TCP/IP.

With standard Boolean values it would require 1 KB of data to be sent, but with bit manipulation only 128 Bytes. Small optimizations like this can speed your program up…

Basic Encryption

Encryption is another use for bit manipulation. Here is a very basic encryption program using XOR.

Tips: XOR is good for encryption because applying it with the old value it was XORED with turns the bits back into their previous values.

Example:

We have to characters:
‘a’ and ‘b’
We want to encrypt ‘a’ by XORING the bits of ‘b’ into it.

To encrypt:

Int encrypted ;
Char c, key ;
C = ‘a’ ;
Key = ‘b’ ;
Encrypted = c ^ key ;

Which yield this result:
‘a’ = 97 which is 01100001, b’ = 98 which is 01100010
Encrypted now equals: 00000011

Void Encrypt( char *message, char *key, int msglen )
{
int I ;
byte new_key ;
// Make key more secure… Hash key
for ( I=0; I for ( I=0; I {
*message ^= new_key ;
message++ ;
}
}

Now to decrypt:

Int old ;
Old = encrypted ^ key ;

Which gives us the binary number 01100001, which is? Yes, we have ‘a’ again.

Void Decrypt( char *message, char *key, int msglen )
{
// Reverse XOR by XORING it again…
Encrypt( message, key, msglen ) ;
}

So now we have the basic components behind the encryption of chars.

Now all we have to do to encrypt a file is read all the chars from the file, one by one. Encrypt them with given key and save it back to a new file. This same process can then be repeated to decrypt the file.

To make this method a bit more secure replace:

Old: Byte new_key ;
New: DWORD new_key = 0xCDC31337 ; // Random number

Old: *message ^= new_key ;
New: *message = *message ^ ( new_key >> ( 8 * ( I & 3 ) ) ) ;

Checksums

Another thing XOR is often used for is checksums. Checksums is a very efficient way to ensure that a message you receive is authentic.

Assume you receive a message
{ 0×16, 0×32, 0xF1 }

Checksum is added by XORING all he chars together:

char Checksum = 0 ;
For ( int I= 0 ; I < len ; I++ )
Checksum ^= buffer[ I ] ;

When you receive the message, it’s authenticity can be checked by reversing the previous process.

Char check = buffer[ len – 1 ] ; // checksum is the last char in the buffer

For ( int I = len - 1 ; I > 0 ; I-- )
Check ^= buffer[ I – 1 ] ;

If ( !Check )
MessageBox( NULL, “Authentic”, “Authentic” , 0 ) ;

This is often used at device level because it is very easy to implement!

Final thoughts about XOR

You can easily update the encryption and checksum methods to be more secure. Just use you imagination. The checksum can be made more secure by having two checksums, one for even bytes and one for odd…

Ones compliment (~) can also be used to create an encryption routine.

I also received some code to crack the XOR encryption. I will publish more on this topic soon. I just need to test the code. It is illegal to crack encryption code in some countries so please use this information at your own risk.

The 2 biggest problems with XOR encryption are that it is relatively easy to decrypt and key exchange is very difficult.

How to convert from binary to HEX

0101 1110 1010 0111
5 14 10 7

0101111010100111 = 0×5EA7

Every four bits of a binary number will equal one hex number. This makes it easy to convert them.

Tags: bit, encryption, XOR