Alright, the last section of our memory data and addressing portion, is going to cover a little bit about Boolean algebra. The kinds of things we need to know, the kinds of operators we need to know about to do some bit level manipulations on the bits were storing into memory. let's go through the basics of Boolean algebra really quickly. Boolean algebra was developed by Goerge Boole, that's who it's named after, in the 19th century. And basically it's an algebraic representation of logic. We encode True as a 1 and False as a O. again, binary number system and we have a few basic operators. A very important one is the logical AND often represented with an ampersand as in operator. that says if the variable A and the variable B are true, then the AND, the product of their values in Boolean algebra is also true, okay? So, A&B is 1, when both A is 1 and B is 1. similarly we have the OR operator which as you'd expect, is true if, A is 1 or B is 1, or both. And then of course we have the exclusive or operator. Often abbreviated as XOR. which is true if A is true, or B is true, but not both. So, it excludes that case. That's where that X comes from. And then finally we have a Unary operator in Boolean algebra. That says the NOT of A, or the complement of A, is is just the opposite value. So, if A is 1, then its complement is 0. And vice versa. If A is 0, then its complement is 1. interesting law in Boolean algebra that can be derived from basic principles is De Morgan's Law. Which basically says the complement of the OR of two variables is the same as the AND of the complemented variables. And this can be very valuable when we want to eliminate ORs to have only ANDs or eliminate ANDs to have only ORs. In a logic expression. Here are another representation of these basic operators in what are called Truth Tables. Here we see the operator, in this case the AND. And the val, the possible values of one variable. And the possible values of another variable. And this is the AND of the two. So, when they're both 0, then the AND is 0. When they're both 1, the AND is 1. And when either one of them is 0, then the result is also 0. So, in the case of AND, it is 1 only when both are True or 1. For the OR, which we use the vertical bar you'll see that it's a 1 whenever either one of them is a 1 and only 0 when both are 0. For the Exclusive OR, again, if one is a 1, but not both so, in this case, we want to make sure that this is a 0 as well. That's the difference to the OR case that we had here. And then, the Unary operator, of course is only one variable and it's just the opposite of the, of the value. So, that's the basic of Boolean algebra. How we use this to manipulate bits? Well, we can have two bytes in memory. Here we're showing two bytes. And we can AND them together bit wise one bit at a time. So, we can AND 0 and 0 and of course that result would be a 0. 1 and 1 the result would be a 1. In these two, the next cases these are all zero the result except for the last one where again the two values are one so we would expect the one as a result okay? So, this would be the resulting AND across these two variable, so the OR case the same values again. As long as one of them is a 1, we expect to see a 1 down here. So there's only two cases where we would end up with a 0, here and here, where both variable values are 0. finally, for the Exclusive OR. where would we expect to see zeros? Well, certainly here, where they're both 0. certainly here, where they're both 0. But also where they're both 1. And that's here at the end. And also right here in the second column. So, that result, is the corresponding one for XOR. And then for the bit wise compliment or not, we would just expect to see the bits flip, okay? So, this is the the Boolean operators applied to bit vectors. In this case just the bytes lengths of bits. And in C we have these exact same operators available to us and they can apply to any integral data type long, int, short, or character. remember character being just a byte. and the arguments to these operators appear are treated as bit vectors. And the operations apply bitwise. So, you can see here we've declared three byte variables a b and c. you'll notice here that we're setting the value of a to the hex four one. That's represented here in its bit notation. And when we take the compliment of a. and assign it to b, this is the value we get and assign it to b. In hex, this is BE, not immediately obvious, from the 41. Okay, but you can see that the 1 and e add up to 16, and the 4 and b add up to 16. Alright if we take the value of 0 and put it in a, as in this case, then the compliment is just FF all ones. Here's a case of an AND. we've taken 69 and 55 as bit vectors represented here in In these values. This should say 69, not 41. And, sorry about that error there. This is a 6, and 9. And, the, the bit vector is correct however. And, a and b, is just this string of, of 1s and 0s. Again, similar to the example on the previous page, which results in a 41. Okay. So, this is how we do bit-level operations in in C just using those basic operators. Okay. So, the other thing we should know is that zero is always viewed as false and anything that is non zero is true. So, the value doesn't have to be one to be true. Anything that is not a zero is interpreted as true. Now, when we're talking about bits, of course, the only values we can have are zero or one. But if we apply a logical operator to an entire series of bits. For example, an entire byte at a time, or an entire int at a time. Then it will only be considered false if that entire int is equal to zero. In other words, all the bits are zero. And anything else. So as long as there's any one anywhere, then it will be considered as true, alright? This is very useful, for early termination of if statements. And, we'll see that a little bit later on. but let's take a look at a few examples. here's the compliment. Again this is now the logical operator, not the bitwise complement, so we're using a different symbol. The exclamation point or bang rather than the tilda. And so the complement of 41 is what we'd expect from our logic is to be zero, false. You'll notice its not the bitwise complement, that was a different value In this case, it's simply zero. If we take the complement of zero, what would we expect to get? Well, actually anything would do that has at least a one, one in it, that would be true, but by convention, we'll just flip one bit and make it equivalent to a hex zero one. Alright, if we and 69 and 55 as we did on the previous page, we know this result would've been 41, if we had done a lot bit wise operation. But in this case, this value is interpreted as true, this value is interpreted as true. So, our result is simply true. Or one. if we then do 0 and with 55, a 0 is false, so our results should be false, as it is. again let's do an an OR operation and we would see 69 true or 55 also true, is just going to result in a 1. Okay? So, how does this early termination help? Well, for example, suppose that we're looking to increment the value at which p points. P is a pointer. to a particular value. And, what we're concerned about is that we actually do have a pointer, and that our pointer isn't null, or all zeros. So, we can first say, well, is p true, meaning not zero? so, by putting into an, a logical AND statement, we can do that test. Here, if p is all zeros, a null pointer, we know that the and is going to be false in the end. So, we can just not do that, not continue evaluating this expression, and it would stop right there. On the other hand if p is something else, other than zero, then we can assume it's not null. And it's probably a valid address. And we can de-reference it. Go to the place it points. Get the value and increment. Okay? So, this is a shorthand notation for if p is true, then increment the value at that pointer. But often in C you'll see this as a quick shorthand instead of having to write that in. But this could be placed in the middle of an expression even to help check that pointer. Alright, lastly I want to show you how Boolean algebra can be used to represent sets. We'll be using this in a few places during the rest of the course. So, we can take a bit vector of w bits let's say maybe that's just eight bits for now. so, what we can do is have each bit represent an element of a set, in this case the set can have up to eight elements. And you'll notice in this example here I have this particular vector, and I can have each bit represent 1 element of the set. So, this bit sequence would represent the set of element 0, element 3, 5, and 6. Because those are the ones I've set to 1, okay? Here's another example. Slightly different set. 0,2,4,6. Okay. So, you kind of get the hang of how we could represent a set using a bit vector. And now our operators, our bit wise operators, are pretty interesting. The AND can be viewed as set intersection, because it will only be true if the element is in both sets. So, if we AND these two bit vectors together, we would get this result, which says that 0 and 6 are elements of the intersection, 'kay. Similarly, OR corresponds to set union. If we OR those two values, we would get this bit vector, which represents 0, 2,3 ,4, 5, and 6. You notice that is the union of these two sets. All the elements present. Exclusive OR corresponds to what's called the symmetric difference. In other words, elements that are in one set, but not both. In this case, the elements 2, 3, 4, and 5. And a Compliment is obviously the complimentary set. So, the compliment of the first one, of the second set here is 1, 3, 5, and 7, alright.