Embedded - 241: One Two Blah Blah Blah Ten

Episode Date: April 13, 2018

Andrei Chichak and Alvaro Prieto (@alvaroprieto) join us to talk about bits and how to manipulate them. Alvaro is host of the Unnamed Reverse Engineeringpodcast. His other Embedded appearances are 130, 200, and 215. Andrei (“Andrei from the Great White North”) works at CBF Systems. His other Embedded appearances are 99, 114, 139, and 200. Andrei wrote about bit manipulation as part of Embedded Wednesdayson Embedded.fm: Logic in C, part II. Andrei recommends using ISO646.hto reduce confusion around bit manipulation. Also, his suggested calculator is the SwissMicros DM16L Elecia wrote an introduction to binary and hex. For more information about programming and binary, see How to Count by Steven Frank For advanced bit twiddling, check out: Bit Twiddling Hackswebsite Hacker's Delightbook by Henry S. Warren Jr (1st Edis also available)

Welcome to Embedded. I am Elysia White, here with Christopher White. And we are joined by Andrei Chichak and Alvaro Prieto. Hey guys, what's happening? Hello. It's snowing. It's snowing. That's not possible. It's like mid-April. Where would it be snowing in mid-April?

In the Great White North. So that's Andre from the Great White North. And Alvaro, will you say hello? Oh, hey. Yeah, it's not snowing here. I'm about an hour north of you. And this show is going to be one of our basics episodes, which is why we have our past guests. The theme of the basics episodes are to teach something we think is critically important to embedded systems engineers, but also to talk about how to teach these things and why they are important to embedded software engineers.

The goal today, specifically, is to talk about bits. 80-bitty little bits. In our kibbles. Binary, hexadecimal, bit manipulation, bitwise operations, powers of two, and where this all fits into our chosen career. So, I guess we should start with the definition. Andre, what's a bit? It's a

binary digit, but what the heck does that mean? If we go back, let's go back in time. If we go back to the works of George Boole. The logic guy. He came up with this. Yeah, the logic guy. Well, that's the thing. Basically, you're dealing with a system that has two values, true and false, and a few operators and or not things like that and we can we can understand that but now we move forward a whole bunch to a guy by the name of claude shannon everybody yay yay he's all right

yay there you go come on apparently claude shannon was the guy who took boolean logic the trues and falses ands and ors and stuff like that and figured out how to implement it in hardware so the trues and falses became ons and offs and switches and then when the computer started coming around, they figured, hey, this is very applicable to what we're doing. And we came up with the representations of a relay being on, being a one, the relay being off, being a zero, relay, switch, whatever. Now it's a gate in a in a circuit and it all maps back to george bull with his trues and falses ands and ors and nots being turned into ones and zeros how's that that was way more historically in depth than i expected but cool okay so bit is the smallest unit of I expected. But cool. Okay, Chris? So a bit is the smallest unit of computer storage.

It is either a zero or a one. All right. I like both of those. Alvaro, what's a byte? Eight bits. Eight bits usually. Well, let's not do that. A byte is eight bits.

Don't go there. Yes, a byte is usually eight bits. You're not going to drop that, are you? And a nibble is half a byte. Four bits. I don't know why we're going out of order. Well, because nibble is only funny if you know that it's half a byte. It's like you nibble. What if your byte is seven bits wide?

Then what's a nibble? Say this is what happens when you say a byte is not necessarily eight bits. The reason I say bytes are not necessarily eight bits is that there are a few processors out there that use 16-bit bytes. Those processors should all go away. I think they just misnamed their data with... No, but let's not go too far into that. Let's go back to the binary.

Chris has this book that he really wants to talk about. No, I don't. It's going to take like an hour before we can open the pages. So, bits make up binary. Binary is all about ones and zeros. It's all about what computers use and it's not anything any of us

actually has to know, is it? Yes. How often do you write in binary? Write in binary? What do you you write in binary? Write in binary? What do you mean write in binary? How often do I manipulate binary numbers? Three or four times a day?

Yeah, and that's the thing, is it's not just about the binary, it's about what we can do with it. And Andrea definitely alluded to that with the logic. So can we say more about binary or should we skip to hex? Well, I mean, you might want to say how it's counted briefly. Okay. So you have, let's go with a nibble.

This is four bits. And if all four bits are 0, 0, 0, that's what a nibble is, four bits, then that equates to zero. And if it's 0, 0, 0, 1, then that equates to one. I mean, this is just normal, except that then you get 0, 0, 1, 0, and that's's two because we only have two bits here. It's like right now we have 10 fingers. And so we're used to counting one, two, blah, blah, blah, 10. And that's normal. But what if you only had two fingers? And that's what binary is about. If you wanted to count to 20 on your 10 fingers, you didn't want to use your toes. You have to count up to 10 and then remember the one,

and then count up to 10 and then remember the two. Or you'd have to use your friend's hands. And so with binary, that's kind of what we're doing. We're saying zero, one. Okay, now remember that we already overflowed. Okay, now we're going to do 1, 0 is equal to 2, and 1, 1 is equal to 3, and 1, 0, 0 is equal to 4, 1, 0, 1 is equal to 5, and it goes on like that. And the pattern is much easier to see visually, but if you get in your head that imagine you only had two fingers, and you if you get in your head, imagine you only had two fingers, and you had to use your toes to, and you only had two toes, too, and you had to build up all of this.

And so that's how I describe binary over radio, which I will never, ever, ever do again. Why did I not choose Android for that? Can I take a shot at it? Can I take a shot at it? Can I take a try at it? Sure. So mathematically, if you think of a, just think of a number normally, not binary, a three-digit number, right?

