Fundamentals of Programming: Logical bitwise operators

From Wikibooks, open books for an open world
Jump to: navigation, search

UNIT 1 - ⇑ Fundamentals of Programming ⇑

← Modulo arithmetic Logical bitwise operators Set 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(\overline{P}) AND(P.Q) OR(P+Q) XOR(P \oplus Q)
Description invert input where exactly two 1s where one or more 1s where exactly one 1
Input P 01001010 01001010 01001010 01001010
Input Q 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 all 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
OR: 00111100

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)
  Blank.svg Code Output
Down arrow Hexagonal Icon.svg

1

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:

  Blank.svg Code Output
Down arrow Hexagonal Icon.svg

The Cat sat on the Matt
converting...
tHE cAT SAT ON THE mATT

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)