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
把1 8 3相加 结果是12
adding a 1, an 8, and a 3,and that
gives us 12 so we got a two down here that hits
然后把6 5 1相加
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
two 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,
现在再加上1 0 1 会再次达到限制
now we’re going to add again a 1, a 0, and a 1. That’s going again hit our limit of
在这记一个0 进位1 现在1和1相加
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.
再次达到限制 就在这记一个0 进位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 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 0010010
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 bunchof 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 you add to 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 123’s non sign bits,
so these bits over here, to get 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 right.
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 mask 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 and 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.