Posted on 20 Apr 2014

Bitwise Operations in C++

Why am I talking about messing with bits?

A while ago I decided I wanted to learn more about how cryptography works. In the past I have used encryption in some projects through libraries such as PyCrypto, but I wanted to get a better understanding of how it is actually doing what it does. When doing cryptography you always want to operate on raw bytes rather than encoded strings, so the first thing I needed was a way to encode/decode base64. Upon reading up on base64 via it's wikipedia page I decided I should brush up on bit manipulation since I haven't had a need to use that in quite a while.

This should be a pretty short and straight forward post, and then I will probably have some more posts on other cryptography topics such the base64 encoding/decoding, XOR encryption, and maybe go into block ciphers. We'll see how things go, but for now let's stick with the topic at hand!

Shifting left and right

So to get started let's take a look at the left shift(<<) and right shift(>>) operators. When you use the left shift operator you are moving all of the bits in the variable a given number of places to the left. The format of the call is x << num_of_places. So for example if x = 4, represented in binary as 00000100 and we want to shift three places we would call x << 3. When shifting left zeros are added as padding to the right of the number, so we end up with 00100000 or 32. If you know how binary numbers work it will probably come as no shock to you that left shifting is basically a way to multiply by a power of two. The above is the same as saying 4 * (2^3) = 32. Something to note for left shifting is that if we are working with a single byte with a value of 128 and we left shift we will end up with 00000000. The right shift operator is the equivalent of integer division by a power of two. If x = 44 or 00101100, then x >> 3 is the same as 44 / (2^3) = 5.

Bitwise AND(&), OR(|), and NOT(~) operations

The bitwise operators, as you may guess, do their work on the bits of data rather than bytes that their counterparts(&&, ||, !) use. Let's take a look at what each is and then see some source with them in action!

Bitwise AND is useful for a few things, one being to check if a bit is "on" in a given set of bits. The rule when using bitwise AND is that if either bit in the operation is off(0) then the result is 0, otherwise the result is 1. Bitwise OR is the opposite of that where if either bit is on(1) then the result is 1, otherwise the result is 0. This is useful for turning on a bit. Finally, the bitwise NOT is used to get the inverse of a given set of bits. So for example if you have the byte 00100010 and applied this operator to it the result would be 11011101. Bitwise NOT is useful when you want to turn a bit off by combining it with bitwise AND.

So that is the gist of those 3 operators, and here is a bit of code showing them in use.

bool check_bit(const unsigned char byte, const unsigned char bit) {
    // & a bit = if either is 0 then 0 else 1
    return (byte & 1<<bit) != 0;
}

void toggle_bit(unsigned char &byte, const unsigned char bit) {
    if(check_bit(byte, bit)) {
        turn_bit_off(byte, bit);
    } else {
        turn_bit_on(byte, bit);
    }
}

void turn_bit_on(unsigned char &byte, const unsigned char bit) {
    // | a bit = if either is 1 then 1 else 0
    byte |= (1<<bit);
}

void turn_bit_off(unsigned char &byte, const unsigned char bit) {
    // & the inverse of a bit to turn it off
    byte &= ~(1<<bit);
}

You may notice in the code the use of 1<<bit. Remember that 1 == 00000001, so we are left shifting to the position in the set of bits we are wanting to check/change. One other little trick with using the bitwise NOT is to be able to see what the max size of a type is. This can be done simply like so:

unsigned char maxUC = ~0;
cout << "\nMax unsigned char size: " << (unsigned int)maxUC << "\n";
unsigned int maxUI = ~0;
cout << "Max unsigned int size: " << (unsigned int)maxUI << "\n";

Bitwise XOR(^) - Don't worry it isn't scary!

The final bitwise operator to talk about is the bitwise XOR, or "Exclusive-OR". The rule for bitwise XOR is that if both bits being compared are 0 or 1 then the result is 0, otherwise the result is 1. So if you XOR 01001000 and 01000100 the result would be 00001100. There are a couple things to keep in mind, and then I will show some code using XOR.

First, given the rule I just stated you may see that you can use bitwise XOR to get the same result as using bitwise NOT(~). For example, given 00100010 XOR'd with 11111111 you get 11011101 just as above. Next, say we have three variables, x,y, and z, each representing a set of bits. If you take x ^ y and assign the result to z, then call z ^ y you then essentially have x ^ y ^ y. This flips every bit in x twice by y, resulting in the original value of x. The xor_swap function below shows this in use. Let's take a look at ways we can use bitwise XOR.

void toggle_bit_xor(unsigned char &byte, const unsigned char bit) {
    // ^ a bit = if both are 0 or 1 then 0, else 1.
    byte ^= (1<<bit);
}

void xor_swap(int *x, int *y) {
    // x now equals x ^ y
    *x ^= *y;
    // y now equals original value of x(y ^ "original_x" ^ y)
    *y ^= *x;
    // x now equals original value of y("original_x" ^ "original_y" ^ "original_x")
    *x ^= *y;
}

That swap may seem tricky, but if you read the comments you should be able to wrap your head around it. Also, while the xor_swap works perfectly fine and is a cool example for using XOR, it isn't something I would recommend you really use unless necessary(which shouldn't be often, if ever, for most).

And we are done!

So hopefully that wasn't too bad. Using bitwise operators is something that just takes a little messing with to understand, and for me a little refreshing once in a while since it isn't something I have to use often. In the future I will probably show a some of these in use via the base64 encoding/decoding I mentioned at the start!