Difference between revisions of "Bitwise math"

Latest revision as of 06:47, 18 November 2012

Bitwise math is the foundation of all binary math and most mathematic operations performed in assembly. Many of the bitwise mathematics primitive operators can be found in a variety of compiled languages and interpreted languages as well.

Language specific information can be found for Perl, Python, and Ruby

Introduction to Binary

Binary math and hexadecimal math have slight differences to decimal math but the same principles apply. For example, in the decimal number 1234, the ‘4’ is in the “ones” placeholder, the ‘3’ is in the “tens” placeholder, the ‘2’ in the “hundreds” placeholder and the ‘1’ in the “thousands” placeholder.

Example 1: Decimal number 1234

Example 1: Decimal number 1234
Thousands (1x10^3)	Hundreds (1x10^2)	Tens (1x10^1)	Ones (1x10^0)
1	2	3	4

Binary operates a little bit differently, instead of having 1’s, 10’s, 100’s, etc, it has 1’s, 2’s, 4’s, 8’s, etc (That is to say, decimal math operates on a base of 10, while binary math operates on a base of 2). So analysing this for a moment, the binary number 1010, has a ‘1’ in the “eights” placeholder and a ‘1’ in the “twos” placeholder. Add these together and 10 is obtained in decimal numbers.

Example 2: Binary number 1010 = 8+2 = Decimal number 10
Eights (1x2^3)	Fours (1x2^2)	Twos (1x2^1)	Ones (1x2^0)
1	0	1	0

Another example is 1111:

Example 3: Binary number 1111 = 8+4+2+1 = Decimal number 15
Eights (1x2^3)	Fours (1x2^2)	Twos (1x2^1)	Ones (1x2^0)
1	1	1	1

Detailed Example
	Eights (1x2^3)	Fours (1x2^2)	Twos (1x2^1)	Ones (1x2^0)
Binary Values	1	1	1	1
Decimal Values	8	4	2	1

Through the use of the binary table, the binary values can each be multiplied (1’s) by the above multipliers (1x2^3 1x2^2 1x2^1 1x2^0) or “8, 4, 2, 1”. This will then give us, 8+4+2+1=15.

Basic Addition

Much like the decimal system, binary numbers can be added together. For this example the binary numbers 0110 and 0010 are going to be used and added.

	Eights	Fours	Twos	Ones	Total
Binary	0	1	1	0	6
Decimal	0	4	2	0	6

	Eights	Fours	Twos	Ones	Total
Binary	0	0	1	0	2
Decimal	0	0	2	0	2

Thus by using decimal addition, 4+2+2=8, the value of the addition of two binary numbers can be determined as 8.

Binary to Hexadecimal

The past exercises have featured working with 4 bits at once (4 values ranging from 0-1, e.g. 0001). This is known as a nybble in hexadecimal. A byte is made of two nybbles (8 bits make a byte).

In hexadecimal, there is a 1’s placeholder and a 16’s placeholder. Hexadecimal is 0 through 9 and A through F. A nybble can hold 16 unique values but the highest value is 15 because one of the values is 0. A nybble is a single hex digit. So, A = 10, B = 11, so on and so forth, F = 15.

In hex, AF is obtained as a byte.

AF = 175 in decimal because A is in the 16’s placeholder

A = 10, 10*16=160,

Plus F which is in the 1’s placeholder,

F = 15, 15*1=15

Therefore 160(A)+15(F) = 175.

NOT, AND, OR and XOR

Note: all examples in this section will be using hexadecimal and binary.

NOT

NOT is a bitwise operator that takes only ONE operand. It inverts or reverses the binary value.

Example:

 A = 1010 in binary or 10 in decimal. NOT A results in the inversion of 1010 which is 0101. Therefore NOT A = 5.

AND

AND returns “TRUE” per true bit in both of the required two operands. True is 1 and false is 0. It operates bit by bit, just like NOT.

AND rules

AND compares each bit and if both bits per placeholder are true, then it returns a true for that placeholder, all else gets turned into 0.

1 and 1 = 1
1 and 0 = 0
0 and 0 = 0

AND properties

anything AND'd by itself results in itself
anything AND'd with 0xF results in itself
anything AND'd with 0x0 results in 0x0

AND example

Example: 0x6 AND 0x5 = 0x4

Operation	Hexadecimal	Binary	comment
and	6 5	0110 0101	The second and third bits are true. The second and fourth bits are true.
=	4	0100	The second bit is the only one true in both instances (5 and 6).

AND logic table

