Bitwise math
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.
Contents
Introduction to Binary
Bitwise math/Introduction to Binary
Basic Addition
Bitwise math/Introduction to Binary/Basic Addition
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 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 0 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 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 2 0 0 2 2 0 0 2 2 0 0 2 2 0 0 2 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 4 0 0 0 0 4 4 4 4 0 0 0 0 4 4 4 4 5 0 1 0 1 4 5 4 5 0 1 0 1 4 5 4 5 6 0 0 2 2 4 4 6 6 0 0 2 2 4 4 6 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 8 8 8 8 8 8 8 8 9 0 1 0 1 0 1 0 1 8 9 8 9 8 9 8 9 A 0 0 2 2 0 0 2 2 8 8 A A 8 8 A A B 0 1 2 3 0 1 2 3 8 9 A B 8 9 A B C 0 0 0 0 4 4 4 4 8 8 8 8 C C C C D 0 1 0 1 4 5 4 5 8 9 8 9 C D C D E 0 0 2 2 4 4 6 6 8 8 A A C C E E F 0 1 2 3 4 5 6 7 8 9 A B C D E F
OR
|
|
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 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
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:
Circular Shift or Bit Rotation
Bitwise math/Circular Shift or Bit Rotation
Negative Numbers
Sign and Magnitude
Bitwise math/Negative Numbers/Sign and Magnitude
Two's Complement
Bitwise math/Negative Numbers/Two's Compliment
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.
