Binary

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.

Common Binary Lengths

NameBitsMax ValueNotes
Bit11
Nibble415The number of bytes represented by a single hexadecimal character (more on that below)
Word1665535This is a more ambiguous length and value. Also known as natural unit of data for a given architecture.
Double Word324294967295

Binary Values

Decimal ValueBitsBinary Representation
110001
220010
430100
841000
1650001 0000
3260010 0000
6470100 0000
12881000 0000
25690001 0000 0000
512100010 0000 0000
1,024110100 0000 0000
2,048121000 0000 0000
4,096130001 0000 0000 0000
8,192140010 0000 0000 0000
16,384150100 0000 0000 0000
32,768161000 0000 0000 0000
65,536170001 0000 0000 0000 0000
131,072180010 0000 0000 0000 0000
262,144190100 0000 0000 0000 0000
524,288201000 0000 0000 0000 0000
1,048,576210001 0000 0000 0000 0000 0000
2,097,152220010 0000 0000 0000 0000 0000
4,194,304230100 0000 0000 0000 0000 0000
8,388,608241000 0000 0000 0000 0000 0000
16,777,216250001 0000 0000 0000 0000 0000 0000
33,554,432260010 0000 0000 0000 0000 0000 0000
67,108,864270100 0000 0000 0000 0000 0000 0000
134,217,728281000 0000 0000 0000 0000 0000 0000
268,435,456290001 0000 0000 0000 0000 0000 0000 0000
536,870,912300010 0000 0000 0000 0000 0000 0000 0000
1,073,741,824310100 0000 0000 0000 0000 0000 0000 0000
2,147,483,648321000 0000 0000 0000 0000 0000 0000 0000
4,294,967,296330001 0000 0000 0000 0000 0000 0000 0000 0000
8,589,934,592340010 0000 0000 0000 0000 0000 0000 0000 0000
17,179,869,184350100 0000 0000 0000 0000 0000 0000 0000 0000
34,359,738,368361000 0000 0000 0000 0000 0000 0000 0000 0000
68,719,476,736370001 0000 0000 0000 0000 0000 0000 0000 0000 0000
137,438,953,472380010 0000 0000 0000 0000 0000 0000 0000 0000 0000
274,877,906,944390100 0000 0000 0000 0000 0000 0000 0000 0000 0000
549,755,813,888401000 0000 0000 0000 0000 0000 0000 0000 0000 0000
1,099,511,627,776410001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
2,199,023,255,552420010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
4,398,046,511,104430100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
8,796,093,022,208441000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
17,592,186,044,416450001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
35,184,372,088,832460010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
70,368,744,177,664470100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
140,737,488,355,328481000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
281,474,976,710,656490001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
562,949,953,421,312500010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
1,125,899,906,842,624510100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
2,251,799,813,685,248521000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
4,503,599,627,370,496530001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
9,007,199,254,740,992540010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
18,014,398,509,481,984550100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
36,028,797,018,963,968561000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
72,057,594,037,927,936570001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
144,115,188,075,855,872580010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
288,230,376,151,711,744590100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
576,460,752,303,423,488601000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
1,152,921,504,606,846,976610001 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
2,305,843,009,213,693,952620010 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
4,611,686,018,427,387,904630100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
9,223,372,036,854,775,807641000 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 1input bit 2resulting bit
111
100
010
000
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 1input bit 2resulting bit
111
101
011
000
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 1input bit 2resulting bit
110
101
011
000
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;    // 11111101

Bit 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 00000001

Hexadecimal

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 DigitDecimal ValueBinary
000000
110001
220010
330011
440100
550101
660110
770111
881000
991001
A101010
B111011
C121100
D131101
E141110
F151111

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.

HexDecimal Binary
0x5E00101 1110
0xFFFF11111 1111 1111 1111
0xCAFEBABE21100 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.