123. Okay. Each of those digits corresponds to a power of 10. So the rightmost one, the three, corresponds to 10 to the 0. So you multiply 3 times 10 to the 0. 10 to the 0 is 1. So if you look at that digit, its value is 3. The next digit over is the 2.

That one is 10 to the first power. So if you wanted what that digit represented, you'd multiply 2 times 10 to the first.. So if you wanted what that digit represented, you'd multiply 2 times 10 to the first. So that's 20. 20 plus 3, 23. Same thing for the one digit on the left. That would be 10 to the 2. 1 times 10 to the 2 is 1 times 100. 100. So you do the same thing for binary, except instead of tens, it's twos. So the rightmost digit is 2 to the 0. The next one over is 2 to the first. Next one over is 2 squared, 4, and on and on and on.

So when you're looking at a string of binary digits, you can start from the right and just multiply that digit times 2 to the 0, multiply the next one by 2 to the 1, next one by 2 to the 2, next one by two to the two, and add them all up, and you'll have a decimal number. And this is why powers of two are so important to know. Yes. And if you take a look at it as a language, a binary has basically two symbols in the whole language, zero and one.

So when you're putting together a binary number, you can string together zeros and ones. Much like in decimal, you have zero through nine. In binary, you have zero and one. Okay. And that's all I got. Okay. So hex, Alvaro. What's hexadecimal? Okay. I think we've... And that's all I got. Okay. So hex, Alvaro, what's hexadecimal and why do we care?

That's just, well, it's for us humans. It's an easier way to read things, basically, right? The machine doesn't care. But instead of using a base 2 number, like binary, us humans use base 10. So we have all those 10. But let's say your nibble, your four bits, you can count up to 16 in decimal. So I don't know who decided. It's like, hey, if we count up to zero through nine,

then A, B, C, D, E, F, you can count to 16 with a single character. And then you can represent a byte with two characters. Anywhere from 0 to F. And so in hexadecimal, it's like I have 16 fingers instead of 10.

Yep. So instead of having to write 0 through 255, which takes a variable number of, you know of up to three digits, you can compact that all into two digits. Well, it's hard with binary because if you want to have eight bits, I mean, that's eight characters, but they're very boring characters. They're just zeros and ones. If you want to make it more compact, you could use base 10, but then you're not really showing that things are in binary. And you use base 16 because it maps well to the binary world. Yep.

Powers of two. Powers of two. Some of the older computers used to use three bits, and so you'd have values between zero and seven. And that was known as octal but it uh it got pretty strange to uh like it once again got very large so they added an extra bit but they you know now you're suddenly going above nine and you need some extra symbols so they grab the A through F. And this is why we do not start numbers with 0 and C.

Because you might. Yes. Oh, because it turns into octal. If you start it with X, it's hexadecimal. If you start it with 0, it's octal. And if you start it with nothing, it's decimal. How very exciting. It's almost as though we couldn't write these things out.

Okay. I'm not going to ask what you use hexadecimal for, because I think we're going to get to that in great detail. Maybe we should instead talk about ands and ors. So and is a conjunction I think we're all pretty familiar with. If I say Christopher and I are going to the grocery store, that means we're both going to the grocery store. If I say Christopher or I is going to the grocery store, however grammatically that would sort out, that would mean one of us may be going to the grocery store or both of us, but not none of us.

If I say Christopher and not me are going to the grocery store, that means Christopher's going to the grocery store and I'm not. But there was an and in there. Note that there was an and in there. It was Christopher and not me. If it was Christopher or not me, then it's super confusing and you shouldn't do that. I totally lost it. Well, I think we should start with, before we get into logical operators, we should start with what you can do with binary because it's 0 and 1.

Right? You're jumping ahead to operations, but maybe... Go ahead. Okay. Explain the thing you want to explain. I just want to make sure we're all on the same page. So, because it's a 0 and 1, you can represent things that are true and false quite easily.

Whereas if you had decimal numbers, what does that even mean? 5 is true? I don't know. So, since you can represent things that are true and false easily, you can is, what does that even mean? Five is true? I don't know. So since you can represent things that are true and false easily, you can keep state around, or you can keep representations of things that are on or off.

But when you have things like that, you want to be able to manipulate them and compare them and say, is this thing on while this thing is off? Or are both these things on? So that's why this is important. I just, sorry, wanted to know why it's important.

Anybody else want to add anything? No. No. Okay. No, it's cool. So where I was going with the ands and the ors and the nots is to truth tables, which is probably something you saw in school and something you probably don't use now because that was such a boring lecture.

But the idea that you have two things, and you represent all of the possible options with the and and the truth table. And this lets you know what these binary things are going to be. Now, the truth tables are not things you should remember. You should be remembering what the and means or the or means or the not means. You shouldn't just memorize the truth table because if you forget some piece, you're in total trouble. Pete Or if you get the table completely wrong. And you're relying on the table. But if you think about and, and is both and and or is one or the other, and maybe both, and not is the opposite.

XOR is a little more confusing because it's exclusive or. And that's Christopher XOR I go to the grocery store means one of us goes to the grocery store. Exclusive. So it's either he goes or I go. But not both and not none. Right. And so that's either he goes or i go but not both and not none right and so that's a little confusing but if you just what does exclusive or mean it means exclusive and or so i don't know i i think truth tables are important so it basically means exactly one of them is on. Yeah. So if you're going to a grocery store that can only

handle one white at a time, so if both of you show up, the place shuts down. And so, why are these important? That's so you can do computers. No, they let you do arithmetic. I mean, you can do math with them, and then you can make decisions based on them. It's the basis for digital logic, right?

Yeah. But how do we get from math? How do we get from and, or, x, or, not to math? Andrea kind of alluded to it. This was where Shannon blew the socks off people. Exactly. See, and with our decimal number system,

