Wednesday, January 27, 2016

Binary Subtraction and Two's Complement

A while ago, I talked about how to use Boolean algebra to add two binary numbers. Now I'm going to show you how you can do subtraction in a similar way.

To start with, I'm going to ignore negative numbers. I'll get to those later, but for now, for simplicity's sake, I'm going to assume the first number will always be larger than the second, so the answer will always be positive.

Let's start again with 1-bit numbers. 1-1=0, 1-0=1, 0-0=0, so we have this truth table:

XYZ
000
01?
101
110

The question mark is to denote a value that can be either 1 or 0. We don't care about that particular value, because it would be negative. Because of that value, there are two functions that satisfy this truth table: X XOR Y, and X AND ¬Y.

Extending this to multiple digits is similar to extending addition to multiple bits, but instead of sometimes needing to carry, we'll sometimes need to borrow. The difference between carrying and borrowing is that instead of adding one to the next digit to the left, you subtract one from the next digit to the left, and you borrow in cases where the result would be less than 0, instead of greater than 1.

XYBN-1ZBN
00000
00111
01011
01101
10010
10100
11000
11111


BN-1 indicates whether a borrow was required for the digit to the right of the current one, and BN indicates whether the current digit requires a borrow. For the rightmost digit, BN-1 is 0.

So, Z = X XOR Y XOR BN-1, and BN = (¬X AND Y) OR (¬X AND BN-1) OR (Y AND BN-1)

Now, what about negative numbers? For that matter, how do we even represent negative numbers? Computers only have 1 and 0, there's no -.

Well, there are a number of ways you could do that. You could for example designate one bit to be a sign bit, where one value indicates positive, and the other negative. Normally, the sign bit is the leftmost digit, and normally 0 indicates positive. So, 0101 would be 5, while 1101 would be -5.

This particular method has the disadvantage of wasting a number, because 000 and 100 represent 0 and -0, which are equal. It also requires different algorithms for adding and subtracting negative numbers.

Wouldn't it be nice if there were a representation of negative numbers that allowed the use of the same algorithms for both positive and negative numbers? Well, there is one, it's called two's complement.

It's not very intuitive, but it's very convenient for doing these bitwise functions. Like the method I just described, the leftmost digit is a sign bit, and 0 represents positive. But instead of the rest of the bits being the same as the positive representation, you flip all the bits, and then add 1.

0101 would still be 5. To get the bits for -5, first start by replacing every 1 with a 0, and every 0 with a 1, so we get 1010. Then add 1, so we get 1011. If the rightmost digit is 1, it carries the way you would expect, so -3 ⇒ 0100 ⇒ 1011 ⇒ 1100.

Notice what happens when you try to represent -0 like before. 0000 ⇒ 1111 ⇒ 0000. So, there's only one possible representation of 0. 1000 would represent -8. In general, with N bits, the highest number you can represent is 2N-1-1, and the lowest is -2N-1

When you use two's complement, you can use exactly the same algorithm I described above to subtract with both positive and negative numbers. You can also add using the same algorithm I described in my previous post.

Friday, September 25, 2015

Very Unique

Some people object to using a modifier like "very" or "a little" with the adjective "unique". They say that "unique" means "one of a kind", and that is a strict binary.

Well, they're wrong. "Unique" is not a strict binary. As with most other things, it's a continuum, and things can be more or less unique.

For example, consider the Wright brothers. They built bicycles. At first, their bicycles we made using the same designs as any other bicycle. It would be safe to say they weren't unique. But the Wright brothers were inventive fellows, and they came up with ways to improve the design of their bicycles. At that point, their bicycles were unique. There were no other bicycles like them. Then they built an even more unique machine. A machine that did something no previous machine had done. The bicycles were unique, but they were still bicycles. The airplane was a whole new thing.

Another example. Consider two books. One is full of old tropes and tired clich├ęs. Utterly predictable, but not plagiarized. It's not unique in that it mimics other books, but it is unique in that it consists of a sequence of words that had never been written before. The other book is more original. It's unique in that no other book has a similar plot, but it's not unique in that it still consists of words printed on paper. The latter book is more unique than the first.

There are many ways something can be one of kind, and the more ways that apply, the more unique a thing is.

Friday, September 18, 2015

The Sun of God

Do you believe in the sun? Do you think that the sun exists?

I certainly do. I've never doubted the sun's existence, even when it was out of sight. And I don't think anyone else has either. Certainly, I've never heard of anyone who claimed that the sun doesn't exist. Even solipsists, I'd be willing to bet, would admit that they perceive the sun, even if they deny that their perceptions are indicative of reality.

People even agree on details about the sun, even when those details change, and vary from place to place. Someone in China will say the sun is up at the same time someone in America will say the sun is down, but both will agree that the other is correct for their location.

Why are people in such unanimous agreement about the sun? Is a supernatural entity using telepathy to mind-control us? No, the reason we agree about it, is because we can see it. The evidence for its existence is right there, clear as day.

Some people say that the evidence for god is clear and obvious, but it's clearly not as obvious as the evidence for the sun. If it were, there wouldn't be such disparate religions. Christians, Muslims, Hindus, Buddhists... People can't even agree on whether god exists, let alone specific details about him.

