Fundamentals of Programming: Logical bitwise operators
As you have probably discovered already, converting a positive binary number into a negative binary number involves changing bits. As does converting a capital ASCII letter into a lower case ASCII letter. How exactly does a computer perform this action? The answer lies with bitwise operators:
Bitwise Operator | NOT() | AND() | OR() | XOR() |
---|---|---|---|---|
Description | invert input | where exactly two 1s | where one or more 1s | where exactly one 1 |
Input | 01001010 | 01001010 | 01001010 | 01001010 |
Input | 11110000 | 11110000 | 11110000 | |
Output | 10110101 | 01000000 | 11111010 | 10111010 |
So how can we use these for useful tasks in a computer? If we look closer at the examples above we can see that setting Input 2 bits to 1s or 0s has a direct inpact on the Output. We'll call Input 2 a mask, and we apply this mask to change the values in Input 1 in certain ways. Consider these questions about Masks:
- If we have an AND mask bit as 0 what is the output in all cases?
- If we have an AND mask bit as 1 what is the output in all cases?
- If we have an OR mask bit as 0 what is the output in all cases?
- If we have an OR mask bit as 1 what is the output in all cases?
- If we have an XOR mask bit as 0 what is the output in all cases?
- If we have an XOR mask bit as 1 what is the output in all cases?
In summary:
AND | OR | XOR | |
---|---|---|---|
0 | clears the value | retains the value | retains the value |
1 | retains the value | sets the value | inverts the value |
uses | setting chosen bits to 0 | setting chosen bits to 1 | inverting chosen bits, finding differences between bit sets |
Exercise:Bitwise operators
So know we know how each Bitwise Operator works we can use them with masks to calculate things: Input data 11011011, I want an output with bits 4 and 5 set to 0 and I don't care about the others. (???00???)
Answer : By using an AND I can set bits to 0 and keep other bits. The mask I need is :11100111 Input data 11011011, I want an output with bits 1 and 8 set to 1 and I don't care about the others. (1??????1)
Answer : By using an OR I can set bits to 1 and keep other bits. The mask I need is :10000001 Input data 11011011, I want an output with bits 3,4,5,6 set to 1, bits 1 and 8 set to 0 and I don't care about the others. (0?1111?0)
Answer : AND: 01111110 followed by Alternatively: XOR: 10100101 |
This might all sound a little academic, what are the actual practical uses of this? Take a look at the following:
Example: Turning a positive binary integer into a negative
We are going to convert the number 37 into -37 37 = 00100101 1. Flip the number by XORing it 00100101 XOR11111111 = 11011010 2. Add 1 11011010 + 00000001 11011011 = -37 |
Example: Finding a lowercase ASCII letter
We are going to find out the how to convert any Upper case ASCII value into its lower case equivalent. First lets find out the difference between two letters, we'll look at 'P' and 'p', and 'A' and 'a': P: 01010000 p: 01110000 A: 01000001 a: 01100001 You can probably work out the difference by looking at them, but let's use a XOR to make sure: 01010000 (P) XOR 01110000 (p) 00100000 (difference) 01000001 (A) XOR 01100001 (a) 00100000 (difference) We can clearly see that it is the 6th bit that defines whether a number is upper case (not set) or lower case (set). Now let's apply this rule to see if it works: If given the letter g what is the upper case ASCII value? g = 01100111 We know that all we have to do is get rid of the 6th bit. But how can we perform this? By using an AND mask, to return all the bits excluding the 6th: 01100111 (g) AND 11011111(mask) 01000111 (G) |
Exercise: Masks
For the example above we can also do this by using a XOR, can you find out how?
Answer : 01100111 (g) XOR 00100000(mask) 01000111 (G) What about converting an upper-case letter into a lower-case letter, try with X (01011000), you can't use AND what can you use? Answer : 01011000(X) OR 00100000 (mask) 01111000(x) |
Programming[edit]
You can program logical bitwise operators to change the case of letters and even encrypt messages. Unfortunately it isn't always possible to play around with binary digits and you may have to work with decimals instead. Let's take a look an an example using an AND:
We know that 3 = 011 and 5 = 101. If we AND the two together we get: 011 (3) 101 (5) === 001 (1)
Let's check:
Console.Writeline(3 AND 5)
You can also use NOT, XOR, NOT
and any combination of them. Let's look at a slightly more interesting example:
Example: Bitwise programming
We are going to write a short program to swap the case of a sentence that you input, for example, if you typed: Dim sentence As String Dim converted As String = "" sentence = Console.ReadLine() Console.WriteLine("converting...") For x = 0 To sentence.Length - 1 'as the 6th binary digit defines upper and lower case 'mask with 000100000 converted += Chr(Asc(sentence.Substring(x, 1)) Xor 32) Next Console.WriteLine(converted) |
Exercise: Bitwise programming
Program a bitwise mask that will flip the 2nd and 5th binary bits of each letter of an entered sentence to convert it into a secret code:
Answer : Dim sentence, converted As String sentence = Console.Readline() Console.Writeline("converting...") For x = 0 to sentence.Length - 1 'as 2nd and 5th = 00010010 converted += Chr(Asc(sentence.Substring(x,1)) XOR 18) Next Console.Writeline(converted) Write code that uses bitwise operators to display whether an input number is a Odd or Even. For example if the user inputs 9, the program should output 1. If they input 64 it should output 0 Answer : Dim input As Integer input = Console.Readline() Console.Writeline("converting...") Console.Writeline(input AND 00000001) |