DEV Community: csm-yujinkim

Convert a decimal fraction to binary

csm-yujinkim — Wed, 12 Feb 2020 19:52:06 +0000

In this article, we deal with item 5 of the following key skills that build up to understanding the floating point system:

Define and identify the most and least significant bits in a word. Count how many combinations are possible in a word given its bit length.
Encode a positive integer in binary. Decode an unsigned integer to decimal.
Encode an integer in two's complement notation. Decode a signed integer to decimal.
Use sign extension to expand the number of bits in a word. Explain the mathematics.
Convert a decimal fraction to binary. Explain why this does not require any particular encoding scheme, such as a floating point standard.

Expanding our idea

We use the same method as we used before to convert number representations.

Practice

QUESTION 1 Convert the decimal number 25.5 to unsigned binary.

Answer: 25.5 - 16 = 9.5

9.5 - 8 = 1.5

1.5 - 1 = 0.5

0.5 - 0.5 = 0

The powers of two used are: the 4th, 3rd, 0th, and negative 1st. Negative powers of two gets placed to the right of the binary point. Arrange: 0001 1001.1.

QUESTION 2 Convert the decimal number 16.1 to unsigned binary.

Answer: 16.1 - 16 = 0.1

0.1 - 0.0625 [ or 2^-4 ] = 0.0375

0.0375 - 0.0315 [ or 2^-5 ] = 0.00625

0.00625 - 0.00390625 [ or 2^-8 ] = 0.00234375‬

0.00234375‬ - 0.001953125 [ or 2^-9 ] = 0.000390625‬

0.000390625‬ - 0.000244140625‬ [ or 2^-12 ] = 0.000146484375‬

...

We see that the pattern .0001 1001 1001 ... is repeating. Arrange the bits: 0001 0000.0001 1001 1001 ....

QUESTION 3 Convert 1011.0101 to decimal.

The bits below the binary point (.) have the values of the negative powers of two.

The answer is 2^3 + 2^1 + 2^0 + 2^-2 + 2^-4 = 10.3125‬.

It's not that difficult!

Review of Signed Number Representation

csm-yujinkim — Wed, 12 Feb 2020 04:41:55 +0000

In this article, we deal with items 3-4 of the following key skills that build up to understanding the floating point system:

Define and identify the most and least significant bits in a word. Count how many combinations are possible in a word given its bit length.
Encode a positive integer in binary. Decode an unsigned integer to decimal.
Encode an integer in two's complement notation. Decode a signed integer to decimal.
Use sign extension to expand the number of bits in a word. Explain the mathematics.
Convert a decimal fraction to binary. Explain why this does not require any particular encoding scheme, such as a floating point standard.

Two's complement notation

Two's complement notation is a practical and widely-used way to represent signed integers. This notation is not tied to any particular computer architecture, real or abstract.

The only change from unsigned notation is that the most significant bit (the 31st bit in our case) has the same magnitude but a negative sign: If we use 32-bit words, then its value is -2^31 , not 2^31 .

Because of that, the available range is shifted by -2^31 units to the left. In unsigned notation, the range of representation was [0, 2^32 - 1]. In signed notation, the range of representation is [-2^31, 2^31 - 1]. Note that 2^32 is exactly twice the value of 2^31 , since they are subsequent powers of two (the base 2 makes them twice as different). Hence, 2^32 - 2^31 - 1 = (2^31 + 2^31 ) - 2^31 - 1 = 2^31 - 1.

It takes practice to understand how this change affects arithmetic. Let's get into practice.

Practice

QUESTION 1 Convert -56 to a signed binary integer.

Answer: We use the same process we used in unsigned notation. The "smaller" as in "closest smaller power of two" still means actually smaller (not absolute value).

In this case, -64 is the closest power of two to -56 that is smaller than it. Use the subtraction: -56 - (-64) = 8. -64 is -2^6 .

8 happens to be the third power of two.

Use bit positions 6 and 3: 100 1000. 8 - 64 is indeed -56.

If we were to use all eight bits of the byte, then the answer would be 1100 1000. -128 + 64 + 8 is also -56. This is not a coincidence: We will explore the sign expansion technique in a bit.

QUESTION 2 Convert 101 1001 to a decimal.