we have other sorts of truth tables like multiplication tables and addition tables and things like that. But with binary, all that we've got is ands, ors, nots, exclusive ors. So if we want to represent other sorts of number systems like our decimal number systems, Shannon came up with a method of doing ands and ors and nots to change binary into, well, to represent decimal as a series of binaries and using binary operations to simulate additions, subtractions, multiplications, divisions, things like that and then there was this thing that kind of

blew my mind with when we talked about all of these logical things and that was de morgan's law does anybody remember what that is if so if not i get to explain it, you know. You could. I didn't want to. It's too hard. Okay. De Morgan's law. Not A and B is equal to not A or not B. To which you say, what the hell does that mean?

Well, it gets worse. Not A or B is the same as not A and B. It goes both ways. It's how the operations distribute, right? Yeah. So it's like the associative law of mathematics. Yeah. A times C plus D equals A times C plus A times D. So when you have to do this associative thing

for the logical operations, it's weird, because not a and b is not just not a and not b. That's actually the wrongest thing. Wrongest. New word. Instead, not A and B is the same as not A or not B. And so it changes the ands to ors. And that's really important in electronics because sometimes it's easier to get an and gate or an or gate. And so the whole thing becomes a lot more possible if you can switch between ands and or or an OR gate. And so the whole thing becomes a lot more possible if you can switch between ANDs and ORs however you want.

And DeMorgan's Laws gives you a way of doing that. It's also a good way to clean up your code. If you have an IF with lots of complicated logical stuff, sometimes DeMorgan's Law lets you rewrite that in a cleaner way. Yes. If I didn't get an ADC error and I didn't get an I2C error and I didn't get a stuff-up error,

then do something else. Or you can have it be if not or all of those. That really didn't make sense to me. It's okay. I'm sure you know what I'm talking about. We don't need to explain it well enough that people can go use it right now. We just need to explain it well enough

that people can go look it up. And you don't really need to remember the name to Morgan's Law. I actually had to look up the name. I knew it was Morgan something. Thank you. You didn't? That was in my university-level logic i mean i've learned it but i totally if you had just asked me randomly walking down the street i would have been like what law

i could totally have answered it i just chose not to i would have blown your mind because i know that one i actually used to hang out with the morgan dude drank a lot of coffee. Christopher's a liar, liar, pants on fire. Really? What tipped you off? Okay, so I think we've got these logical things down, and we've talked about if statements, so we know about logical if statements. But we also started talking about binary and those aren't i mean if you use logical

operations and you want binary operations it's bad i mean this is this is the bug where you where you do a and and b and instead of a and b oh i see what you're saying if you're in c and you want bitwise versus logical you really have to know the difference so can someone explain the difference can i blow your mind for a second blow our minds blow our mind back when they were putting c together the uh kernahan and anyway the guys that richie no he wrote the book who was it ken thompson and thompson and richie anyway the guys who wrote language they they had this all figured out where they would figure out the ands and ors from context so that there was no question as to whether you should use the logical or bitwise ands and ors and equals until somebody decided that they were going to do these weird assignments of ands and ors and equivalences, and they said, oh crap, it's going to be too much like effort to do it from context,

and they came up with equals equals and and ands and ands and or ors and ors and all that crap. So the short answer is the logical operations are like double characters. So if you have and, which is usually ampersand, the logical operation is and, and. And the bitwise or arithmetic operation is just simply and. It doesn't apply to plus and minus, because that's something completely different.

Well, but the main thing for C, the logical one spits out a single bit, right? And then the bitwise one does the whole variable you're acting on. Okay, so if I have a logic operator and I have A equals 1 and B equals 1, and I do A and and B, what do I get? One. And if I do the bitwise operation, A and B are, what do I get? One. And if I do the bitwise operation, A and B are both still one, what do I get?

You still get one. Okay, so they're the same, right? No. So now let's say A equals 10 and B equals zero. Is this 10 binary or 10? Nope, not that one. A equals 10 and B equals 8. 10.

Oh no, I'm headed somewhere. I just have to do it No, 8 and 10 isn't going to work for where you're headed. Fine, you do it. Okay, so

A equals 10 and B equals 8. And with logical, they're both non-zero, so they're both true, so the answer there is 1. With bitwise, with the

single and, with a equals 10 decimal, and b equals 8, when you and them, you get 8. Is that not the weirdest thing? I mean, you don't get 1 like you did before. You get 8. And you don't get 10 like you did before. You get eight. And you don't get ten.

Gotta look at the binary. Oh my god, I need to know what each one of these is? No. The computer does it for you? If you're going to use it that way. This was hard for me to start with. The idea that I needed to know all of these numbers and how to put them in hex. I have strategies for this, but does anybody else remember how they got used to figuring out which bit was which?

The dumb way. What was the dumb way? Years and years and years of just doing it the hard way. What's the hard way? The way I described how to figure of just doing it the hard way what's the hard way the way i described how to figure out binary numbers at the top of the show adding it up it got easier once i realized that you could divide it into nibbles yeah and the nibbles were hexes yeah that's where the hex comes in just to get to learn 16 because then you only have to do binary with four bits. Or four fingers, as it

turns out. I count all my fingers. How did he know I was holding up four fingers? I don't know. He's magical. It's true. So what I... There were two things I did. First, when I have

insomnia... Oh, no. I multiply powers of two in my head and I try to remember what they are. So like two times two is four, two times four is eight. Okay, so that's three. And then two times eight is 16. So that's four and so i basically taught myself to know where the bits are by not sleeping um and yet it is a good way to go to sleep and because once you get up to like uh 14 bits it's really hard to keep it in your head and it's easier to just go to sleep