AND	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1
2	0	2	2	0	0	2	2	0	0	2	2	0	0	2	2
3	1	2	3	0	1	2	3	0	1	2	3	0	1	2	3
4	0	0	0	4	4	4	4	0	0	0	0	4	4	4	4
5	1	0	1	4	5	4	5	0	1	0	1	4	5	4	5
6	0	2	2	4	4	6	6	0	0	2	2	4	4	6	6
7	1	2	3	4	5	6	7	0	1	2	3	4	5	6	7
8	0	0	0	0	0	0	0	8	8	8	8	8	8	8	8
9	1	0	1	0	1	0	1	8	9	8	9	8	9	8	9
A	0	2	2	0	0	2	2	8	8	A	A	8	8	A	A
B	1	2	3	0	1	2	3	8	9	A	B	8	9	A	B
C	0	0	0	4	4	4	4	8	8	8	8	C	C	C	C
D	1	0	1	4	5	4	5	8	9	8	9	C	D	C	D
E	0	2	2	4	4	6	6	8	8	A	A	C	C	E	E
F	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F

OR

OR will return true bits for the respective placeholder if any of the bits are true.

OR rules

OR determines if any bits are true from the given binary operands

1 or 1 = 1
1 or 0 = 1
0 or 0 = 0

OR properties

Anything OR'd with itself results in itself
Anything OR'd with 0xF results in 0xF
Anything OR'd with 0x0 results in itself

OR example

Example: 5 OR C = D

Operation	Hexadecimal	Binary	comment
or	5 C	0101 1100	The second and fourth bits are true. The first and second bits are true.
=	D	1101	The first, second and fourth bits are true in at least one instance.

OR logic table

OR	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	1	1	3	3	5	5	7	7	9	9	B	B	D	D	F	F
2	2	3	2	3	6	7	6	7	A	B	A	B	E	F	E	F
3	3	3	3	3	7	7	7	7	B	B	B	B	F	F	F	F
4	4	5	6	7	4	5	6	7	C	D	E	F	C	D	E	F
5	5	5	7	7	5	5	7	7	D	D	F	F	D	D	F	F
6	6	7	6	7	6	7	6	7	E	F	E	F	E	F	E	F
7	7	7	7	7	7	7	7	7	F	F	F	F	F	F	F	F
8	8	9	A	B	C	D	E	F	8	9	A	B	C	D	E	F
9	9	9	B	B	D	D	F	F	9	9	B	B	D	D	F	F
A	A	B	A	B	E	F	E	F	A	B	A	B	E	F	E	F
B	B	B	B	B	F	F	F	F	B	B	B	B	F	F	F	F
C	C	D	E	F	C	D	E	F	C	D	E	F	C	D	E	F
D	D	D	F	F	D	D	F	F	D	D	F	F	D	D	F	F
E	E	F	E	F	E	F	E	F	E	F	E	F	E	F	E	F
F	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F	F

XOR

XOR is a bitwise comparison operator that returns a true bit if the compared bits in question are different. If they are the same, it returns a false bit.

XOR rules

XOR determines which bits differ in the two binary numbers used as operands.

1 xor 1 = 0
1 xor 0 = 1
0 xor 0 = 0

XOR properties

Anything xor'd with itself results in 0
Anything xor'd with 0xF is the same as a "not"
Anything xor'd with zero results in itself

XOR example

Example: A xor F = 5

Operation	Hexadecimal	Binary	comment
xor	A F	1010 1111	The first and third bits are true. The first, second, third, and fourth bits are true.
=	5	0101	The second and fourth bits are true in ONLY one instance as opposed to two.

The 8’s and 2's placeholders are the same so they return 0.
The 4’s and 1’s placeholders are different, therefore return true.

XOR logic table

XOR	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
0	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
1	1	0	3	2	5	4	7	6	9	8	B	A	D	C	F	E
2	2	3	0	1	6	7	4	5	A	B	8	9	E	F	C	D
3	3	2	1	0	7	6	5	4	B	A	9	8	F	E	D	C
4	4	5	6	7	0	1	2	3	C	D	E	F	8	9	A	B
5	5	4	7	6	1	0	3	2	D	C	F	E	9	8	B	A
6	6	7	4	5	2	3	0	1	E	F	C	D	A	B	8	9
7	7	6	5	4	3	2	1	0	F	E	D	C	B	A	9	8
8	8	9	A	B	C	D	E	F	0	1	2	3	4	5	6	7
9	9	8	B	A	D	C	F	E	1	0	3	2	5	4	7	6
A	A	B	8	9	E	F	C	D	2	3	0	1	6	7	4	5
B	B	A	9	8	F	E	D	C	3	2	1	0	7	6	5	4
C	C	D	E	F	8	9	A	B	4	5	6	7	0	1	2	3
D	D	C	F	E	9	8	B	A	5	4	7	6	1	0	3	2
E	E	F	C	D	A	B	8	9	6	7	4	5	2	3	0	1
F	F	E	D	C	B	A	9	8	7	6	5	4	3	2	1	0

Shift and rotate

Each of these operations can occur either to the right or to the left. Examples will use nibbles as operands (4 bits or 0.5 bytes).