Add the powers of two. The most significant bit has a negative value assigned. So, the summation looks like: -2^6 + 2^4 + 2^3 + 2^0 = -39.

What about 0101 1001? Its summation looks like 2^6 + 2^4 + 2^3 + 2^0 = 89. So, this is not the same as before. In fact, it is a positive number.

Lastly, consider 1101 1001. Its summation looks like -2^7 + 2^6 + 2^4 + 2^3 + 2^0 = -39.

So, we put as many 1's to the left as possible if we wanted to expand the number of bits?

QUESTION 3 There is a byte position in your memory that reads 0101 0100. You are asked to expand it to a four-byte word.

The given notation represents the number 84. We could either make it 1111 1111 1111 1111 1111 1111 0101 0100 or 0000 0000 0000 0000 0000 0000 0101 0100. Let's determine the values of these competing representations.

The first represents ‭-172‬. The second represents 84. In hindsight, it is clear that the first one would never work in the first place because the most significant digit is 1---it represents a negative integer. So, we should use the second representation.

Sign expansion

As we see through examples, if we have a representation like y..., and if we wanted to increase the number of bits in it, then we do not either just add 0s or 1s to the left of the MSB: The result may or may not equal the original number.

In fact, if we have y..., then the correct expansion is y...y.... That is, duplicate the MSB to the left.

For example, if the byte representation 1111 1111 was to be now represented by a 2-byte string, then the result should be 1111 1111 1111 1111. In case of 0000 0000, it should be 0000 0000 0000 0000.

The Mathematics

The technique of sign expansion relies on the fact that -2^n+1 + 2^n (11...) is the same as -2^n (1...). The following proof draws from the idea that they are powers of two, so one of them has a magnitude (absolute value) exactly twice as great as the other.

-2^n+1 + 2^n =?= -2^n

-( 2^n + 2^n ) + 2^n =?= -2^n

-2^n =?= -2^n

True.

Bonus: Overflow detection when all operands agree on sign

If all operands have the same sign (positive or negative), then if the result has a different sign, then overflow happened.

How? If we add all positive numbers, then the result should be positive. If it is negative, then overflow happened, since it is arithmetically impossible.

Practice

QUESTION 1 Sign-expand the 16-bit word 1101 0101 0010 0000 to 32 bits.

Answer: 1111 1111 1111 1111 1101 0101 0010 0000.

Question 2 Is this statement true or false, in all cases? "If overflow did not happen, then at least one operand must had had a different sign than the rest."

Answer: False. 0001 + 0001 = 0010. No overflow, but all operands agree on sign.

Question 3 "If overflow did not happen, then either or both of the following must be false: There was a sign agreement among the operands; the result was the same sign."

Answer: True by contraposition.

Review of MSB, LSB, and Unsigned Integers

csm-yujinkim — Wed, 12 Feb 2020 03:46:15 +0000

In this article, we deal with the first two of the following key skills that build up to understanding the floating point system:

Define and identify the most and least significant bits in a word. Count how many combinations are possible in a word given its bit length.
Encode a positive integer in binary. Decode an unsigned integer to decimal.
Encode an integer in two's complement notation. Decode a signed integer to decimal.
Use sign extension to expand the number of bits in a word. Explain the mathematics.
Convert a decimal fraction to binary. Explain why this does not require any particular encoding scheme, such as a floating point standard.

The MSB and the LSB. Unsigned Representation Practice

Definition: The most significant bit (MSB) is, in unsigned representation, the bit position associated with the greatest absolute value. Also, in two's complement representation, the bit position that changes the sign of a number.

Definition: The least significant bit (LSB) is the bit position that has the least value associated, that is, the value of 1.

Let's say we have a 32-bit machine that deals with 32-bit words. Each word is a string of four octets (bytes), so there are 32 bits in it. Then, generally, bit position 0 is the LSB, and bit position 31 is the MSB.

Bit position n has the value of 2^n, so, for instance, the number 1010 (unsigned) will be equal to 2^3 + 2^1 = 8 + 1 = 9. In this instance, the rightmost bit is the LSB and the leftmost bit the MSB.

Number of Combinations In a Word That Has n Bits

