Three notations for an integer:
Decimal (base 10)
Binary (base 2)
Hexadecimal (base 16)

The integer 2026 written in decimal (base 10)

In decimal, each place has 10 times the value of the previous one.
Depending on the number, we might need to write ten decimal digits in these places: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

2 × 1000 = 2000
0 ×  100 =    0
2 ×   10 =   20
6 ×    1 =    6
           2026

The same integer 2026 written in binary (base 2)

In binary, each place has 2 times the value of the previous one.
No matter what the number is, we will only need to write two binary digits in these places: 0 and 1.

A binary digit (either 0 or 1) is called a bit.
Today we write the two possible values of a bit as 0 or 1.
In the days of Morse Code, we wrote them as “dot” and “dash”.

A series of 8 bits is called a byte. For example, 01010111.
A series of 4 bits is called a nibble. For example, 0101.

It takes eleven bits to write 2026 in binary:

1 × 1024 = 1024
1 ×  512 =  512
1 ×  256 =  256
1 ×  128 =  128
1 ×   64 =   64
1 ×   32 =   32
0 ×   16 =    0
1 ×    8 =    8
0 ×    4 =    0
1 ×    2 =    2
0 ×    1 =    0
           2026

The bits are numbered from right to left.

The bits of an integer are numbered from right to left, starting at 0. An integer on our machine occupies 32 bits, so its bits are numbered from 0 (least significant) to 31 (most significant) inclusive.

More examples of integers written in binary

On our machine storm.cis.fordham.edu, an int occupies 32 bits.

00000000000000000000000000000000  (zero)
00000000000000000000000000000001  (one)
00000000000000000000000000000010  (two)
00000000000000000000000000000011  (three)
00000000000000000000000000000100  (four)
00000000000000000000000000000101  (five)
00000000000000000000000000000110  (six)
00000000000000000000000000000111  (seven)
00000000000000000000000000001000  (eight)
00000000000000000000000000001001  (nine)
00000000000000000000000000001010  (ten)
00000000000000000000000000001011  (eleven)
00000000000000000000000000001100  (twelve)
00000000000000000000000000001101  (thirteen)
00000000000000000000000000001110  (fourteen)
00000000000000000000000000001111  (fifteen)
00000000000000000000000000010000  (sixteen)
00000000000000000000000000010001  (seventeen)
00000000000000000000000110110101  (four hundred thirty-seven)
00000000000000000000011111101001  (two thousand twenty-five)
00000000000000000000011111101010  (two thousand twenty-six)
00000000000000000000011111101011  (two thousand twenty-seven)

Counting in binary was invented by Leibniz (1646–1716).

Norman Mailer on binary numbers

The twentieth century American author Norman Mailer wrote a book about Apollo 11, Of a Fire on the Moon, in 1969–1970 to pay for his failed 1969 campaign for mayor of New York.

“The digital computer was a diabolical machine, or the greatest instrument ever handed to man, but it could hardly be both for it was constructed on the implicit premise that all phenomena might yet be capable of capture by statistics. The digital computer was based upon millions of switches, all primed individually to say one or nothing, yes or no. If the switch allowed a current to pass, the answer was one, or yes; absence of current was zero. 1 and 0 became the simple building blocks upon which numbers could be re-created. The entire decimal system was replaced by two numbers, 1 and 0, rather than 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Thus the figure of 111 in this new system stood for 7 because it was a way of writing

Why computers count in binary

An electrical component capable of holding a decimal digit has to be able to hold one of ten different levels of electricity. But an electrical component capable of holding a binary digit has to be able to hold one of only two different levels of electricity. The binary component will probably be cheaper to manufacture, and more reliable, than the decimal component. (And it will be smaller, lighter, more durable, and use less electricity and generate less unwanted heat, etc.)

Writing in binary takes more digits than in decimal.

The price we have to pay for these binary components is that we will need many more of binary components than decimal components. For example,

       2026    We wrote the number 2026 with only four digits in decimal,
11111101010    but we needed eleven digits to write it in binary.

To write the number n (e.g., 2026) takes ⌈log₁₀ n⌉ digits in decimal, or ⌈log₂ n⌉ digits in binary.
⌈log₂ n⌉ is a much bigger number than ⌈log₁₀ n⌉.
That’s why they invented “hexadecimal” notation.

Hexadecimal (base 16) notation

