A Look at Bitwise Operations
At some point in your journey to learn programming and learning about Computer science, you’re bound to come across “bitwise operations”. You may not even get told what it’s called but you may come across an example that looks something like this:
int x = 3 << 2;
or maybe you’ll see something like this:
int y = 64|35;
If you’ve never encountered bitwise operations before, you may see that and think, “What in the world is that?” This article intends to give a very brief introduction to bitwise operations, what they mean and why they are used.
It’s all 1’s and 0's
To the untrained eye, bitwise operations may seem a bit cryptic…no pun intended. But we have to remember the fact that at the very root of everything, information is stored in computers with 1’s and 0’s. So we will be dealing with binary numbers when it comes to bitwise operations.
It’s in the Title
That’s right. Bitwise operations refer to dealing with numbers bit by bit. So for example, the number 5 in base 10 is “101” in binary. So using the number 5 in a bitwise operation means we will really look at “101” and apply an operation for each bit (“1”, “0”, and “1”).
Why are they important?
Bitwise operations have its uses in cryptography, video games, hash functions. We are essentially manipulating bits, which means that this is applicable to low-level programming. This means that bitwise operations take advantage of a very important benefit that comes from dealing with purely 1’s and 0’s: speed. Now, modern processors are quite quick when it comes to calculating data but older processors are much faster when they use bitwise operations.
A Look at the operators
Bitwise operations are conducted using bitwise operators (surprise, surprise). They are not much different from the logical boolean operators. We have “AND”, “OR”, and “NOT”. Of course, we can combine some of these to describe things like inclusivity or exclusivity, and we will look at these as well. Additionally, we will touch upon manipulating bits through the use of shifting.
AND Operator
For our examples, let’s use the C Programming language. C uses “&&” as the “AND” logical operator. When comparing data, both sides of the AND operator must be true for that part of the operation to be true. Depending on the programming language you are using, the possible values can be “true”/ “false” or “1”/ “0”. In C, our possible values are 1 and 0.
The logical AND operator in C has two sides and can be written as:
A && B
This is read as, “A and B”. So what does this mean? Simply that if A is true and B is true, then the expression yields, in C, the value of 1. So if I have something like
int x = 10;
int y = 4;
int z = (x>y) && (x%2==0);
printf(“%d\n”, z);
The resulting console will print 1:
Briefly, going over the code, we have two integers, x and y, and set them equal to 10 and 4, respectively. Then we declare an integer z and set it equal to the result of the expression on the right side, namely,
(x>y) && (x%2==0)
This means to check if x is greater than y AND if x/2 has a remainder of 0. Both of these statements are true, so the expression yields a value of 1.
This is straight forward, but how is this related at all to bitwise operations? Well it’s completely different from bitwise AND. Bitwise AND is denoted as “&” (a single ampersand) and it compares both sides bit by bit.
See, the way
A && B
is evaluated, we evaluate to 1 (in C) if neither side of the expression is 0. So if we have the above code and change the line for the variable z,
int x = 10;
int y = 4;
int z = x && y;
printf(“%d”, z);
the console will still print 1 because neither side of the expression is 0. However, if we have
int x = 10;
int y = 4;
int z = x & y;
printf(“%d”, z);
the output will be the 0.
Why? Well let’s see how this works. Both 10 and 4 are base 10 numbers. Since we are using bitwise AND, we must convert them to binary to work this out by hand.
10 = 1010 remember, (1)*2³+(0)*2²+(1)*(2¹)+(0)*2⁰, hence 1010
4 = 0100
So really, we’re comparing 1010 and 0100 bit by bit.
1010
0100
— —
0000
See what we did here? 0 and 0 is 0, 0 and 1 is 0, and so on.
So what happens when we have something like this?
int x = 10;
int y = 6;
int z = x & y;
printf(“%d”, z);
Well let’s see, again
10 = 1010
6 = 0110
So we do our bit by bit comparison using AND as our operator.
1010
0110
— —
0010
0010 in base 10 is the number 2. So
z = 2.
Let’s check.
Right away we see a difference (a GIGANTIC difference).
Let’s look at a truth table:
bit A | bit B | A & B
0 | 0 | 0
1 | 0 | 0
0 | 1 | 0
1 | 1 | 1
So this is done bit by bit.
OR Operator
Next in line is the OR operator. The logical OR operator is denoted by “||” and it means that either side of the equation can be true for the expression to yield a true value (a value of 1, in our case). This is pretty simple and best represented by a truth table:
A | B | A||B
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 1
In our coding example, if we change the bitwise AND to a logical OR, C only cares if both sides of the expression are 0. If not, then the expression will yield 1.
int x = 10;
int y = 6;
int z = (x || y);
printf(“%d\n”, z);
But it is int he bitwise OR that things get more interesting. The bitwise OR in C is denoted by “|” (a single “|”) and it compares the values bit by bit but in the same manner (as long as both bit values are not 0, then we have a 1 for that bit). Let’s see how this works using the example above but replacing the logical OR with the bitwise OR.
int x = 10;
int y = 6;
int z = (x | y);
printf(“%d\n”, z);
What will be the value of z? Let’s work it out by hand.
1010
0100
— —
1110
1110 in base 10 is equal to 14. So z = 14.
The differences between the logical OR and bitwise OR are the same as the differences between the logical AND and bitwise AND. The logical operators look at the each side as a whole while the bitwise operators look at each side bit by bit.
NOT Operator
Ok we understand AND and OR. Next on our list is NOT. This one can be a little difficult to understand but we will just have to take some information as given. Otherwise we’ll have to explore into the mysterious world of complements. For more information on that just search “one’s complement” and “two’s complement” but be ready for some complicated math.
The logical NOT is denoted as “!” and it turns any true value (any non-zero value in C) into false (0 in C) and any false value into true.
A | !A
0 | 1
1| 0
The bitwise NOT, superficially works quite intuitively. It is denoted in C by the “~” and we sometimes refer to it as the complement. How dies it work? We look at the value bit by bit and turn the 1’s into 0’s and 0’s into 1’s. Simple right?
int x = 10;
int y = 6;
int z = ~(y);
printf(“%d\n”, z);
What do you think the resulting value of z will be?
0110 ←6
~(0110) = 1001 ←9 in binary, right?
So will z = 9?
Nope! z = -7. How? Why? Well without diving too much into it, the complement (bitwise NOT, remember?) is defined as the value times (-1) minus 1. Why? Well too many reasons that you can research yourself (and it would take us into a pretty big tangent).
OK, so z = -7, but how is 1001 equal to -7? We’re using ‘int’ in our code. So we’re not just dealing with these four bits. Actually we have 31 bits to worry about. Yes, you read right. 31. Not 32. At least not really. See (and this is where it gets really interesting), the very last bit is used to indicate the sign of the integer. 1 indicates a negative number and 0 indicates a positive. Still with me? Good. So really
~(6) =
~(00000000000000000000000000000110) =
111111111111111111111111111111001
Let’s have a word on how negative numbers are represented in binary by machines. Because of the way positive numbers are represented, the largest possible 32-bit signed integer is
011111111111111111111111111111111
Notice the ‘0’ on the first bit. Technically the next number in binary would be
10000000000000000000000000000000
But, again, because of the way the numbers are structured, this number is the smallest negative number that we can represent with a 32-bit integer, namely, -2147483648 (think of this as circling around from one extreme to the next). From there we keep counting up where
10000000000000000000000000000001 = -2147483647
This works perfectly since that would make
111111111111111111111111111111111 = -1
As a consequence,
~(-1) =
~(111111111111111111111111111111111) = 0
Likewise,
~(0) = -1
So here is possibly the most significant difference between the bitwise NOT and the logical NOT. The logical not looks at things in terms of only true or false (0 or not 0 in C). Using the logical NOT in C will gives us a completely different answer than the bitwise NOT:
!(0) = 1
XOR Operator
Previously we spoke about the OR operator. Looking back, we see that the OR operator evaluates to true (or 1) if either of the values being compared is true (or non-zero). This means that if both values are non-zero, then the expression evaluates to 1. This operator is inclusive. The XOR operator is exclusive, which means that it will also evaluate to false/0 if both values are true/non-zero. Let’s remember that we are doing these comparisons bit by bit. The XOR operator is denoted by “^” in C. Let us look at the truth table.
A | B | A ^ B
0 | 0 | 0
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0
So what is the effect on values? The procedure to evaluate this is very much the same as we’ve been doing. Let us take our code
int x = 10;
int y = 6;
int z = x^y;
printf(“%d\n”, z);
What is the value of z? Let’s work it out:
1010 ← 10
0110 ←6
— — —
1100 = 12
Let’s Expand
We have just discussed the basic bitwise operators. We can now mix them to formulate NAND and NOR, which are frequently used in digital circuitry. NAND refers to “NOT AND”. This means that whenever the AND operator evaluates to true/1, then NAND evaluates to false/0. There is no actual NAND operator in C programming but we can use a combination of “~” and “&”.
A | B | ~(A & B) ←Negating the “AND”
0 | 0 | 1
1 | 0 | 1
0 | 1 | 1
1 | 1 | 0
So looking at this in code,
int x = 10;
int y = 6;
int z = ~(x&y);
printf(“%d\n”, z);
What will be the value of z?
1010 ← 10
0110 ←6
— — —
1101
What number will this be? Well, let’s take a closer look.
(x&y):
1010 ← 10
0110 ←6
— — —
0010 = 2
So ~(2), as we mentioned above, will be
(-1) * 2 -1= -3
Therefore z = -3. Now let’s do the same analysis for NOR. NOR is, you guessed it, “NOT OR”. This implies that when OR evaluates to true/1, NOR evaluates to false/0. Again, there is no operator for it in C programming but we can formulate this using “~” and “|”:
A | B | ~(A | B) ←Negating the “OR”
0 | 0 | 1
1 | 0 | 0
0 | 1 | 0
1 | 1 | 0
Looking at this in code,
int x = 10;
int y = 6;
int z = ~(x|y);
printf(“%d\n”, z);
The value of z is evaluated as follows,
1010 ← 10
0110 ←6
— — —
0001
Looking at it closely, we know that (x | y) is 1110, which is 14 in base 10. Therefore, ~(14) is
1*(14) -1 = -15
Therefore z = -15.
Shifting bits
The next step in our learning process is to look at shifting bits to the left or right. What does this mean? Left shift is denoted by “<<” and it describes a shift of bits to the left by a certain number. So if we do something like
6<<1
This really means for
0110 ← 6
each bit gets moved to the left by 1:
1100
This number evaluates to 12 in base 10. Interesting…let’s keep looking at this.
6<<2 = 11000 (binary) = 24 (base 10)
Do you see the pattern? Each shift to the left by n bits means we’re multiplying by 2^n. Therefore
6<<2 = 6*2² = 6*4 = 24.
Notice when we shift the bits to the left, the other bits to the right are left with 0’s.
Likewise, we have a right shift operator denoted by “>>”. This is when we shift the bits to the right. Let’s look at 6 >> 1. Then
0110
becomes
0011 = 3
The pattern is the opposite as the left shift. Instead of multiplying by a 2^n we divide by 2^n.
Bonus: Applications!
Let’s take a look at a way to use this in video games. Suppose we let the player be represented by
1000 (binary)
Maybe we let a power-up be
0100 (binary)
Enemy1 can be
0010 (binary)
Block1 can be
0001 (binary)
We know intuitively that these objects will interact differently with each other, if at all. We want the player to have a different interaction with the enemy than with the power-up. When we run through the game loop and detect a collision between some of these game elements (player, Enemy1, power-up, block1) using “|”, we can make a certain event happen depending on the resulting number, which describes the interaction. In pseudocode,
interaction = asset1| asset2
if(interaction == 1010) // player|Enemy1 =1010 (binary) = 10 (base 10){
code to take health away from player
}
Conclusion
Bitwise operations can look tricky at first but working them out makes the problems intuitive. One must remember the difference between logical and bitwise operators. Logical operations look at items as a whole, where bitwise operations look at items bit by bit.