In unsigned notation like this, there are a total of 2^n combinations of the digits where n is the number of bits in a word. If there are 32 bits in a word, then 2^32 numbers can be represented. If we made a sequence of these numbers, it will start from 0, so the last number is exactly 1 less than the number of combinations, that is, 2^n - 1. So, in unsigned notation, numbers [0, 2^n - 1] are represented.

Practice

QUESTION 1 Represent the decimal number 254 in unsigned binary notation. What are the most and least significant bits?

ANSWER: The decimal number 254 is closest to a smaller (or equal) power of two, 128, or 2^7 . Divide 254 with that power. (Since the quotient is always 1, we replace the division by subtraction.) The remainder is 126. Do the same: The closest smaller (or equal) power of two is 64, or 2^6 . The difference is 62. With 2^5 = 32, the difference is 30. With 2^4 = 16, the difference is 14. With 2^3 = 8, the difference is 6. With 2^2 = 4, the difference is 2. With the equal power of two, 2^1 = 2, the difference is 0. The exponents of two are where the 1's are. They are bit positions 1, 2, 3, 4, 5, 6 and 7.

Let's use an octet (an eight-bit string). The leftmost is the MSB, so it is bit position 7. The rightmost is the LSB, and its bit position is 0. Now, arrange it: 1111 1110. This is our representation.

The MSB is 1, and the LSB is 0.

Let's use a 32-bit word. Again, the leftmost is the MSB, and its bit position is 31. The rightmost is the LSB, and its position is 0. Now, arrange it: 0000 0000 0000 0000 0000 0000 1111 1110. The MSB is changed: It is now 0. The LSB is still 0.

QUESTION 2 Represent 142 in unsigned representation.

Answer: Remember to choose the closest smaller (or equal) power of two, until the remainder (or difference) is 0. Then, record the bit positions---that's our method.

142 - 128 = 14

14 - 8 = 6

6 - 4 = 2

2 - 2 = 0

The powers are: 1, 2, 3, 7. Use an octet. The leftmost is the MSB, bit position 7, and the rightmost is the LSB, bit position 0. Arrange: 1000 1110.

QUESTION 3 Decode 1001 1010 in unsigned rep. to decimal. The leftmost is the MSB.

Answer: It is a sum of powers of two. The 7th, 4th, 3rd and 1st powers are represented. So, add them up: 2^7 + 2^4 + 2^3 + 2^1 = 154.

Challenge

Challenge Problem 1

Convert the positive integer 1,257,281 to binary:

Is a byte sufficient to store the representation? A 2-byte word? A 32-bit word? A 64-bit word?

Challenge Problem 2

Consider the representation 1111 1111 in unsigned notation in a byte:

What is its decimal value?
If the most significant bit was assigned the value of -2^7 , instead of 2^7 ,then what is its new decimal value?

Generate and register an SSH key pair to log into an SSH server

csm-yujinkim — Sun, 09 Feb 2020 01:25:06 +0000

The command ssh-keygen can be used to create an SSH key pair that is used to authenticate oneself. SSH supports a variety of authentication schemes, including the public-key system (SSH.com).

This article is a summary of an article found on Medium, which is written by Risan Bagja Pradana.

There are different algorithms for generating a key pair that SSH supports. The EdDSA algorithm is most recommended. The SSH term (or variant) for the algorithm is "Ed25519" (Pradana).

Among Pradana's recommended options (Pradana), one seems essential: The t option, which specifies the algorithm used to generate the key pair. So, for example, using the t option, the following command can be used to generate a key pair: ssh-keygen -t ed25519 (Pradana).

After generating the key pair, it is essential that we register the key pair with the SSH Agent. The Agent must first be running. And then, we use either of the following commands to add our new pair (Pradana):

ssh-add ~/.ssh/id_ed25519 # new pair, OR
ssh-add                   # all existing keys

Lastly, we must register the public key with the server we intend to connect to. Use the following command: ssh -i ~/.ssh/id_ed25519 username@server (Pradana).

More information can be obtained in the cited article by Pradana. It is a Medium article, but it is not a "Premium" article.

[Code Snippet] Printing prime factors of a number. Demo included.

csm-yujinkim — Tue, 04 Feb 2020 05:39:24 +0000

Print all prime factors of a number without duplication. In this example, each factor is printed in each successive line. The included demo provides examples for numbers [2-31].