We usually consider bits in groups of 4 or 8 at a time (nibble by nibble, or byte by byte).
So let’s add five leading 0s to make a total of 16 bits:
0000011111101001

As shown by this example, a number usually needs many more digits when written in binary than in decimal.
Hexadecimal digits come to the rescue.
Each hexadecimal digit (hex digit) is an abbreviation for a series of four bits (or one nibble).
There are 16 possible nibbles, listed in the following table.
That’s why we have 16 possible hex digits.

We can now write our 16-bit number (2026 = 0000011111101010) with only 4 hex digits (07EA).

Exercise.
Write the following 32-bit integer as 8 hexadecimal digits. I put spaces between the 4 bytes to make it easier to read. (This example is from The Practice of Programming (1999) by Brian W. Kernighan and Rob Pike, p. 159.)
11011110 10101101 10111110 11101111

Write a number in hexadecimal in a C++ program

Write 0x (zero, lowercase x) in front of a hexadecimal number in a C++ program, such as 0x07EA. The hex digits that are letters can be written in either upper or lowercase.

	int lastYear {0x07E9};   //2025 in binary is 00000000 00000000 00000111 11101001
	int thisYear {0x07EA};   //2026 in binary is 00000000 00000000 00000111 11101010
	int nextYear {0x07EB};   //2027 in binary is 00000000 00000000 00000111 11101011

The code number of a “wide character” (Chinese, Japanese, Russian, etc.) can be written as four hexadecial digits. See, for example, wcout.C with Greek characters.

Write a number in hexadecimal in a page of HTML

Write # in front of a hexadecimal number in a page of HTML, such as #FF0000. An HTML rgb (red/green/blue) color code in a web page can be written as three two-digit hexadecimal numbers, standing for three eight-bit binary numbers.

For example, if you paste the following text into a web page,

<SPAN STYLE = "color: #FF0000;">Hello.</SPAN>
<BR/>
<SPAN STYLE = "background-color: #FF0000;">Hello.</SPAN>

your browser will render the text as

Output an integer in decimal, hexadecimal, and binary.

output.C, output.txt
Uses the C++ format function introduced in C++ version c++20 in the year 2020.

c++ -std=c++20 output.C
c++ -std=c++23 output.C

To output an integer in binary without using the format function, we will need two of the following “bitwise” operators:

Shift the bits of an integer to the left.

In the decimal world, left-shifting a number multiplies it by 10. For example,

   7     (seven)
  70     (seventy)
 700     (seven hundred)
7000     (seven thousand)
etc.

In the binary world, left-shifting a number multiplies it by 2. For example,

   111   (seven)
  1110   (fourteen)
 11100   (twenty-eight)
111000   (fifty-six)
etc.

	//Demonstrating the "left shift" operator <<
	//Its left operand is always an integer (in this case, n).

	const int n {0x7}; //In binary, n is 00000000 00000000 00000000 00000111 (seven)
	int i {n << 1};    //In binary, i is 00000000 00000000 00000000 00001110 (fourteen)
	int j {n << 2};    //In binary, j is 00000000 00000000 00000000 00011100 (twenty-eight)
	int k {n << 3};    //In binary, k is 00000000 00000000 00000000 00111000 (fifty-six)

An overloaded operator

The C++ operator << is overloaded. That means it can do two completely different operations, depending on the data type of its operands:

1. If the left operand of << is a destination for output (such as the familiar cout or cerr, or the unfamailiar wcout or wcerr), the << will perform input.

   	cout << "Hello.\n";
   

2. If the left operand of << is an int, the << will perform left-shift.

   	const int n {0x7}; //In binary, n is 00000000 00000000 00000000 00000111 (seven)
   	int i {n << 1};    //In binary, i is 00000000 00000000 00000000 00001110 (fourteen)
   

Left-shift in a loop

leftshift.C, leftshift.txt
Each iteration of the loop shifts the bits of the mask one place farther to the left.
The output demonstrates that each place in a binary number has twice the value of the place to its right.

Exercise.
In leftshift.C, have i count up to 63 instead of 31. You will have to make two other changes:

1. Change the data type of the mask from int to long int.
2. Change the width from 10 to 19.

There’s also a right-shift operator

In the decimal world, right-shifting a number divides it by 10. For example,

70000     (seventy thousand)
 7000     (seven thousand)
  700     (seven hundred)
   70     (seventy)
