5.1 Bits and Bytes

What is a bit?

• The smallest amount of information in a digital computer

• It can store the boolean value of one switch (on/off; 1/0; voltage/no voltage, etc)

What is a byte?

• A sequence of 8 bits

• cf. 8 christmas lights, one next to the other

How many different states can k bits together represent?

• 2^k different states

How many numbers can be written with k bits? What is the biggest number?

• 2^k

• Biggest number: 2^k - 1 (because 0 is also written with this representation)

What sizes are also (ocasionally) common in CS?

• word, containing 16 bits (2 bytes)

• double word (DWORD), containing 32 bits (4 bytes)

• quad word (QWORD), containing 64 bits (8 bytes)

Def: numeral

• symbol representing a small intefer value

Def: positional number system

• System constructed by fixing a totally ordered set of r numerals

• Each numeral is associated with an index i N₀ equal to the power of a radix r

• r is equal to the cardinality of the set of all numerals

• cf. algebraic representation of numbers in base r

What are the most important positional number systems in CS?

• Binary system

• Octal system

• Decimal system

• Hexadecimal system (0 to 9 and A to F)

• Base32 system

• Base64 system

Name one application of the Hexadecimal system?

• Colors in computer graphics programs

What is the algorithm to convert a number from one base to another? (3)

• Seperate the number in integer and fractional part

• For the integer part, divde the number by the radix (base) into quotient and remainder. Iterate. The integer part is made by reversing the order of the obtained numerals

• For the fractional part, it is iteratively multiplied by the radix, and take the numeral in front of the radix point as the numeral and truncate the number to its fractional part until a fixed number of fractional bits is achieved

Must fractional digits be limited during conversion? Why?

• Yes

• Because fractional numbers do not neededly have a finite representation in the target number system

Which methods are there to represent negative integers?

• Signed Magnitude

• Ones Complement

• Twos Complement

• Bias shifted

What is done in Signed Magnitude method?

• Using the most significative bit (leftmost bit) to represent the sign

• Usually, 0 is positive and 1 is negative

What are the disadvantages of Signed Magnitude method? (2)

• Implementing addition and substraction is complecated

• (0)₁₀ has two representations (000…0) and (1000…0) being 0 and -0 respectively

What is done in Ones Complement method?

• The negative number is the binary NOT of the positive number (the addition of both should result in 111…1)

What are the disadvantages of Ones Complement method?

• Double 0 (two representations of 0, namely 000…0 and 111…1)

What is done in Twos Complement method?

• The negative numbers are computed in binary as in Ones Complement. Then 1 is added to the binary number

• To add and substract them, the leftmost digit in the sum is ignored

What is the default representation for negative integers in CS nowadays?

• Twos Complement method

What is done in Bias Shifted?

• A fixed amount of numbers out of the total amount of numbers representable by the fixed amount of bits is taken

• Binary 000…0 then becomes the most negative number and onwards

What are the disadvantages of Bias Shifted method?

• Addition and substraction is extremely anti-intuitive

How does floating point representation works?

• Is the radix-equivalent to scientific notation (real numbers in radix r)

• x = s m r^e, where s is the sign, m is the mantissa and e the exponent

What is the bit distribution of floating points? (3)

• It uses 1 bit for the sign, 8 bits for the exponent and 23 bits for the mantissa (in 32bits)

• It uses 1 bit for the sign, 11 fot the exponent and 52 for the mantissa (in 64bits, for doubles)

• It uses 1 bit for the sign, 15 for the exponent and 112 for the mantissa (in 128bits, for quadruples)

What is the meaning of ASCII?

• American Standard Code for Information Interchange

How many characters are described in the ASCII table?

• 127

What is/was ASCII code used for?

• To represent characters as numbers

What is used nowadays instead of ASCII?

• Unicode UTF-8

Def: String

• Sequence of characters

What is used in C as delimiter for strings?

• NULL character with all bits set to zero