uh the other thing 32 768 65, I'm addicted to my notebooks. And this is one of the great things about graph paper. You go ahead and you write down the number in binary. You take your 10 and you write it down. And if you need to use a calculator to figure it out, that's fine. Do that. But so you write down your 10 and then you write down your eight and you put them both in binary and you line them up. And now if you need to and them or you need to or them or you need to not or do something with them. They're lined up. And just like Chris said, those bits line up so they must survive the end. And I think that writing things down like this was so helpful. It doesn't have to be in a permanent notebook. It can just be on a sticky

note, although graph paper is really useful. And then you start to be able to see the nibbles too and how you can put them in hex without killing yourself because you have them written four bits at a time. Does this, I mean, is this what you guys did? Or is this just... Yeah, pretty much eventually. I mean, in college, the graph paper, like you said, now I just use the calculator program in every OS that has a programming mode, and then it shows you the bits. I like the calculator, and I use it sometimes,

but when you're looking at a data sheet and it says, in order to turn on the FIFO, you need to set bit seven of this register. You do have to do that translation some yourself. Well, I used to do that, but now you just click on bit 7 and it turns it on and it shows you the byte. But the other way I would do it was just with the powers of 2, like Chris said, and just shifting stuff over. But Alvaro,

what if you had to do computer work in a world where all the computers were destroyed and you didn't have a calculator? Oh, blast. You got me. Lightning round. What's two to 17? Two to 17 is a hundred and something.

Thousand. No, it's, um, let's see, that would be 32 million. No, it's, let's see, that would be 32 million. No, it doesn't. Sorry, I just imagined that lightning round could have been just random.

What's this number? Yeah, it's 131,072. I did have a friend who interviewed somewhere, and one of the questions was what was 2 to the 12, which is 4096, so you don't strain yourself. But it was, the person who told me this was complaining that it was a stupid question. And I was like, no, that's totally reasonable. If you know that off the top of your head, then you probably know all the binary stuff you need to know, which is totally arbitrary.

If you can't figure it out, even if you don't know off the top of your head, if you can't figure it out, that's kind of... Yeah, no, that's a great firmware interview question. Like, just an easy first question weed out if someone doesn't know what they're talking about. All right. Okay. You could figure that one out on your fingers, too. You'd be surprised. I've had some really bad interviews.

I thought you were going to tell us how many fingers you have. I really thought that was going to be about number of fingers. It's like, I don't have 12 fingers, Andrew. I couldn't have answered that. You're not the six-fingered man okay i kind of alluded to uh bits and registers and i want to go in that direction because this is one of the areas where a lot of embedded engineers first have to deal with these uh bits and and knowing what they are. So getting away from just the technical, tactical, how do you figure it out? Can anybody else talk about why we need these for registers?

Andrew? Can anyone? Andrew? Okay, a lot of the peripherals in the processors that we're working with are, each one of the bits has a particular meaning. So if you want to enable and interrupt, you have to set to this particular bit. If you want to turn on the UART, you have to turn on a particular bit in a register, leaving all the rest of them alone so you end up having to um set and clear particular bits in peripheral registers all of the time this is just a normal thing that you do when you're setting up a processor or even if you're doing bit manipulations with your GPIOs and you want to turn it on, you end up having to turn on one particular bit in the IO register for that port. But you don't want to affect all the rest of the bits in that port. So you have to leave those alone. Just turn on one particular bit. How's that? Okay, there's a lot there.

How do I turn on just one bit? The typical way of doing it is to read what's in the register. So you take a copy of the values that are in the register or in the port right now. You mask off the bit that you're interested in, and you write it all back. What does mask mean? Ooh, that's good. I mean, the way I think of masks is if you go back to graph paper and you have your binary number and some squares and then you get another piece of graph paper and you punch holes in the bits that you care about and you put that piece of paper on top of the bits and only doing operations on the rest. So you would do that with and another number. So the holes you cut out on the graph paper would be ones on, on your mask. So if you have on a nibble, uh, one, one, zero, zero,

you're masking off the lower two bits. You're, you're ignoring them. So, so if you have, um, one, one, one, one, and you mask off the lower two bits, you're only left with one, one, zero, zero. If the original number was zero, one, zero, zero, and you masked off the lower two bits it's still going to be zero one zero zero but i i visualized it as if i was covering up the the bits so what you're saying is basically you you have a number which tells you which bits to hold steady yes and i'm locking these bits in place,

but these other bits are the ones that I'm going to manipulate. Yep. So you have a binary number, and some of them say hold steady, and some of them say these are allowed to change. And then you use an and operation to... They will get zeroed out. Right. Yeah.

But the next operation you do will need to affect that. They will get zeroed out. Right. But the next operation you do will be to change them. Okay, so trying to combine what you all said and realizing that we throw around the word mask a lot, but wow, it's hard to explain.

If I have A equals 10 and B equals 8, and my A is a register that is going to affect a GPIO, set it on and off, and I mask it with B, does that mean that the result of A10 masked with B8, is that 2 or 8? Well, it depends how you define mask, right? If you only wanted to change a single bit, you would use the inverse of that to mask it. So if you want to change, in a case of a nibble, if you want to change the second bit, you would do every other bit would be one and that bit would be zero. So you're basically leaving everything else alone, making that zero, and then you can either make it

one or zero with an or. So you're saying that I can do A and B, but the real key is that after that, I'm going to manipulate the results of A and B. Yes. Okay. And so masking is not just a two thing operation. It's actually the results of two things goes into the third, and that's what masking really means. Yes. Okay.

