Analogy of Binary subtraction to decimal subtraction [duplicate]

This is a very basic question. But I come from non computer science background and is having trouble understanding this . Lets say I want to subtract two binary numbers (say 100 - 001 = 011). How do I go about doing this subtraction ? Please provide an analogy for a decimal subtraction

P.S: Actually I found out that the HashMap in Java requires its bucket size to be a power of 2 and finds the bucketIndex by the following code and this works well if n is a power of 2 . h is the value of the key to be hashed and length is number of buckets in the HashMap

static int indexFor(int h, int length) {
return h & (length-1);
}


So I am assuming that that n here is 4 . So lets say we do 4-1 =3 which is 011 in binary .I am getting confused with borrowing operation here for the 2's place and 4's place during the subtraction process.

-

marked as duplicate by MJD, sdcvvc, William, tomasz, t.b.Sep 10 '12 at 21:58

You go for that subtraction exactly as you would do for decimal, except that you need to borrow already for $2=$10. So for your example, you have

  100
- 001
<- place for borrows
___


So you start in the rightmost column, where you have $0-1$. Since $0<1$, you have to borrow from the left, so you have 10-1 that is $2-1$ which is $1$. So after this step, you end up with

  100
- 001
1
___
1


Now to the second solumn. Again, including the borrow, you have to subtract $1$ from $0$, so you need to borrow again. Again, you'll get 10-1$=2-1=1$:

  100
- 001
11
___
11


Finally, with the left column, you have $1-1$, which doesn't need a borrow and gives $0$. So you end up with

  100
- 001
11
___
011


Which evidently is the correct result.

However it may be easier to first only collect the borrows and then subtract them in a separate step (continuing until no borrows are left). Note that this could be done in decimal subtraction as well. With that algorithm you collect the borrows below the preliminary result, and then restart the subtraction algorithm. This is especially useful for problems like 100-011 where the borrow gets larger than $1$. Here's how that method works:

  100
- 011
___
<- Preliminaty result
0  <- Borrows (initialized with a rightmost 0)


First, subtract the right-most column. This needs a borrow, which this time is noted below.

  100
- 011
___
1
10


Now we get to the second column. With the previous algorithm, you'd have to subtract $10$=2$, which is of course possibile with borrow, but you need to think a little bit more (which is especially bad if you are a computer and thus quite stupid). With this second algorithm, you just ignre the borrow for the moment, and subtract the second column normally (which again gives a borrow).  100 - 011 ___ 11 110  Finally you subtract the leftmost column, which works without a borrow:  100 - 011 ___ 111 110  Now the borrows are not empty, therefore you have to subtract them. Fortunately you know how to do that:  100 - 011 ___ 111 - 110 ___ 001  Voila, the correct result! OK, so why is this algorithm better? Well, because you never get a borrow larger than$1$, and since computers are especially good with$0$and$1$, this is better suited for them. Moreover, if you look at the preliminary results, you'll find that each bit is 1 exactly if the original bits are different; that operation is known as XOR and is a basic logic operation which can be easily implemented on computers. Also, it is easy to see that the borrow now occurs exactly when the bit of the first number is 0 and the bit of the second number is 1. Which is also a combination of two basic logical operations, NOT and AND. Also note that the XOR is also valid for addition, only the borrow has to be changed to a carry. A carry happens exactly if both bits are 1. So basically the only difference between binary addition and binary subtraction is a NOT on the first number when calculating the borrow instead of the carry. - so in step 1 I am borrowing a 2 from the 2'splace of the upper number right ? Also "except that you need to borrow already for 2=10" . What does this mean ? – Geek Aug 22 '12 at 13:22 Yes, that's right. And if you look closely, I've written$2$in math mode, and 10 in code mode. What I mean is the number$2\$, written in binary as 10. – celtschk Aug 22 '12 at 13:42