Hi, I'm Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today we're going to talk about bits. So we're going to talk
about how positive and negative numbers are represented in binary. We're going to talk
about operations like shifting and arithmetic including the logical and the
arithmetic shift. And then I'm going to talk about how we can use masks to do
operations like clearing, setting, and getting bits. Now there's a little bit of
cross dependency in these topics so the order might seem a little bit funny to
be jumping back and forth but it'll be a little better this way. So let's relate
this to base 10 numbers. What does a number like 583 mean? What do those digits represent? Well it's five times ten to the second, plus 8
times 10 to the first, plus 3 times 10 to the 0th. In base 2 or binary we can do the
exact same thing. Now let's talk about adding. Well in
base-10 we add up the two digits and if it hits our limit then we roll that over
to the next digit so we added 3 and the 7, that gets ten, that hits our limit of
ten, so we roll that one over and now we're adding a 1, an 8, and a 3, and that gives us
12 so we got a two down here that hits our limit of 10 so we roll that over up
here, and then we're adding a 6, a 5 and a 1, and that again hits our
limit of 10 per digit, so we go down that too and we carry the 1 over and we get
1220. So we can do that exact same thing in binary. In binary of course our limit
of each digit is just 2, so we're going to add this 1 and this 1, and that's
going to hit our limit of two so we're going to record a 0 over here, carry the one, now we're going to add again a 1, a 0, and
a 1. That's going again hit our limit of 2 so I'm going to record a 0 there, carry the 1
over and now we're going to add a 1 and a 1. Again we're hitting this limit of two so
we're going to record a 0 here and carry the 1 over and we get 1000. So that's
again how you do binary addition. It's very very parallel to what you do in
base-10. Now let's talk about how we represent negative numbers on a computer. Typically a negative integer is
stored in two's complement form and what this means is that the very first bit is
used to represent this sign. A 0 means it's it's a positive number and a one means
it's negative. Then the remaining bits over here are filled in with the two's
complement, the number that you'd have to add to these, to the positive version, to
the absolute value to get 2 to the 8th in this case. We use 8 because
it's an 8-bit number. So let's think about this. What number would we have to add to 00 100 10 to get 1 000 000 0. Well if we just added the inverse of 0 0 100 10 to it
then we would get 0 with a whole bunch of ones afterwards. Therefore if we add 1 up here and a 1
down here we should get the values we're looking for. So remember that our original question
was how do we represent negative 18 in binary? Well we take the positive value of that, the
18 and we look at this binary representation and then we say what
number can we add to that to get one followed by whole bunch of zeros? Well the number we add to it to get all
one's is just invert all the numbers so if we add 1 to a bunch of the, to both of
those, then we have 110 1110 so therefore the two's complement, the number
that you add to this series of bits here is in fact that number so our
representation is this right here. So that's how you represent negative 18 in
binary. So just to make sure you understand that. Let's look at one more
example. So if we want to convert negative 123 to
binary we'd be looking for the thing that we add to 123s non sign bits, so
these bits over here, to get 2 to the 8th. So we'd take 123, convert it to binary, so
we get that then invert all of the bits, and then we add 1 to that. And that will give us our two's
complement version of negative 123. The next topic I want to talk about is
shifting. Specifically two types of shifting, logical shifting and arithmetic
shifting. So let's consider some number in binary like this. So if we want to
left shift then we just move everything over by one to the left and if we want to right
shift, move everything over by one to the righ. Now we've been talking about these
in binary so much we forgot what these numbers actually are in base-10.
Interestingly that top number is 23 and this left shift number is 46 and the
right shift number is 11. Now what do you notice about those
numbers? Well the left shift had the effect of multiplying that number by 2 and the right shift had the effect of dividing it by two. Of course with some truncation
in there, and that's not a coincidence. That's what a left shift a right shift
generally do. Now some of you might be wondering what happens on a negative
number to this sign bit if we're doing a right shift? Does it shift with the
number or not? And that's an interesting question. And that's where you get into
logical vs arithmetic right shifts. So let's consider the number negative 23. In
a logical right shift we do what we would logically think that a right shift would
do, we move everything including the sign bit over. This gets us this weird value
of 116 which doesn't really seem to have any particular relationship to the number
negative 23. The arithmetic right shift operates slightly differently but in
doing so preserves an arithmetic relationship between the original number
and the new right shifted number. What the arithmetic right shift does is it shifts
everything over by one including the sign bit but then it fills in the sign
bit with the original sign bit instead of with a 0 as in the logical right shift. The
resulting number is negative 12 which does still bear that sort of, that divide by 2
relationship, except that with negative 23 dividing by 2 is negative 11.5 so we're rounding to
negative 12 this time. So now we're on to our final topic - using masks to do things
like getting a bit, updating it, things like that. First let's review some of the basics. When we and two bits we get a 1 only if both of
those bits are 1. When we or two bits we get a 1 if either of those two bits
are 1. And when we do an XOR we need exactly one of those two bits to be a 1. If
both are ones we get a zero. So now let's turn to how you would get a particular
bit and a number. So how do we figure out if say this bit was a one or a zero? Well
if we create a mask or just a number that has a 1 only in that one bit and
we and it with the original number that will indicate whether that value is a
one or a zero because if there's a zero there the whole number will be 0.
Otherwise it'll be something bigger than 0, so that mass can be created by taking
one and shifting it over to the left by i spots. So to figure out if the ith spot
is a one or a zero we just compare X, do an and of X with that mask and say does that
not equal 0? Now what about setting the ith bit? Well
we can do a very similar thing. We create actually exact, the exact same mask and
we just or it with that original value. And that will make sure that ith bit is
set. Now what about clearing the ith bit? Well that's a little bit trickier but
still very doable. What we want to do is end it with a mask
that has a 1 everywhere else but that one spot. But how do we create such a
mask? Well all we have to do actually is just take
the mask from before and invert it and that's exactly what you see here. So
we've now covered the basics of bit manipulation. We talked about how numbers
are represented both in positive and negative form, and then we talked about
different operations like, how we add numbers comparing that to base 10
numbers. We talked about shifting both logical and arithmetic and then we
talked about how to do getting, setting, and clearing using masks. So from
candidates there's a lot of focus on learning different bit manipulation
tricks and things like that. What I really encourage people to do is just really
solidify their understanding of the basics and from there a lot of these
tricks and things like that will follow, but really nail that foundation of the basics. So now that
you've seen these basic operations why don't you try your hand at a new bit
manipulation problem. Good luck.