So when we set a bit, we read it. We read the register. Going back to what Andrea was saying, we read the register. Actually, Andrea, why don't you we read the register and then we do something to it and we want to set a bit what do we do okay what what you're looking for is what operation are you going to do on on a value that would make a bit turn on. So you don't know if it's a zero, you don't know if it's a one, but you want the result to be a one. As it turns out, if you take any value, any binary value, zero or one, and you or it with a one, your result will be one. So one or 1 is 1. 0 or 1 is 1.

So what you're going to be doing is an or operation with a 1 in the position that you want to turn on. So if it's GPIO 3 and my GPIO register is set up so GPIO 3 is the third bit over, then i'm probably going to or it with an eight yeah okay but what if a one zero zero because one is in the third bit and that's the bit you want to turn on and the zeros you don't remember that now The zeros aren't going to affect anything else in the result. And that's important. So your mask is, yeah. So if you want to turn something on, you or it with zeros with a one in the particular position that you want to turn on. Yes. What if you want to turn something off to clear it this is this is one of those things that people just you look at this code and you're like i don't know this is gross i mean so now we're looking for an operation that independent of which binary number you give it, zero or one,

what would give you a zero? So an and with a zero, if you have a zero and zero, you get a zero. So your pattern, your mask, will all be ones with a zero in the position that you want to turn off. So if I want to turn off my pin three in my GPO three, then I want to use an AND. I want to turn it off. So I want an AND. But before I was using 100. So now I need to use 011.

It's sort of like 100. It's just that everything is backwards to what you need inverted not it so how can we take 1 0 0 and turn it into 0 1 1 tilde which means is that what this called not if it's a 0 make it a 1 if it's a 1 make it a 0 well and this is confusing because with logic operators not is the uh exclamation point yeah and i always felt like it should be the double exclamation point but to match all the others but this is super confusing instead to not to bitwise not to invert a uh a binary mask

you use the tilde key. And that's the shift. Is that the right name for it? And it's on the left of the number one. Tilde, yes. And you have to use shift to get it. Yeah. So it's up there next to escape and one and tab.

I call it the squiggly. Tilde is not usually what I remember. The squiggly. Okay, and that's the weird thing. You go in and you see this code that says GPIO and equal not 0100, and you're like, okay, that is the most inscrutable piece of code that is incredibly common uh but it's it's to clear things it's to make it so that that bit is zero and the rest of

the bits are unchanged okay you guys all thought we would get way past here by now, didn't you? No. No, this is basics. So basically what you're doing is you're making a mask, however it's necessary, and then you take your value and your mask and you do some sort of a binary operation on it to get your result i i think the single bit um it's also like when you'd have multiple bit uh um items in a register it makes a lot more sense to use a mask or to think of it as a mask right when when let's say you register the first two bits um mean uh which mode your device is in, right? You have four modes. So you have to clear the first two. So you have to mask everything else, keep it, clear the first two.

Then you can write a two-bit number to change it. Because with a single bit, you could just and or or to get that particular bit. But in the multi-bit case, you actually have to think about it. Okay, let's mask this off, and then we can write or variable or your value in. And so that would look like register equals register and some mask, and then you would then or it with the value you want.

Okay. I think we need to move on from this. I think we're going to move on from this. Let's shift over to another topic. Oh, thank you. Nice. Wow. Nice.

I was going to go with circular buffers, but now clearly we're going with chips. Good segue. Angle brackets. Angle brackets are not just for templates. How would I put the, like if you know that you want to do the third bit in your register, how would you put the one in the proper position to make your mask well you could do it explicitly and just pound define yeah my my super duper mask equals one zero b one zero zero zero

b one zero zero yes or or if i know it's eight i can just put eight or if i know it's eight in hex i can put zero x eight or if it's an octal yes okay so yeah okay so we we pound that we define this ahead of time if it's a variable amount oh yeah i don't know this is where shifting comes in shifting so cool real cars don't shift themselves great i can get more email about that than anything we've ever done uh okay so shifting shifting is a little angle brackets and they're the ones that uh that are above the period and the comma and so there's left shift which points to the left and right shift which points to the right it's greater than and less than yes greater than and less than

except it's doubled so it's double good and if you want to shift shift one bit over three places so that we get to eight you left shift it over you shift it up.

So it'd be one less than less than three. Yes. Got it. And if you wanted to shift something down, it would be greater than greater than. So this is really useful with registers because then you don't necessarily need to pound to find everything initially. You can actually just generate them

and not worry so much about using that calculator on your computer. It's also multiplication and division in binary. Because every time you shift something over by one bit, you multiply by two.

This is the coolest and worst thing ever. Why? Well, on one hand, it's super cool because you can divide and multiply by two for nearly free on your processor. If you want to divide or multiply by two, it's one instruction. It's super fast.

But most compilers will let you divide by two and will automatically do it for you. Because the shifts and divides, while not necessarily, I mean they are bitwise operations, but they also have divide and multiply, so they're also regular operations.

People look at them and go, what the heck is this? So you have to be a little careful using shifts where it's not appropriate. On the other hand, it's super fun. It looks cool. Andrew, you were got bits that are shifting across bytes. And if you're just taking that value and shifting it, down below the compiler is going to take the lowest bit from this byte, put it into the top of the next byte, and do all that work for you. And the compilers are a lot smarter than you think. So doing a divide by two, the compiler is just going to generate all of the shift writes for you anyways, and the code ends up readable. Whereas if you're going to be very

clever and say, oh, I'm going to save so much time by doing a shift rather than a divide, you end up with code that isn't very readable. Somebody's going to be questioning why you're doing a shift rather than a divide. And the compiler probably would have generated better code than you are anyways. And it, your result depends on your type of variable signed, signed versus unsigned and sign extension can be your friend

or it can just shoot you in the foot. I wasn't suggesting you use it for multiply and divide but it is the effect of what you're doing so people should know

