Questions about this topic? Sign up to ask in the talk tab.

Bitwise math/Negatives

From NetSec
Jump to: navigation, search
back to Bitwise math

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.