Bitwise math
Contents
1.0 - Introduction to Binary
Binary math and hex 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
| 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 and 8’s. So let’s analyse this for a moment, the binary number 1010, has a ‘1’ in the “eights” placeholder and and a ‘1’ in the “twos” placeholder. Add these together and you get 10 in decimal numbers.
| Eights (1x2^3) | Fours (1x2^2) | Twos (1x2^1) | Ones (1x2^0) |
|---|---|---|---|
| 1 | 0 | 1 | 0 |
Another example is 1111…
| Eights (1x2^3) | Fours (1x2^2) | Twos (1x2^1) | Ones (1x2^0) |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 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, we can multiply each of the binary values (1’s) by the above multipliers (1x23 1x22 1x21 1x100) or “8, 4, 2, 1”. This will then give us, 8+4+0+1=13.
1.1 - Basic Addition
Much like the decimal system, binary numbers can be added together. For this example we are going to use the binary numbers 0110 and 0010 and add them.
| 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, we can determine the value of the two binary numbers together is 8.
2.0 - Binary to Hexadecimal
For the past exercises, we have been working with 4 bits at once (4 values ranging from 0-1, e.g. 0001). This is a /nybble/ in hexadecimal. A byte is made of two nybbles as 8 bits make a byte. In hexadecimal, we have 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.
So in hex, say we’ve got AF 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, 15*1=15. Therefore 160(A)+15(F) = 175.
3.0 - NOT, AND, OR and XOR
3.1 - NOT
Not is an instruction that takes only ONE operand. The best way to describe it is that it inverts 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.
3.2 - AND
Our next instruction is AND, which returns “TRUE” per bits that are the same and takes two operands. True is 1 and false is 0. It operates bit by bit, just like NOT.
Example:
F AND A = A, F AND * = *
Any time F is AND’d with something, whatever it is AND’d with is the result.
Example: F AND A
-----------
F = 1111 so...> 1|1|1|1 < - All four bits are true.
-----------
A = 1010 so...> 1|0|1|0 < - The first and third bits are true.
-----------
1010 > 1|0|1|0 < - The first and third bits are the only true values in both F and A.
-----------
Because the bits in F and A that are the same, generate A but…
Example:
-----------
6 = 0110 so...> 0|1|1|0 < - The second and third bits are true.
-----------
5 = 0101 so...> 0|1|0|1 < - The second and fourth bits are true.
-----------
0100 > 0|1|0|0 < - The second bit is the only true values in both 6 and 5.
-----------
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.
3.3 - OR
OR will return true for each placeholder if ANY of the bits are true.
Example: 5 OR C
(0101 = 5) OR (1100 = C) = 1101 which equals D.
-----------
5 = 0101 so...> 0|1|0|1 < - The second and fourth bits are true.
-----------
C = 1100 so...> 1|1|0|0 < - The first and second bits are true.
-----------
D = 1101 > 1|1|0|1 < - The first, second and fourth bits are true in at least one instance.
-----------
3.4 - XOR
Xor is kind of a strange command, if the placeholder bits are different, it returns a true bit. If they are the same, it returns a false bit. Thus, anything XOR’d with itself, results in 0.
General Examples:
1 xor 1 = 0, 0 xor 0 = 0, 1 xor 0 = 1.
Detailed Example: A xor F = 5
-----------
A = 1010 so...> 1|0|1|0 < - The first and third bits are true.
-----------
F = 1111 so...> 1|1|1|1 < - The first, second and third bits are true.
-----------
0101 = 5 > 0|1|0|1 < - The second and fourth bits are true in ONLY one instance as opposed
to two found in bits 1 and 3.
-----------
The 1’s placeholders are the same so they return 0, same with the 8’s placeholder. The 4’s and 2’s are different, therefore return true. XOR is really WHICH BITS ARE NOT THE SAME.
4.0 - Conclusion
So that wraps up our basics of hex math, part two will contain bit shifting, bit rotation and some more advanced hex math (difference between logical and arithmetic shifts etc).
Shift and rotate
We're about to cover two more bitwise operations. One is called shift, the other, rotate. For those of you who already understand these concepts, we'll be covering /Logical/ shifts and Rotates /without carry/ (also known as /Circular shifts/). Each of these operations can occur either to the right or to the left. As we covered nibbles yesterday, that is the size of binary we will use in our examples (4 bits).
For this lesson, we can assume big endian. So we'll start with logical shifts.
Logical Shifts
On a binary level this stuff is really simple, given that we're only using a nibble. Lets use A or 1010 as an axample.
vvvvvvvv |-1010-| Shifted left once, the 1 at the beginning gets shifted off. |-0100-| Thus, the value becomes 0100. ^^^^^^^^
The end value "0" is /always/ used to replace the residual stuff. If you shift A to the left twice it goes from 1010 to 1000:
vvvvvvvv |-1010-| The first `10' is shifted off and the remaining two placeholders get zeroed out. |-1000-| <-x2 ^^^^^^^^
If we shift A to the right once it goes from 1010 to 0101
vvvvvvvv |-1010-| ->x1 |-0101-| ^^^^^^^^
If we shift it to the right twice it goes from 1010 to 0010
vvvvvvvv |-1010-| ->x2 |-0010-| ^^^^^^^^
This is going to get you to the point where you can understand real hacking & cryptography. If you don't understand this stuff you won't understand a lot of stuff later. Think of it as baseline knowledge.
Exercises:
1) Solve for B left shift one
vvvvvvvv |-????-| Value of B |-????-| <-x1 ^^^^^^^^
2) Solve for F right shift three
vvvvvvvv |-????-| Value of F |-????-| ->x3 ^^^^^^^^
Answers: (1) 0110 or 6. (2) 0001 or 1.
Circular Shift or Bit Rotation
We're about to cover something called a circular shift. Also called a bit rotation. On processors, they do something called rotate /with carry/. Circular shifts are the same as rotate /without/ carry. So, since we were using a nibble, and A (1010) was our example...
vvvvvvvv |-1010-| If we rotate that 1 to the left it becomes 0101 or 5 |-0101-| <-x1 ^^^^^^^^
Instead of replacing a value with zero, like a normal shift, we take the value shifted off of one side and apply it to the other side. So for 1100 (C)
vvvvvvvv |-1100-| Shift left 1, becomes 9 (1001) |-1001-| <-x1 ^^^^^^^^
vvvvvvvv |-1100-| Shift right 1, becomes 6 (0110) |-0110-| ->x1 ^^^^^^^^
Based upon these examples, a circular shift is not the same thing as a logical shift. So now we'll go a little further. I'm going to explain two's complement and something small about binary.
Remember in our previous lesson, we said 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. We get the 4 from the number of bits and the -1 from the zero placeholder. If we were going to do a full byte it would be 2^8 - 1. The maximum value of which is 255.
Two's Complement
Two's complement is a way to represent negative numbers in binary, the same thing as giving an integer a sign. Getting into the mechanics of two's compliment, though we end up with a few ways to do it. Signing bits are used these days.
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 2's complement. Basically, you call the leftmost bit the sign bit. Now you can go two ways. (taking nibbles as an example) -1 could be 1001. This is not useful, as now there are two ways to represent 0, being 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 the two's complement, the two's complement is basically using 1111 for -1 and 1000 for -8. You first basically perform a NOT operation on the nibble.
You have to do -1. To determine the two complements you need the positive representation of the number. If its negative you complement it and add one. Thus, to determine the two complements you need the positive representation of the number. 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.
Let's just use one byte. It's got 256 possible values So lets do 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 this 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.
Let's take the example of -42. First , we take its positive representation. So 42 , in binary is: 00101010 (32+8+2). All those placeholders have 1's and rest have 0's
Next step , as mentioned is to perform 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. so we do:
11010101 + 00000001 ---------- = 11010110
What you can also do, is go at the bits one by one, starting at the right, and copy all the zeroes, until you get a 1. Copy that 1 too, then flip all the remaining bits. So we get 42 again, which is 00101010. Then we go over it 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
Your highest positive value is gonna be 7, 0111, your lowest negative value is going to be -8, 1000. On a processor, the increment instruction(inc) changes this. If you inc -8, you get -7, since it is incremented. Basically when we get to 7 and we increment it, the next step in binary is 1000 and it lands on -8.
In an arithmetic shift, this is typically what processors do since we work with signed numbers most of the times. Now of course, there are ways to use unsigned numbers, but we will leave that 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.
vvvvvvvv |-0110-| (6) |-1100-| left shift 1 becomes 1100 ^^^^^^^^
The difference here is if that first bit is -8 and not an 8 we've just turned a positive number into a netative number. 6 left shift 1 = -4
-8 4 2 1 1 1 0 0 -8 + 4 = -4
It's now -4.
If you shift to the right, a single shift will /always/ change the sign. If you shift to the left on any /unsigned/ binary number (shift by n), it's the same as multiplying it by 2^n. If you shift to the right on a two's complement signed number its 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. if you get a fraction) it'll round down until the fraction is gone.
The flow on problem from this is if it rounds down and n is signed, we can run into a divide by zero error. This caused
Rotate With Carry
Now we're gonna get 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. We'll pretend we're on an 8 bit system just for sanity:
2^8 - 1 = 255
That would be the largest value you can hold. Say we wanted to hold 256, we'd 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 we want to rotate a 16 bit number.
1011 1000 1010 0011 (that's a 16 bit number)
Now, the registers only contain 8 bits, so register 1 = 1011 1000 and register 2 = 1010 0011 to connect these during the shift operation rather the rotate operation. There is a small bit, the carry flag, 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 so on and so forth.
