ADDITIONAL JAVA TOPICS - Java Programming: From Problem Analysis to Program Design - page 950

For example, for the integer 65, k ¼ 6, a 6 ¼ 1, a 5 ¼ 0, a 4 ¼ 0, a 3 ¼ 0, a 2 ¼ 0, a 1 ¼ 0, and
a 0 ¼ 1. Thus, a 6 a 5 a 4 a 3 a 2 a 1 a 0 ¼ 1000001, so the binary representation of 65 is 1000001, that is:

65 10 ¼ð 1000001 Þ 2 :

If no confusion arises, then we write (1000001) 2 as 1000001 2 .
Similarly, for the number 711, k ¼ 9, a 9 ¼ 1, a 8 ¼ 0, a 7 ¼ 1, a 6 ¼ 1, a 5 ¼ 0, a 4 ¼ 0,
a 3 ¼ 0, a 2 ¼ 1, a 1 ¼ 1, and a 0 ¼ 1. Thus:

711 10 ¼ 1011000111 2 :

It follows that to find the binary representation of a nonnegative integer, we need to find
the coefficients, which are 0 or 1, of various powers of 2. However, there is an easy
algorithm, described next, that can be used to find the binary representation of a
nonnegative integer. First, note that:

0 10 ¼ 0 2 ; 1 10 ¼ 1 2 ; 2 10 ¼ 10 2 ; 3 10 ¼ 11 2 ; 4 10 ¼ 100 2 ; 5 10 ¼ 101 2 ; 6 10 ¼ 110 2 ; and 7 10 ¼ 111 2 :

Let us consider the integer 65. Note that 65 / 2 ¼ 32 and 65 % 2 ¼ 1, where % is
the mod operator. Next, 32 / 2 ¼ 16, and 32 % 2 ¼ 0, and so on. It can be shown that
a 0 ¼ 65 % 2 ¼ 1, a 1 ¼ 32 % 2 ¼ 0, and so on. We can show this continuous division
and obtain the remainder with the help of Figure D-1.

dividend/quotient

dividend/quotient

remainder

remainder

65 65

65 % 2 = 1 = a 0

1 = a 0

2 65 / 2 = 32 2 32

32 % 2 = 0 = a 1

0 = a 1

2 32 / 2 = 16 2 16

16 % 2 = 0 = a 2

16 / 2 = 8 0 = a 2

2 2 8

8 % 2 = 0 = a 3 0 = a 3

8 / 2 = 4

2 2 4

4 % 2 = 0 = a 4 0 = a 4

4 / 2 = 2

2 2 2

0 = a 5

2 / 2 = 1 2 % 2 = 0 = a 5

2 2 1

1 / 2 = 0 1 = a 6

1 % 2 = 1 = a 6

0

(a) (b)

FIGURE D-1 Determining the binary representation of 65