# Binary Arithmetic

You can’t really “do” computer science without understanding your basic base 2 numbering system.

## Conversion

Converting a binary number (base 2) to a decimal number (base 10) is pretty straight forward if you know your powers of 2:

 Power of 2 $2^7$ $2^6$ $2^5$ $2^4$ $2^3$ $2^2$ $2^1$ $2^0$ Decimal Place Value 128 64 32 16 8 4 2 1 Binary Numeral 1 0 0 1 1 1 0 1

Decimal Value: $128 + 16 + 8 + 4 + 1 = 157$

## Binary Operations

### Binary AND

Binary AND operations work the same way as Boolean AND operations (duh). It combines two binary numbers, 1 bit at a time, AND’ing each bit. A 1 is treated as “True” in Boolean and 0 as False. So anytime there is a 0 in an AND operation the result is always 0. Only 1 $\land$ 1 = 1.

AND’ing anything with a string of 1’s will always be the original binary number:

 110100 $\land$ 111111 $=$ 110100

AND’ing anything with a string of 0’s will always result in a string of 0’s (set to null):

 110100 $\land$ 000000 $=$ 000000

### Binary OR

Binary OR operatios also act the same as Boolean OR operations (doi). It acts the opposite of AND: Anytime there is a 1 in an OR operation the result is 1. Only 0 $\lor$ 0 = 0.

OR’ing anything with a string of 1’s will always be a string of 1’s:

 110100 $\lor$ 111111 $=$ 111111

OR’ing anything with a string of 0’s will always be the original binary number:

 110100 $\lor$ 000000 $=$ 110100

### Binary XOR

XOR is far more interesting than AND and OR. It only returns 1 if there is a 1 in one of the two operators and not in the other. So if the two bits do not match a 1 is returned and if they do, then a 0 is returned.

XOR’ing anything with a string of 1’s will flip all the bits:

 110100 $\oplus$ 111111 $=$ 001011

XOR’ing anything with a string of 0’s will always be the original binary number:

 110100 $\oplus$ 000000 $=$ 110100

One other interesting characteristic of XOR is that it is reversible. So if you take the result of the first XOR and XOR it with the second number in the original operation, you will get the first number:

 001011 $\oplus$ 111111 $=$ 110100

Note:
Bit-level XOR produces exactly the same results as doing addition mod 2:
$( a + b )$ mod $2 = a \oplus b$

### Arithmetic Shift

A left or right shift is a bitwise operation that shifts all the bits in a binary number over however many positions. In order to preserve signedness, the leftmost bit (the sign bit) is replicated rather than being filled with 0’s when doing a left shift. A right shift will just fill in 0’s.

Shifting left by n bits on a signed or unsigned binary number has the effect of multiplying it by $2^n$. Shifting right by n bits on a two’s complement signed binary number has the effect of dividing it by $2^n$, but it always rounds down (towards negative infinity).

### Bitwise Rotation

A bitwise rotation, also known as a circular shift, either moves the first bit to the last position, shifting all other bits up a position or vice versa. It does not preserve the signedness of the binary number.