Some people say that god wants us to believe in him. But surely an omnipotent would be capable of performing a feat that an inanimate object has managed. If god wants us to believe in him, he must not want it very much.

Thursday, June 4, 2015

Ultron

Note: This post contains spoilers of Avengers 2: Age of Ultron.

I liked Avengers 2: Age of Ultron, but as tends to happen with Marvel villains, Ultron's motivation is unclear. Why does he interpret his mission of "peace in our time" as "kill everyone"? Why does he hate Tony Stark so much? I have two ideas about this.

The first idea is that Tony didn't actually create Ultron. He simply downloaded the consciousness of the mind stone into a computer. As evidence of this, when Ultron is first activated, one of the first things he asks Jarvis is "Where is your body?", and upon learning that he's a machine, says "This feels weird. This feels wrong.".

Under this interpretation, the reason he hates Tony so much is because Tony is the one who put him into a machine. He hates Tony more than Bruce Banner, because it was Tony's idea. As for the mission, he never cared about peace. He just said that to confuse and make fun of the Avengers.

The second idea is that Tony did actually create Ultron, and Ultron was performing his mission. He saw that humans are a divisive and warlike species. He realized that we would never accept an externally imposed order. But that we might unite to fight a common enemy. And that plan worked, at least as far as getting the Maximoffs to put aside their differences with the rest of the Avengers.

In this case Ultron hating Tony was the lie. Ultron figured that Tony, having created him, would be less willing to fight him. So he made sure Tony would think he he hated him, so Tony would hate him back.

Monday, May 11, 2015

Redefining Marriage

Conservatives like to complain that allowing same-sex couples to get married is redefining marriage. The most common response to this is to argue that redefining marriage isn't necessarily bad, and to point out the many times marriage has been redefined in the past. However, I think the argument can be refuted on another level: Gay marriage is not a redefinition of marriage.

Or rather, the redefinition of marriage which logically leads to gay marriage already happened, and it happened a while ago. The change happened gradually, over a long time. There wasn't a single landmark court case I can point to like Loving v. Virginia.

A long time ago, a woman was considered to be basically the property of her husband. Even after that was the case, a woman was still supposed to be subservient to her husband. He had authority over her.

But over time that changed. Eventually, a marriage was no longer a relationship between owner and property, or between superior and inferior. It became a relationship between equal and equal. And once that happened, there was no longer a masculine role and a feminine role, and thus no need for a man and a woman. Just two people.

Tuesday, December 9, 2014

Quis custodiet ipsos custodes?

There have been a lot of stories recently about police abuses of power. Undoubtedly, these stories are not representative. The vast majority of police-civilian interactions do not end with death or violence. Most cops are good cops.

But that doesn't matter, when the whole system is bad.

When a police officer can kill someone with no provocation, on camera, and get away with it, it doesn't matter that there are more good cops than bad cops, because the good cops are part of a system that does nothing to stop the bad cops.

And it's not just the major abuses like that. I've heard (not being a cop, I don't know for sure) that police officers will usually not give other officers tickets for traffic violations. Of course, that's a very minor thing, but it's indicative of the problem. Police officers are held to a lower standard of conduct than civilians.

"With great power comes great responsibility." Unless you're a cop.

Monday, November 24, 2014

Binary Addition

Before, I talked about how to use binary to represent a number using only two values. But what if you want to actually do something with those numbers? How do you add numbers using Boolean operations?

Well, let's start with a simple case: adding two one-bit numbers. We'll call them X and Y, and since they each only have one binary digit they can only have the values 0 or 1. So here are the cases we need to account for: 0+0=0, 0+1=1, 1+0=1, 1+1=10.

Notice the answer for that final case has two digits. A Boolean function can only return one value, so how can get that? By having two functions, one for each digit.

So, the function for the rightmost digit has to satisfy this truth table:
XYZ0
000
011
101
110
What Boolean operation does that look like? XOR.

The function for the next digit will have to satisfy this truth table:
XYZ1
000
010
100
111
That's the same as the AND operation.

I'm using the subscripts here to indicate which digit in the overall number. So our two bit answer Z has the individual bits Z1Z0, where Z1 = X AND Y, and Z0 = X XOR Y;

So, that's how you can add two one-bit numbers. But what if you want to add bigger numbers? Well, the way you add the second bits together is pretty much the same as the first bits, with one major difference: You need to account for the bit that got carried from the sum of the first bits. If that carry bit was 0, then the result of the next bit will be same as the first. But if it's one, then the result is increased by one. So, 0+0+1=1, 0+1+1=10, 1+0+1=10, 1+1+1=11.
So, now we have these two truth tables:
X1Y1CZ1
0000
0101
1001
1100
0011
0110
1010
1111
X1Y1CZ2
0000
0100
1000
1101
0010
0111
1011
1111
So, Z1 = X1 XOR Y1 XOR C and Z2 = (X1 AND Y1) OR (X1 AND C) OR (Y1 AND C). C, the carry bit, comes from the second bit of the result of the sum of the first two bits, that is C = X0 AND Y0.

Each subsequent bit works just like the second, with the second bit of the previous result being carried over. Generally, and Zn = (Xn AND Yn) OR (Xn AND Cn-1) OR (Yn AND Cn-1), and Cn = Xn XOR Yn XOR Cn-1.

Here's another challenge for you: How do you do subtraction in a similar manner?