what it does. Absolutely. You, I believe it, so who wrote the part in about sign extension? Whoever that was put that in the outline

now has to talk about it. I don't remember. Was it me? Might have been. extension? Whoever put that in the outline now has to talk about it. I don't remember. Was it me? It might have been. I didn't put it in the outline. I didn't put it in the outline. I remember talking about it on Slack, but I wasn't. I might have done it.

I don't know. Well, so there's two different kinds of ships, logical and arithmetic, right? That's just the names of it. And it has to do with what... Wait a minute, but they're the same... Yeah. They're the exact of it. And it has to do with what... But they're the same... Yeah. They're the exact same key. Well, so in C, that's the same...

Yeah, you're still using the same characters, and the compiler, depending on your variable type, does a different type of shift. And the only difference there is when you have an unsigned number, when you shift to the right, it just shifts all the numbers to the right and brings in zeros on the left side. So the most significant bit becomes zero every time you shift to the right. With a signed number, if you have a negative value, you will have the most significant bit is going to be one.

And the right shift is going to copy that value over. So it's going to right shift a one and then another one, another one. It's going to keep the upper part of the number the same. And that's sign extension. So that when you think about it, this makes sense. If you divide negative four by two, you want negative two. And if you divide two by two, you want one, you don't want it to go negative. But the problem comes in when you don't realize that you are going to get sign extension. If you divide, you don't really care what number you have, you're just dividing by two and you want the results, but you don't want sign extension. One of the problems is we didn't really discuss signed binary numbers,

which is a giant podcast of its own, which we're not going to talk about. But the effect of representing a negative number in binary, remember I said about all that powers of two business, obviously there's no way just looking at that to say, oh, how do you do a negative number in binary. Remember I said about all that powers of two business. Obviously there's no way just looking at that to say, oh, how do you do a negative number? So there's various ways of representing negative numbers. The effect of which is usually, as Alvaro said, the high bit is set to one to signify that it's negative.

And that's why you have to tell your compiler whether you want a signed car or an unsigned car or a signed int or an unsigned int. But you don't have to do that for floats. Because floats are represented completely differently and you should never think about the binary part of floats. You should never use binary operations with floats. You should just... floats are magic.

Well, also the compiler is going to play pretty fast and loose with your types. So if you do like some complex math operation, you might end up with a signed value, even though you started out with a bunch of unsigned values because that's just the way that C works. So when you do your shift operations, you could end up with sign extension when you

really didn't expect it. That's why it always pays to be explicit about what you want the compiler to do. So cast if you need to. If you have any question about, oh, it always pays to be explicit about what you want the compiler to do. So cast if you need to. If you have any question about, oh, if I do this operation, is it going to turn my unsigned int into a signed or vice versa or this or that? Or is it going to promote my float or demote my float or whatever?

Just cast everything if you're confused. And parentheses everywhere. Just everywhere. Thousands of parentheses. Make it look like Lisp. I can send you an SD card with a whole bunch of them that you can use whenever you want. I know, I know. No, I can't.

No, you can send it electronically. It's so much cheaper. All right. Okay. So, I think we've got shifts down. So, shifts are really cool for making masks. And less cool for doing multiplication and division. Yeah.

Okay. So, having said that, I want to talk about circular buffers. And why it's so much nicer to have your circular buffer be a power of two. What's a circular buffer? Okay, so you have a buffer, and you're getting things from your serial board. And you want to be able to store what you haven't read and be able to put in new bytes that you haven't read. Oh my God, I should never have started this. Okay.

So you have, I don't know, 255 bytes. And so you can fill your circular buffer with 255 bytes. When you get to the end, it goes back to the beginning. On the idea that you've already read those beginning bytes, usually there are two pointers that show where you are putting stuff and where you are getting stuff out. Wow, this is really its own whole show. And the reason that powers of two are nice and circular buffers is because you can mask off however big they are and then count them up. Okay, so that didn't quite make sense. But let's say your circuit buffer is 255. And so you put stuff into position 0, and you put stuff into position 1,

and you put stuff into position 254, 255. And then you put stuff into 256, but you only have 8 bits. And so it flops over, and it becomes 0 again. You're talking about doing a modulo operation without any effort. Yes. Okay, so you're using an 8-bit value for your pointer, right? I'm using an 8-bit value for my index. Right.

But it doesn't have to be 255. We could have a 16-byte FIFO by masking off after the 16th position. And so that would be... Oh, so your index would be a 4-bit value. Yes. Clever. I don't really have a four-bit value on my compiler, so I just say and 0x0f. And that means only keep those four bits. Don't ignore whatever's in the top bits.

We don't care. So if it increments over to 16, then I mask it off and it jumps back down to zero. So you're saying that if you had a 32 element circular queue, you could use a five bit value the same way. You just have your mask being the bottom five bits rather than the bottom four. Right. That's clever. And this means you don't have to divide, and you don't have to do that if my buffer is greater than whatever my buffer size is, go to zero.

Although, this is a little on the clever side. At one time, I did this a lot because we didn't have the processing power and it just made so much more sense now i mean throw a few bites at it let it spend its time doing that these processors are really bored the battery backs to differ you do see this a lot with circular buffers. Compilers are smart enough to, instead of doing a divide, they'll do a single cycle multiply and use the appropriate overflow to make it look like a divide. So your masking might even be more costly than doing the division because you have to set up your mask, you have to do your and or operations and your nots, or you can just let the compiler figure it out.

It could be faster. It's certainly worth trying the easy and easy to read way first optimize later i agreed okay so that's circular buffers um chris you you mentioned graphics and i thought this was a good time to talk about x or because we only talked about it in the grocery store context um why do we care about x or it's one of the most underused nobody ever cares about poor xor i use xor all the time what does it do it's great for toggling things toggling what does toggling mean it means if it's a zero it's a one if it's a one it's a zero so if you come through a loop and you want to flip something on and off in order. Like an LED? You have your register with your bit or your status byte or your status variable.

