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

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 move the 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.

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.