etc.

In the binary world, right-shifting a number divides it by 2. For example,

1110000   (one hundred twelve)
 111000   (fifty-six)
  11100   (twenty-eight)
   1110   (fourteen)
etc.

	//Demonstrating the "right shift" operator >>
	//Its left operand is always an integer (in this case, n).

	const int n {0x70}; //In binary, n is 00000000 00000000 00000000 01110000 (one hundred twelve)
	int i {n >> 1};     //In binary, i is 00000000 00000000 00000000 00111000 (fifty-six)
	int j {n >> 2};     //In binary, j is 00000000 00000000 00000000 00011100 (twenty-eight)
	int k {n >> 3};     //In binary, k is 00000000 00000000 00000000 00001110 (fourteen)

Another overloaded operator

The C++ operator >> is overloaded. That means it can do two completely different operations, depending on the data type of its operands:

1. If the left operand of >> is a source of input (such as the familiar cin or the unfamailiar wcin), the >> will perform input.

   	cout << "Please input an integer: ";
   	int i {0};
   	cin >> i;
   
   	if (!cin) {
   		cerr << "Sorry, couldn't read the input.\n";
   		return EXIT_FAILURE;
   	}
   

2. If the left operand of >> is an int, the >> will perform right-shift.

   	const int n {0x70}; //In binary, n is 00000000 00000000 00000000 01110000 (one hundred twelve)
   	int i {n >> 1};     //In binary, i is 00000000 00000000 00000000 00111000 (fifty-six)
   

Right-shift in a loop

rightshift.C, rightshift.txt.
Each iteration of the loop shifts the bits of the mask one place farther to the right.
The output demonstrates that each place in a binary number has half the value of the place to its left.

How to perform “bitwise and”

The “bitwise and” operation is simpler than addition or subtraction, because there is no carrying or borrowing.
Simply write the two operands on top of each other in binary.
A given bit of the result will be 1 if the two bits above it were 1s.
Otherwise, the bit of the result will be 0.

  1010  (ten)
& 0011  (three)
  0010  (two)

Use “bitwise and” to turn off selected bits of an integer.

In the following example, the mask 0011 gives us a result in which only the two rightmost bits of the original number (the 1010 in the top line) survive unchanged. The other bits of the original number get zeroed out.

  1010   the original number
& 0011   Allow only the 2 rightmost bits of the original number to survive unchanged.
  0010   The rest of the bits in the result are all 0s.

	//Demonstrating the "bitwise and" operator &

	int n {0xA};    //In binary, n is 00000000 00000000 00000000 00001010
	int m {0x3};    //In binary, m is 00000000 00000000 00000000 00000011
	int j {n & m};  //In binary, j is 00000000 00000000 00000000 00000010

Use “bitwise and” to turn off one bit of a character

  01100001   the original number (the ASCII code for lowercase 'a')
& 11011111   Allow 7 of the 8 bits of the original number to survive unchanged.
  01000001   Bit 5 has been changed to 0.

toupper.C, toupper.txt.

Exercise.
In toupper.C, change 0xDF to the expression
~(0x1 << 5)
with a tilde. It’s an easier way to make 0xDF, an integer in which every bit is turned on, except for bit number 5.

00000001  0x1
00100000  0x1 << 5
11011111  ~(0x1 << 5)   A tilde makes a photographic negative.

How to perform “bitwise or”

The “bitwise or” operation is simpler than addition or subtraction, because there is no carrying or borrowing.
Simply write the two operands on top of each other in binary.
A given bit of the result will be 0 if the two bits above it were 0s.
Otherwise, the bit of the result will be 1.

  1010  (ten)
| 0011  (three)
  1011  (eleven)

Use “bitwise or” to turn on selected bits of an integer

In the following example, the mask 0011 gives us a result in which only the two leftmost bits of the original number (the 1010 in the top line) survive unchanged. The other bits of the original number get changed into ones.

  1010   the original number
| 0011   Allow only the 2 leftmost bits of the original number to survive unchanged.
  1011   The rest of the bits in the result are all 1s.

	//The "bitwise or" operator &

	int n {0xA};    //In binary, n is 00000000 00000000 00000000 00001010
	int m {0x3};    //In binary, m is 00000000 00000000 00000000 00000011
	int j {n | m};  //In binary, j is 00000000 00000000 00000000 00001011