And you just XOR it with itself. No. You XOR it with... Your mask? Your mask. And then it'll flip on and off. You mentioned graphics. There's kind of a famous thing in graphics.

When you want to draw a cursor or something or a sprite on screen, but you want to do it in an efficient way without a lot of extra storage. If you have the frame buffer, and the frame buffer stores what's on screen right now. Let's say you want to draw your mouse cursor. Depending on where you're drawing it, it might not be visible, right? If it's on a black screen and you have a black cursor, it won't be visible on the black sections,

and it won't be visible on, if you had a white cursor, it wouldn't be visible on the white sections. But if you XOR that image buffer with the frame buffer, then it will combine the two in such a way that it will always be visible. And then you can easily clear it by just applying it again and get back the original contents. There's actually a famous software patent has trotted out as an example of why software patents are terrible. Somebody patented this method of drawing a cursor on the screen. The story is that Amiga got in trouble for this.

I don't know that that's necessarily true, but that's the famous story. But yeah, for graphics, for drawing things, it's often a cheap and efficient way of putting something on screen that you want to clear later with the same operation. So when I think about XOR, I should be thinking about toggling and opposites. Well, or combining things in a way that you can reverse the operation later. Okay, okay, I like that. Alvaro, did you have anything to add to XOR? Yeah, I just use it for toggling things okay um let's see counting bits oh go ahead go ahead um this is something that i used on a fuel injection system at one point where you had to keep track of the number of teeth on a timing wheel.

Did they fall off? No, there's some missing. Sorry, sorry. No, it's a good question, though. Okay, I don't know how these things work. You have 60 teeth, but two of them are missing. So that way you, and they're missing at a particular, you can delete this out. No, no, no, I like it.

Oh, okay. The timing wheel that's attached to the crankshaft of the car typically has 60 teeth with two of them knocked out. And they have a sensor that goes along and it says tooth, tooth, tooth, tooth, tooth, tooth, tooth, tooth, tooth. And then it'll have missing teeth. And the processor will time out and say, wait a second, I've just noticed that there's two teeth missing. This must be top dead center. And you've got a good idea of the timing of the engine. So you know where top dead center is when all that you've got is this wheel with two teeth knocked out. You see this all the time if you look at flywheels on cars. So what happens is that in an interrupt routine, you end up having to flip between two values for counting teeth.

Let's say offhand, 17 and 42. So you're counting teeth, but you have to flip between these two numbers very quickly. So I found that what you can do is you can have the number of teeth, such as 17. And then every time you go through this interrupt, you exclusive or that value with 17, and then you exclusive or it with 42. And if you do the math, this is something for the students to do at home. If you just say value is equal to value, exclusive or it with 17, exclusive or it with 42, and you just keep on doing that operation, it will ping pong between the values 17 and 42, 17 and 42.

So the same way that you use it for flip-flopping bits, you can also flip-flop binary or decimal numbers. One thing I will add is it's used heavily in encryption. I know this is like totally different topic, but XORs are... And checksums, yeah. In part because of one of the things you said, Christopher, and that is, it is an operation you can invert, and yet you need to know what the value is that you want to invert. And so if you think about encryption or checks, I mean, you have some value, and then you want to do something to it, something secret, or something that you want to recover later, given some piece of information. XOR is one of those things that you can't just look at it and say,

oh, I'll try to multiply it by two, I'll try to multiply it by four, I'll try all these things and something will work. You kind of need to know what you started with. Yeah, I mean, if I XOR my document with a bunch of random numbers and only you know those random numbers, there's no way to get the data back unless you have those random numbers. It's also used in binary addition so that if you had two numbers that you want to add together. If you look at the, such as the lowest bits, if it's zero and zero and you add them together, you get a zero. If it's one and a one and you add them together,

you get a zero. But if it's a one and a zero or a zero and a one, basically when you're adding numbers together in binary, the addition operation is exclusive or. Wow. We should have started with that. Good graphics. And then your carry,

your carry gets added into the next digit and all that sort of stuff. Your carry is your and. Yes. Building, building adders is cool um not the snakes right that always confuses me uh but we we are we are over time already and still have a lot to go on so i'm just going to zoom through some some of this andre tell me about iso 646 ah because humans don't really grok this uh ampersand ampersand ampersand difference um the people who came up with uh the c99 standard came up with a new header file called ISO 646.h, which is named after the ISO 646 standard. What it does is give you words like and, and or, and not that you can use in your code rather than having to use ampersand, ampersand, and stick, stick, and tilde, tilde, and stuff like that.

So go to your local C compiler and include, so pound include, Angley bracket, ISO 646.h, Angley bracket. 646 dot H Angley bracket. Go into that file. See what's there. It's pretty cool. It's good to use. Cool. We never said that XOR was the caret above the six, but we should.

No, sorry. It's fine. And US keyboards, yes. What is it on your keyboard? Oh, I've just, I've had, I've used keyboards in German and Russian and Spanish and all the special characters from different places. It's really annoying. Probably not so much for them.

No, it's annoying to switch back and forth. Yes. Yes. Okay, so now finally we get to the book. The book. The book. The book. I don't have much to say about the book. Because it's impenetrable.

So, no. If you want to go deeper. Much deeper. Much deeper. The deepest you can possibly go. Marianna's trench deep. Into this. Clever, clever. There is a book. Clever, clever Much deeper. Much deeper. The deepest you can possibly go into this. Marianas Trench Deep. Clever, clever. There is a book.

