Binary math is the underpinning of modern computing and data storage. All data is stored as either a 1 or a 0 and its encoding determines how those bits are interpreted.
Most of what a Software Engineer works with are higher level tools that are ultimately translated into machine code which ultimately operate on bits and bytes. A fundamental understanding of binary is an essential component of being a Software Engineer and understanding how things in a computer work.
Following are links to some good articles, explanations and tutorials on binary. Read them first before continuing to the further reading and exercises.
- http://www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml
- http://stackoverflow.com/questions/141525/absolute-beginners-guide-to-bit-shifting
- http://sol.gfxile.net/boolean.html
- PHP Bitwise Tutorial by Jim Plush
- http://access.mvps.org/access/general/gen0038.htm
- https://en.wikipedia.org/wiki/Two%27s_complement
Common Binary Lengths
| Name | Bits | Max Value | Notes |
| Bit | 1 | 1 | |
| Nibble | 4 | 15 | The number of bytes represented by a single hexadecimal character (more on that below) |
| Word | 16 | 65535 | This is a more ambiguous length and value. Also known as natural unit of data for a given architecture. |
| Double Word | 32 | 4294967295 |
Binary Values
| Decimal Value | Bits | Binary Representation |
| 1 | 1 | 0001 |
| 2 | 2 | 0010 |
| 4 | 3 | 0100 |
| 8 | 4 | 1000 |
| 16 | 5 | 0001 0000 |
| 32 | 6 | 0010 0000 |
| 64 | 7 | 0100 0000 |
| 128 | 8 | 1000 0000 |
| 256 | 9 | 0001 0000 0000 |
| 512 | 10 | 0010 0000 0000 |
| 1,024 | 11 | 0100 0000 0000 |
| 2,048 | 12 | 1000 0000 0000 |
| 4,096 | 13 | 0001 0000 0000 0000 |
| 8,192 | 14 | 0010 0000 0000 0000 |
| 16,384 | 15 | 0100 0000 0000 0000 |
| 32,768 | 16 | 1000 0000 0000 0000 |
| 65,536 | 17 | 0001 0000 0000 0000 0000 |
| 131,072 | 18 | 0010 0000 0000 0000 0000 |
| 262,144 | 19 | 0100 0000 0000 0000 0000 |
| 524,288 | 20 | 1000 0000 0000 0000 0000 |
| 1,048,576 | 21 | 0001 0000 0000 0000 0000 0000 |
| 2,097,152 | 22 | 0010 0000 0000 0000 0000 0000 |
| 4,194,304 | 23 | 0100 0000 0000 0000 0000 0000 |
| 8,388,608 | 24 | 1000 0000 0000 0000 0000 0000 |
| 16,777,216 | 25 | 0001 0000 0000 0000 0000 0000 0000 |
| 33,554,432 | 26 | 0010 0000 0000 0000 0000 0000 0000 |
| 67,108,864 | 27 | 0100 0000 0000 0000 0000 0000 0000 |
| 134,217,728 | 28 | 1000 0000 0000 0000 0000 0000 0000 |
| 268,435,456 | 29 | 0001 0000 0000 0000 0000 0000 0000 0000 |
| 536,870,912 | 30 | 0010 0000 0000 0000 0000 0000 0000 0000 |
| 1,073,741,824 | 31 | 0100 0000 0000 0000 0000 0000 0000 0000 |
| 2,147,483,648 | 32 | 1000 0000 0000 0000 0000 0000 0000 0000 |
| 4,294,967,296 | 33 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 |
| 8,589,934,592 | 34 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 |
| 17,179,869,184 | 35 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 |
| 34,359,738,368 | 36 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 68,719,476,736 | 37 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 137,438,953,472 | 38 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 274,877,906,944 | 39 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 549,755,813,888 | 40 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 1,099,511,627,776 | 41 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 2,199,023,255,552 | 42 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 4,398,046,511,104 | 43 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 8,796,093,022,208 | 44 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 17,592,186,044,416 | 45 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 35,184,372,088,832 | 46 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 70,368,744,177,664 | 47 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 140,737,488,355,328 | 48 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 281,474,976,710,656 | 49 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 562,949,953,421,312 | 50 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 1,125,899,906,842,624 | 51 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 2,251,799,813,685,248 | 52 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 4,503,599,627,370,496 | 53 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 9,007,199,254,740,992 | 54 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 18,014,398,509,481,984 | 55 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 36,028,797,018,963,968 | 56 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 72,057,594,037,927,936 | 57 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 144,115,188,075,855,872 | 58 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 288,230,376,151,711,744 | 59 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 576,460,752,303,423,488 | 60 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 1,152,921,504,606,846,976 | 61 | 0001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 2,305,843,009,213,693,952 | 62 | 0010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 4,611,686,018,427,387,904 | 63 | 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
| 9,223,372,036,854,775,807 | 64 | 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 |
Bitwise Operators
Bitwise operators allow you to manipulate a numerical value at the bit level. Following is an overview with examples.
& AND
Resulting bit is set if and only if the same bit is set in both operands. Can be thought of as multiplication. Multiply the two bits together and that is the value of the resulting bit.
Can be used to check if a bit is set or not.
| input bit 1 | input bit 2 | resulting bit |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
char a = 2; // 00000010
char b = 8; // 00001000
char c = a & b; // 00000000| OR
Inclusive OR. Resulting bit is set if either of the bits are set. Can be thought of as addition; 0+0=0, 1+0=1, 0+1=1, 1+1=1.
Can be used with a mask to set or turn on a bit whether or not the bit was already set.
| input bit 1 | input bit 2 | resulting bit |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
char a = 2; // 00000010
char b = 8; // 00001000
char c = a | b; // 00001010^ XOR
Exclusive OR. Resulting bit is set if the two do NOT agree. Unset if they do.
Used to indicate which bits are different in two different values. Can be used to toggle a bit in a value with a mask.
| input bit 1 | input bit 2 | resulting bit |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
char a = 2; // 00000010
char b = 8; // 00001000
char c = a ^ b; // 00001010~ NOT
Unary bitwise compliment that negates the value 0 -> 1, 1 -> 0. Or, bits that are set in the input are not set in the output.
Used in combination with & and a mask to unset a bit, or turn off a flag
flags = flags & ~mask;char a = 2; // 00000010
char b = ~a; // 11111101Bit Shifting
The following is specific to Java, but is generally applicable. There are two different types of bit shifting operations, logical and arithmetic.
- Logical: Will shift all of the bits in the given direction regardless of whether or not the value is signed. A right-shift will add a 0 to the left-most bit, and a left-shift will add a 0 to right-most bit and push the 2nd to last bit to the left into the most significant bit (assuming that this is a big endian architecture) regardless.
- Arithmetic: Will shift bits left and right leaving the most significant bit alone to retain whether or not the value is positive or negative.
>> Logical or Unsigned Right Shift
Shifts the bits in the operand the specified number of places to the right adding a 0 to the left-most bit regardless of the original value
// Ignore the fact that in Java a -2 is actually the two's compliment of 2
// The key is that the most significant bit is changed to a 0.
int a = -2; // 10000000 00000010
int b = a >> 1 // 01000000 00000001 or 2147483647
int c = 4; // 00000000 00000100
int d = c >> 1 // 00000000 00000010 or 2<< Logical or Unsigned Left Shift
Shifts the bits in the operand the specified number of places to the right adding a 0 to the left-most bit regardless of the original value
// Ignore the fact that in Java a -2 is actually the two's compliment of 2
// The key is that the most significant bit is replaced by its left-most
// neighbor.
int a = -2; // 10000000 00000010
int b = a << 1 // 00000000 00000100>>> Arithmetic or Signed Right Shift
Shifts the bits in the operand the specified number of places to the right adding retaining the left-most bit.
// Ignore the fact that in Java a -2 is actually the two's compliment of 2
// The key is that the most significant bit remains the same.
int a = -2; // 10000000 00000010
int b = a >>> 1 // 10000000 00000001Hexadecimal
While not actually binary, hexadecimal is something that every software engineer should know by heart.
A hex digit is a nibble (4 bytes). Digits A-F can, usually, be represented in either lower-case or capital letters. Memorize the following table.
| Hex Digit | Decimal Value | Binary |
| 0 | 0 | 0000 |
| 1 | 1 | 0001 |
| 2 | 2 | 0010 |
| 3 | 3 | 0011 |
| 4 | 4 | 0100 |
| 5 | 5 | 0101 |
| 6 | 6 | 0110 |
| 7 | 7 | 0111 |
| 8 | 8 | 1000 |
| 9 | 9 | 1001 |
| A | 10 | 1010 |
| B | 11 | 1011 |
| C | 12 | 1100 |
| D | 13 | 1101 |
| E | 14 | 1110 |
| F | 15 | 1111 |
In many programming languages hex values are prefixed with “0x”. Check the documentation for your favorite language for the proper syntax. Following are some examples.
| Hex | Decimal | Binary |
| 0x5E | 0 | 0101 1110 |
| 0xFFFF | 1 | 1111 1111 1111 1111 |
| 0xCAFEBABE | 2 | 1100 1010 1111 1110 1011 1010 1011 1110 |
Octal Numbers
Two’s Compliment
A concise explanation of two’s compliment.
Endianness
Determines whether the most significant bit (MSB) is stored in the lower memory address or the higher memory address for a given value. Little-endian is when the least significant bit (LSB) is stored are stored in lower memory addresses, or before, the MSB. A binary number written in code or on a whiteboard, 1011, would be 11 and is represented as a big-endian value.
Exercizes
How do you determine if a given integer value is a power of two?
Write a program that will convert an IPV4 string (“192.168.1.122”, etc) into an integral value and back again
This is a good line of interview questions that I usually start with, “How would you store an IPV4, dotted string, as an integer value?”. If it is in Java, what primitive type would you use and why?
How do you swap two numbers without using a third variable?
The key to the answer to this question is understanding XOR.