Use “bitwise or” to turn on one bit of a character

  01000001   the original number (the ASCII code for uppercase 'A')
| 00100000   Allow 7 of the 8 bits of the original number to survive unchanged.
  01100001   Bit 5 has been changed to 1.

tolower.C, tolower.txt.

Exercise.
In tolower.C, change 0x20 to the expression (0x1 << 5). It’s an easier way to make 0x20, an integer in which every bit is turned off, except for bit number 5.

00000001  0x1
00100000  0x1 << 5

Store information in individual bits

restaurants.C, restaurants.txt
A char is like an int with only 8 bits.
This program uses the rightmost 7 bits of each char.

Output an int in binary using the bitwise operators

decimaltobinary.C, decimaltobinary.txt.

The value of the int is already stored in binary in the computer’s memory. To get the value of each bit individually, we will use >> (right shift) and & (bitwise and).

binary.C outputs the 32 bits of an int one at a time, from left to right. During each iteration, we shift a different bit of the original number n to a position all the way on the right, and then use bitwise and to assasinate all the other bits. Only the bit all the way on the right survives to be output.

Three ways to convert binary to decimal

1. binarytodecimal1.C, binarytodecimal1.txt.

   This program loops from right to left through the characters of the string s.
   The string contains s.size() characters.
   (size is a “member function” of the “object” s.)
   The rightmost character of the string is therefore at subscript s.size() - 1.
   The leftmost character of the string is at subscript 0.

   An issue I don’t want to talk about now.
   I want the variable i to be of data type int.
   Unfortunately, the expresssion s.size() - 1 is of a different data type.
   We use an = to convert this expression to int, instead of using the customary {curly braces} to initialize i.

2. binarytodecimal2.C, binarytodecimal2.txt.

   The variable it is an iterator that gives us access to each char in the string s from right to left.
   (In other words, it is a reverse iterator.)
   We get access to each char by applying the operator * to the iterator, in the same way that we will soon apply the operator * to a pointer.

   There are many types of iterator.
   The function rbegin and the heart-rending function rend give us exactly the kind of iterator we need to loop backwards through the string s.

3. binarytodecimal3.C, binarytodecimal3.txt.

   The C++ Standard Libarary function stoi (“string to integer”) can convert a binary string to a decimal integer.
   If something goes wrong, however, it will “throw” two different types of “exceptions”, invalid_argument and out_of_range.
   We have to be prepared to “catch” these exceptions.

A conversion program that comes with Linux

bc is the binary calculator; -l (space minus lowercase L) is its math library.
ibase is the input base; obase is the output base.
They both default to 10.

Convert decimal to hexadecimal:

bc -l
obase=16
2026
7EA
2027
7EB
control-d

Convert hexadecimal to decimal:

bc -l
ibase=16
7EA
2026
7EB
2027
control-d

Convert decimal to binary:

bc -l
obase=2
2026
11111101010
2027
11111101011
control-d

Convert binary to decimal:

bc -l
ibase=2
11111101010
2026
11111101011
2027
control-d

Add even parity to each byte of input.

An ASCII code number is in the range 0 to 127 inclusive (00000000 to 01111111 inclusive).
Therefore even the largest ASCII code number will fit into the lower seven bits of a byte.

addparity.C
checkparity.C

The sed command (“stream editor”) will deliberately damage the d in Goodbye.
It will change the d from 11100100 (that’s hexadecimal E4) to 01100100 (that’s hexadecimal 64), giving it an incorrect parity.
Let’s see if this damage is detected by checkparity.C:

compile addparity
compile checkparity

echo Goodbye
Goodbye

echo Goodbye | addparity
Goo???e

echo Goodbye | addparity | checkparity
Goodbye

echo Goodbye | addparity | sed 's/\xE4/\x64/' | checkparity
Goo
Byte number 4 had odd parity.

echo $?            (See the exit status.)
1                  (1 means EXIT_FAILURE.)

Exercise.
In addparity.C, change 0x80 to (1 << 7).
It’s a nicer way to say 10000000.

Exercise.
In checkparity.C, change 0x7F to ~(1 << 7).
It’s a nicer way to say 01111111.
(The tilde ~ makes a photographic negative.)

Homeworks

1. restaurants.C restaurant.txt
2. restaurants2.C restaurants.txt