Clever, clever, deeper. Yes, the extreme of clever. The kind of thing, if you're doing encryption, or you're doing checksums, and you're working on the inner parts of it, or you're trying to optimize things to the furthest extent of the law. There is a book by Henry S. Warren Jr. And it's called Hacker's Delight. And it covers topics such as basics, just like this.

But unfortunately it moves past us in about six words. Counting. We didn't talk about how to count bits efficiently. Like how do I know how many bits are set in a particular long word of string of binary? Which you could totally do with a for loop. But there are some efficient ways to do it that involve

anding like F0, F0, or AQ. Magic numbers. Rearranging bits. Multiplication. Reversing bits. That's often an interview question. Can you reverse the bits in a byte? Gray code, Hilbert's curve,

which is a thing that I think comes up in encryption and other things. Floating point talks about all this stuff. So anything you want to do with numbers and bits, this is the book that you should read and then promptly never do anything it says. Yes, think carefully about using this in your code i have used things like this in my code judiciously when trying to be very very efficient so for example if you're doing if you're doing like a bit counting thing

on millions and millions and millions of of elements in an array or graphics, for example, sometimes being clever is required because you don't want to do a for loop millions and millions of times. And doing this is better than going to assembly and tuning it there because the tricks you can get if you're going to do bit manipulation on this level are more efficient than the for loop you'd get if you're going to do bit manipulation on this level are more efficient than the for loop you'd get in assembly.

However, it is wrong. So wrong. It's not wrong. There's lots of great stuff in here, especially discussion of parity and things that are just concepts that are important. And some of them, some of the

tricks and things, while they appear clever initially, it requires you to think about them for maybe a minute or two. And sometimes that's worth it, especially if you put in a comment that says, hey, I got this from Hackers Delight, here's how it works. Here's why I'm using it and why I didn't use the simpler, more obvious approach. And there's a second edition. You're holding the first edition. Yeah. I don't think the second edition has a lot more text to it, but apparently there are new ways to manipulate bits. It says in the last bullet, even formulas for prime numbers, exclamation point.

Even formulas for prime numbers. But if you don't like this book, there's another book by Stephen Frank, which is just an e-book. It's called How to Count. And you can find that on his website, stephenf.com. And that goes through all the stuff we talked about. Well, not all of it, but the very basic things we talked about in an accessible way. So, those are books somebody on our blog wrote something who's that guy oh crap i wrote this what oh no no andre wrote this oh good what who didn't write it oh

x or who wrote it. Who did write it. My goodness! I've written an article on logic in C and all this binary representation and ands and ors and nots and exclusive ors and all that sort of stuff. So we'll put a link down in the doobly-doo and you can read about this and see what we're talking about with truth tables. Yeah, and Andrea goes through binary and hex and it's really nice. So if this show interested you and you want to know more and you want to get a little deeper in, definitely check that out. And it will be in the show notes. And for people who do this every day, people who do this every day,

back in about 1985, I picked up a calculator made by Hewlett-Packard called an HP-16C that got deleted back in the 80s as well. But wait, there's a company called Swiss Micros that has a remake of the HP-16C, and they call it the DM-16L. So it does hex and decimal and octal and binary, and it does all the shifts and masks and all that sort of stuff. And I bought myself one, and it's got my seal of approval. This thing's actually pretty good.

Okay. Alvaro, any tools you like to use? You mentioned some calculators on the computer. I use the Windows, Mac, and Linux. They all have the calculator program. So those are, yeah, those are great. They all have an engineering or programming, programmer mode, I think.

Yeah. Yeah. And for people new to binary, you can hear how we all struggled with this. This isn't obvious. And when you walk up to code and you see ands and the ors and the nots and the pound F zero F six two, it is impenetrable until you start taking it down

to the bit level, which is why binary is so important. It isn't something you know right away. And even if you learned it in school, until you start using it regularly, these things are all pretty opaque. And yet once you start using it regularly, it just becomes habit. And you forget people don't look at that and think, oh, they're setting a bit in a register. That's one of the reasons we have all of these libraries that do it for us. But sometimes they're so big that you just want to be able to manipulate the register directly. So, you know, for the newbies, don't get scared. And for the people who've been around for a while, don't forget that it used to be scary.

I guess that's my final thought. Chris, do you want to have one? One. Alvaro, would you like to have a final thought? No final thoughts for me. Bits are awesome. Keep shifting. Andrew, what about you?

I'd say go out and listen to some live music you enjoy it go do it for real all right our guests have been alvaro prieto co-host of the unnamed reverse engineering podcast they're gonna name that soon no they're never gonna never going to name it. Nope. And Andre Chichak of the Great White North, keeper of the snow and maple syrup. Defender of the wall. Thank you both very much for speaking with us. Sorry, I think that was Ron's reference for something I don't even watch. Thank you, Chichak.

If you said it for me, that would have been a little different. Yes. Don't go there. Thank you to Christopher for co-hosting and producing, and thank you for listening. Usually this is the spot where I thank Patreon supporters for mics, but I didn't have to send out any mics, and they already got their thanks this week. I finally got it together and made a slack channel so if you need another reason to support one of your favorite podcasts now if you support us on patreon you can join our slack channel which is full of

interesting conversations that we may or may not participate in so don't expect us to be around all the time. I'm actually there. I'm just not paying any attention, which is the same as all my Slack channels. And now a final thought to leave you with. This one from Desmond Tutu. Do your little bit of good where you are.

It's those little bits of good put together that overwhelm the world. Embedded is an independently produced radio show that focuses on the many aspects of engineering. It is a production of Logical Elegance, an embedded software consulting company in California. If there are advertisements in the show, we did not put them there and do not receive money from them. At this time, our sponsors are Logical Elegance and listeners like you.