Logical Shifts

For logical shifts, the bytes are assumed to be in big endian.

Using A or 1010 as an example:

Example: A shifted left by 1 = 4

Operation	Hexadecimal	Binary	comment
Left Shift	A 1	1010 0001	shifted to the left once, the 1 at the beginning gets shifted off, thus the binary value becomes 0100, or 4 in hexadecimal.
=	4	0100	The end value 0 is always used to replace the residual numbers.

Example: A shifted left by 2 = 8

Operation	Hexadecimal	Binary	comment
Left Shift	A 2	1010 0001	The first `10' is shifted off and the remaining two placeholders get zeroed out.
=	8	1000	The end value 0 is always used to replace the residual numbers.

Example: A shifted right by 1 = 5

Operation	Hexadecimal	Binary	comment
Right Shift	A 1	1010 0101	a single shift to the right is division by two for even numbers.
=	5	0101	The end value 0 is always used to replace the residual numbers.

If 'A' is shifted to the right twice it goes from 1010 to 0010

Operation	Hexadecimal	Binary	comment
Right Shift	A 2	1010 0001	shifted to the right twice, the one at the beginning gets shifted to the 2nd digit and the one in the 2nd digit place gets shifted off, thus the binary value becomes 0010, or 2 in hexadecimal.
=	2	0010	The end value 0 is always used to replace the residual numbers.

At this point, understanding should be emerging into real hacking and cryptography. If understanding is not attained regarding this knowledge, further extension topics will prove difficult. Thus, it is considered a baseline knowledge.

Exercises:

1) Solve for B left shift one

Operation	Hexadecimal	Binary
Left Shift One	B 1	"(B in Binary)" 0001
=	"??"	"???"

2) Solve for F right shift three

Operation	Hexadecimal	Binary
Right Shift three	F 3	"(F in Binary)" 0011
=	"??"	"???"

Answers:

1) 0110 or 6.

Operation	Hexadecimal	Binary
Left Shift One	B 1	1011 0001
=	"6"	"0110"

2) 0001 or 1.

Operation	Hexadecimal	Binary
Right Shift three	F 3	1110 0011
=	0001	1

Circular Shift or Bit Rotation

Circular shifts, or bit rotation occurs in processors which involves rotate /with carry/. Circular shifts are the same as rotate /without/ carry. So, continuing the usage of a nibble and A (1010) as the example...

If 6 is rotated to the left by 1 it becomes 0101 or 5

Operation	Hexadecimal	Binary	comment
Left Rotate	6 1	1010 0001	shifted to the left once, the 1 at the beginning gets shifted to the first digit, thus the binary value becomes 0101, or 5 in hexadecimal.
=	5	0101	The highest value "loops" back around to the lowest, like a clock/modular arithmetic.

Instead of replacing a value with zero, like a normal shift, the value is taken and shifted off of one side and applied to the other side. So for 1100 (C)

Example: C rotated left by 1, becomes 9 (1001)'

Operation	Hexadecimal	Binary	comment
Left Rotate	C 1	1100 0001	shifted to the left once, the 1 at the beginning gets shifted to the first digit, thus the binary value becomes 1001, or 9 in hexadecimal.
=	9	1001	The highest value "loops" back around to the lowest, like a clock/modular arithmetic.

Example: C rotated right by 1, becomes 6 (0110)'

Operation	Hexadecimal	Binary	comment
Right Rotate	C 1	1100 0001	shifted to the right once, the 1 at the beginning gets shifted to the third digit, thus the binary value becomes 0110, or 6 in hexadecimal.
=	6	0110	Something a little more intuitive

Based upon these examples, a circular shift is not the same thing as a logical shift. Proceeding further, two's complement and something small about binary will be explained.

Remember in the previous lesson, a nibble (four bits) can hold 16 values (the uppermost being 15 because one of these values is 0). Four bits maximum value also = 2^4 - 1. 4 is taken from the number of bits and the -1 from the zero placeholder. If a full byte was going to be shifted, it would be 2^8 - 1. The maximum value of which is 255.

Negative Numbers

There are several ways to represent a negative number:

Sign and Magnitude
Two's Complement

Sign and Magnitude

The first bit is considered the sign bit, which if set, translates the number to it's negative counterpart. While this is very straightforward, it requires a a new operation to be supported by the hardware (subtraction), and generates two representations for the 0 value (10000000 and 00000000). As a result, the sign bit is usually used on the largest endian number (called the two's compliment implementation), so that there can be a negative value one value higher or lower than the highest positive value, for example:

1000 = -8, while 0111 = 7

Two's Complement

A two's complement is basically a NOT operation performed on the nibble. Any binary number is converted between positive and negative by computing its two's complement. The leftmost bit is called the sign bit. There are two ways. (taking nibbles as an example) -1 could be 1001. This is not useful, as now there are two ways to represent 0, 1000 for -0 and 0000 for ordinary 0. Also the addition and subtraction has to be changed for this. This is all not nice. This is why people invented two's complement, two's complement is basically using 1111 for -1 and 1000 for -8.

The first operation performed is a NOT operation on the nibble, -1 has to be done. To determine the two complements the positive representation of the number is required. If it's negative, complement it and add one. Thus, to determine the two complements, positive representation of the number is required. If the original value is negative, determine the compliment and do +1. If its positive, the easy way to do it, is to tack zeroes on in the right number of bits. If negative tack 1's instead.

Just using one byte. It has 256 possible values Doing something like:


-42	-42 + 256	-42 + 255 + 1	255 - 42 + 1	213 + 1	214

The binary representation of both numbers /without/ a signing bit is the same.

Computers use this stuff to represent signing amongst other things. When doing arithmetic stuff gets messy. This gets even more messy when doing arithmetic shifts and rotates with carry on a CPU, since that's what modern day CPU's use.

Taking the example of -42. First, its positive representation is taken. So 42 in binary is: 00101010 (32+8+2). All of those placeholders have 1's and the rest have 0's.

Next step, as mentioned is to perform a NOT operation. So NOT(00101010) WILL BE 11010101. Replace 1 by 0 and vice-versa. Final step is to add 1 to the number obtained in above step. Thus:


11010101	+	00000001	=	11010110

What can also be done, is go at the bits one by one, starting at the right, and copy all the zeroes, until a 1 is obtained. Copy that 1 too, then flip all the remaining bits. So 42 is obtained again, which is 00101010. Then move from right-to-left, and get 11010110.

Overflows

Now, overflow occurs in a "signed" integer when it increments too far. Using a nibble for an example,


-8	4	2	1

The highest positive value is 7, 0111, the lowest negative value is -8, 1000. On a processor, the increment instruction(inc) changes this. If -8 is incremented, -7 is obtained, since it is incremented. Basically when moving to 7 and incremented, the next step in binary is 1000 and it lands on -8.

In an arithmetic shift, this is typically what processors do since signed numbers are worked with most of the times. Now of course, there are ways to use unsigned numbers, but this will be left for later. Most languages use an arithmetic shift, which is also called a 'signed shift'. This is because the number is "signed", that is, it has a + or - attatched to its value. Thus, when reading the hex, the way this works isn't going to change so terribly.

Example: 6 incremented left by 1, becomes -8 (1100)'

Operation	Hexadecimal	Binary	comment
Left Shift	6 1	0110 0001	shifted to the left once, the largest digit gets a 1. In this case, this gives the whole value a -8, not an eight.
=	"-8"	1100	The highest value "loops" back around to the lowest, like a clock/modular arithmetic.

The difference here is if that first bit is -8 and not an 8. A positive number has just been turned into a negative number. 6 left shift 1 = -4

Binary number 1100 = -8 + 4 = decimal number -4
Negative Eights -(1x2^3)	Fours (1x2^2)	Twos (1x2^1)	Ones (1x2^0)
-8	4	2	1
1	1	0	0

It's now -4.

If shifted to the right, a single shift will /always/ change the sign. If shifted to the left on any /unsigned/ binary number (shift by n), it is the same as multiplying it by 2^n. If shifted to the right on a two's complement signed number it is the same as dividing it by 2^n and always rounds down.

Example:

-8 right shift 1 or 1000 right shift 1 becomes 4. In other words, any signed number right shifted becomes positive immediately. Regardless of whether it was positive or not, it will always be positive once a right shift has been applied.

As stated before, x right shift n on a signed number is the same as x/(2^n). The problem that this could cause is that it always rounds down. So, if it always rounds down from 2^n (i.e. a fraction is obtained) it will round down until the fraction is gone.

The flow on problem from this is that if it rounds down and n is signed, the processor can run into a divide by zero error.

Rotate With Carry

Moving on now to rotate with carry. Rotate with carry occurs on a computer when a number is too large to fit into a single register. For example: On 32 bit systems the largest value an unsigned variable can hold is 2^32 - 1. An 8 bit system is being used just for sanity:


2^8	-	1	=	255

That would be the largest value that can be held. If wanting to hold 256, it would need two pieces of processor memory to do this so rotate with carry. There's a bit on the CPU called CF or carry flag. It is just a little bit, 1 or 0. So on an 8 bit system a 16 bit number would want to be rotated.


16 bit number	1011 1000 1010 0011

Now, the registers only contain 8 bits, so:

register 1 = 1011 1000
register 2 = 1010 0011

To connect these during the shift operation rather the rotate operation, there is a small bit called the carry flag (CF) on a CPU, that will store the value as the bits are shifted between the two registers. It will take the first "1" from register 2 into the CF bit then move all of register2 1 bit to the left, and so on and so forth.