Set
A formal collection of objects, which can be anythingMay be finite or infiniteCan be defined by:Listing the elementsDrawing a pictureWriting a rule defining what is insideOperations ’– =Cartesian Product:A B = { (x, y) | x A and y B }Think of picking food from a menu: how many possible meals?The empty set is a subset of every set. It’s unique.
Sets of strings
Begin with an alphabetΣΣn= all words with n “letters”Σ*= all words of any length, including length 0* in general means “0 or more instances of”0* means all words containing any number of 0’s only(0 + 11)* means anyconcatentationsof “0” and “11”“language” = any set of words fromΣ*Example: Let’s sayΣ= { a, b }.L = {ε, a, b,aa,ab,ba, bb } is a language with 7 words. This language happens to beΣ0Σ1Σ2.Example: set of legal identifiers
Working with sets
Boolean algebrasCharacteristic value of a setBit vectorsRepresentationOperationsUse in programming languageExample: Vacation programBit masks
Properties
Set theory and propositional logic are bothbooleanalgebras.What do we mean by “an algebra” ?Definition of abooleanalgebra: a mathematical system with values 0 and 1 and operators + and * having these properties:Closure,Commutativity,Distributivity, identity element, inverseLogic and set theory are “subclasses” ofbooleanalgebra. They inherit these properties.
Properties (2)
What is the practical consequence?Expressions involving set operations are analogous tobooleanexpressions.So, to verify that A (B C) (A B) (A C), we can do so by converting it to the corresponding propositional formula, and seeing if it’s a tautology.a (b c) (a b) (a c)In general, another way to show X Y is to pick an arbitrary x X and show why it must be in Y.To show X = Y is done in two parts:X Y and Y X.
Characteristic value
Often, a set consists of just whole numbers.E.g. { 1, 4, 6 }In this case, it’s convenient to refer to the set by a single numerical value: the set’s characteristic value.The value is the sum of all 2iwhereiis a number in the set.E.g. { 1, 4, 6 } 21+ 24+ 26.The binary representation of this number shows the set! This is called abit vector.
Logic operations
Examples10101101 01101011AND 11110000 AND 00011111Try the same examples with “OR” and “XOR”Observations:What happens when you AND with a 1? With a 0?What aboutOR’ingwith a 1 versus a 0?What about XOR?How would we …Make the rightmost three bits all 1’s? All 0’s?
Operations
Inside the computer, set operations on bit vectors are very fast.Notation in C, C++ and Java: | & ^ ~Let’s look at x = { 1, 4, 6 } and y = { 3, 4, 5 }.How would you handle subset?
Blank cells are zero.
Binary number
Value is based on powers of two:This number equals 128+32+8+4+1 = 173Interesting relationship between unary ~ and –~n = – (n + 1)
Shorthand
Occasionally we need to write a large number in binary. Better to do so as “hexadecimal” – a shorthand that compresses 4 bits in one symbol.Notation: begin with “0x” followed by, usually, 8 digits.Each digit is: 0-9, a-fa = ten = “1010” d = thirteen = “1101”b = eleven = “1011” e = fourteen = “1110”c = twelve = “1100” f = fifteen = “1111”Example: What does0x7ffc0look like in binary?
Shift operations
Two directionsShift left (<<) basically means to multiply by a power of 2.Shift right (>>) essentially divides by a power of 2 and eliminates the remainder.For example1 << 4= 24= 165 << 3= 5 * 23= 4013 >> 1= 13 / 21= 6
Practical use
Let’s suppose we want to use an integer to hold 31booleanvalues, representing the days of a month. We’ll use bit positions 1-31 only.Start withsept= 0, clearing all bits.To turn on a certain bit, we need to “or with 1”sept=sept| (1 << 29)To turn off a bit, we need to “and with 0”sept=sept& ~(1 << 29)How would we determine value of just 29thbit?Multiple bits? …
Mask
Often we want to inspect/modify more than 1 bit, so we need to create an operand that looks like:Ones in middle: 0000000000111110000000Zeros in middle: 1111111000001111111111How? Two waysCan subtract powers of 2Use only bitwise operations
Examples
~0 … 11111111 11111111~0 << 5 … 11111111 11100000~(~0 << 5) … 00000000 00011111~(~0 << 5) << 4 … 00000001 11110000And you can invert one more time if needed.How could we write this as a difference of powers of 2 ?
Bit field
Store more than one value in a variable, to save space.Example: date as month-day-yearHow many bits do we need for each?date = 0date |= month << 16date |= day << 11date |= year
0
Embed
Upload