In order to understand the bit manipulation operators, it is first necessary to understand how integers are represented in binary. Consider a normal decimal number, such as 5623. We intuitively understand that these digits mean (5 * 1000) + (6 * 100) + (2 * 10) + (3 * 1). Because there are 10 decimal numbers, the value of each digit increases by a factor of 10.
Binary numbers work the same way, except because there are only 2 binary numbers (0 and 1), the value of each digit increases by a factor of 2. Just like commas are often used to make a large decimal number easy to read (eg. 1,427,435), we often write binary numbers in groups of 4 bits to make them easier to read.
Converting binary to decimal
In the following examples, we assume that we’re dealing with unsigned numbers.
Consider the 8 bit (1 byte) binary number 0101 1110. 0101 1110 means (0 * 128) + (1 * 64) + (0 * 32) + (1 * 16) + (1 * 8) + (1 * 4) + (1 * 2) + (0 * 1). If we sum up all of these parts, we get the decimal number 64 + 16 + 8 + 4 + 2 = 94.
Here is the same process in table format. We multiple each binary digit by it’s bit value (determined by it’s position). Summing up all these values gives us the total.
| Binary digit | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| * Bit value | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| = Total (94) | 0 | 64 | 0 | 16 | 8 | 4 | 2 | 0 |
Let’s convert 1001 0111 to decimal:
| Binary digit | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
| * Bit value | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| = Total (151) | 128 | 0 | 0 | 16 | 0 | 4 | 2 | 1 |
1001 0111 binary = 151 in decimal.
This can easily be extended to 16 or 32 bit binary numbers simply by adding more columns.
Converting decimal to binary
Converting from decimal to binary is a little more tricky, but still pretty straightforward. The easiest way to do this is to work backwards to figure out what each of the bits must be.
Consider the decimal number 148.
Is 148 >= 128? Yes, so the 128 bit must be 1. 148 – 128 = 20, which means we need to find bits worth 20 more.
Is 20 >= 64? No, so the 64 bit must be 0.
Is 20 >= 32? No, so the 32 bit must be 0.
Is 20 >= 16? Yes, so the 16 bit must be 1. 20 – 16 = 4, which means we need to find bits worth 4 more.
Is 20 >= 64? No, so the 64 bit must be 0.
Is 20 >= 32? No, so the 32 bit must be 0.
Is 20 >= 16? Yes, so the 16 bit must be 1. 20 – 16 = 4, which means we need to find bits worth 4 more.
Is 4 >= 8? No, so the 8 bit must be 0.
Is 4 >= 4? Yes, so the 4 bit must be 1. 4 – 4 = 0, which means all the rest of the bits must be 0.
Is 4 >= 4? Yes, so the 4 bit must be 1. 4 – 4 = 0, which means all the rest of the bits must be 0.
148 = (1 * 128) + (0 * 64) + (0 * 32) + (1 * 16) + (0 * 8) + (1 * 4) + (0 * 2) + (0 * 1) = 1001 0100
In table format:
| Binary number | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| * Bit value | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| = Total (148) | 128 | 0 | 0 | 16 | 0 | 4 | 0 | 0 |
Let’s convert 117 to binary:
Is 117 >= 128? No, so the 128 bit must be 0.
Is 117 >= 64? Yes, so the 64 bit must be 1. 117 – 64 = 53.
Is 53 >= 32? Yes, so the 32 bit must be 1. 53 – 32 = 21.
Is 21 >= 16? Yes, so the 16 bit must be 1. 21 – 16 = 5.
Is 117 >= 64? Yes, so the 64 bit must be 1. 117 – 64 = 53.
Is 53 >= 32? Yes, so the 32 bit must be 1. 53 – 32 = 21.
Is 21 >= 16? Yes, so the 16 bit must be 1. 21 – 16 = 5.
Is 5 >= 8? No, so the 8 bit must be 0.
Is 5 >= 4? Yes, so the 4 bit must be 1. 5 – 4 = 1.
Is 1 >= 2? No, so the 2 bit must be 0.
Is 1 >= 1? Yes, so the 1 bit must be 1.
Is 5 >= 4? Yes, so the 4 bit must be 1. 5 – 4 = 1.
Is 1 >= 2? No, so the 2 bit must be 0.
Is 1 >= 1? Yes, so the 1 bit must be 1.
117 decimal = 0111 0101 binary.
Signed numbers
The following section is optional. Most of the time when we deal with binary numbers and bit operations, we use unsigned numbers. However, it is interesting to examine how signed numbers are dealt with.
Signed numbers are typically stored using a method known as two’s complement. In two’s complement, the leftmost (most significant) bit is used as the sign bit. A 0 bit means the number is positive, and a 1 bit means the number is negative. Positive signed numbers are stored just like positive unsigned numbers. Negative signed numbers are stored as the inverse of the positive number, plus 1.
For example, here’s how we convert -5 to binary:
First we figure out the binary representation for 5: 0000 0101
Then we invert all of the bits: 1111 1010
Then we add 1: 1111 1011
Then we invert all of the bits: 1111 1010
Then we add 1: 1111 1011
Converting -76 to binary:
Positive 76 in binary: 0100 1100
Invert all the bits: 1011 0011
Add 1: 1011 0100
Invert all the bits: 1011 0011
Add 1: 1011 0100
Why do we add 1? Consider the number 0. If a negative value was simply represented as the inverse of the positive number, 0 would have two representations: 0000 0000 (positive zero) and 1111 1111 (negative zero). By adding 1, 1111 1111 intentionally overflows and becomes 0000 0000. This prevents 0 from having two representations, and simplifies some of the internal logic needed to deal with negative numbers.
Quiz
1) Convert 0100 1101 to decimal.
2) Convert 93 to an 8-bit binary number.
2) Convert 93 to an 8-bit binary number.
Quiz answers
0 comments: