data representation in computer questions and answers

Data Representation

Class 11 - computer science with python sumita arora, checkpoint 2.1.

What are the bases of decimal, octal, binary and hexadecimal systems ?

The bases are:

• Decimal — Base 10
• Octal — Base 8
• Binary — Base 2
• Hexadecimal — Base 16

What is the common property of decimal, octal, binary and hexadecimal number systems ?

Decimal, octal, binary and hexadecimal number systems are all positional-value system .

Complete the sequence of following binary numbers : 100, 101, 110, ............... , ............... , ............... .

100, 101, 110, 111 , 1000 , 1001 .

Complete the sequence of following octal numbers : 525, 526, 527, ............... , ............... , ............... .

525, 526, 527, 530 , 531 , 532 .

Complete the sequence of following hexadecimal numbers : 17, 18, 19, ............... , ............... , ............... .

17, 18, 19, 1A , 1B , 1C .

Convert the following binary numbers to decimal and hexadecimal:

(c) 101011111

(e) 10010101

(f) 11011100

Converting to decimal:

Equivalent decimal number = 8 + 2 = 10

Therefore, (1010) 2 = (10) 10

Converting to hexadecimal:

Grouping in bits of 4:

1010 undefined \underlinesegment{1010} 1010 ​

Therefore, (1010) 2 = (A) 16

Equivalent decimal number = 32 + 16 + 8 + 2 = 58

Therefore, (111010) 2 = (58) 10

0011 undefined 1010 undefined \underlinesegment{0011} \quad \underlinesegment{1010} 0011 ​ 1010 ​

Therefore, (111010) 2 = (3A) 16

Equivalent decimal number = 256 + 64 + 16 + 8 + 4 + 2 + 1 = 351

Therefore, (101011111) 2 = (351) 10

0001 undefined 0101 undefined 1111 undefined \underlinesegment{0001} \quad \underlinesegment{0101} \quad \underlinesegment{1111} 0001 ​ 0101 ​ 1111 ​

Therefore, (101011111) 2 = (15F) 16

Equivalent decimal number = 8 + 4 = 12

Therefore, (1100) 2 = (12) 10

1100 undefined \underlinesegment{1100} 1100 ​

Therefore, (1100) 2 = (C) 16

Equivalent decimal number = 1 + 4 + 16 + 128 = 149

Therefore, (10010101) 2 = (149) 10

1001 undefined 0101 undefined \underlinesegment{1001} \quad \underlinesegment{0101} 1001 ​ 0101 ​

Therefore, (101011111) 2 = (95) 16

Equivalent decimal number = 4 + 8 + 16 + 64 + 128 = 220

Therefore, (11011100) 2 = (220) 10

1101 undefined 1100 undefined \underlinesegment{1101} \quad \underlinesegment{1100} 1101 ​ 1100 ​

Therefore, (11011100) 2 = (DC) 16

Convert the following decimal numbers to binary and octal :

Converting to binary:

Therefore, (23) 10 = (10111) 2

Converting to octal:

Therefore, (23) 10 = (27) 8

Therefore, (100) 10 = (1100100) 2

Therefore, (100) 10 = (144) 8

Therefore, (145) 10 = (10010001) 2

Therefore, (145) 10 = (221) 8

Therefore, (19) 10 = (10011) 2

Therefore, (19) 10 = (23) 8

Therefore, (121) 10 = (1111001) 2

Therefore, (121) 10 = (171) 8

Therefore, (161) 10 = (10100001) 2

Therefore, (161) 10 = (241) 8

Convert the following hexadecimal numbers to binary :

(A6) 16 = (10100110) 2

(A07) 16 = (101000000111) 2

(7AB4) 16 = (111101010110100) 2

(BE) 16 = (10111110) 2

(BC9) 16 = (101111001001) 2

(9BC8) 16 = (1001101111001000) 2

Convert the following binary numbers to hexadecimal and octal :

(a) 10011011101

(b) 1111011101011011

(c) 11010111010111

(d) 1010110110111

(e) 10110111011011

(f) 1111101110101111

0100 undefined 1101 undefined 1101 undefined \underlinesegment{0100} \quad \underlinesegment{1101} \quad \underlinesegment{1101} 0100 ​ 1101 ​ 1101 ​

Therefore, (10011011101) 2 = (4DD) 16

Converting to Octal:

Grouping in bits of 3:

010 undefined 011 undefined 011 undefined 101 undefined \underlinesegment{010} \quad \underlinesegment{011} \quad \underlinesegment{011} \quad \underlinesegment{101} 010 ​ 011 ​ 011 ​ 101 ​

Therefore, (10011011101) 2 = (2335) 8

1111 undefined 0111 undefined 0101 undefined 1011 undefined \underlinesegment{1111} \quad \underlinesegment{0111} \quad \underlinesegment{0101} \quad \underlinesegment{1011} 1111 ​ 0111 ​ 0101 ​ 1011 ​

Therefore, (1111011101011011) 2 = (F75B) 16

001 undefined 111 undefined 011 undefined 101 undefined 011 undefined 011 undefined \underlinesegment{001} \quad \underlinesegment{111} \quad \underlinesegment{011} \quad \underlinesegment{101} \quad \underlinesegment{011} \quad \underlinesegment{011} 001 ​ 111 ​ 011 ​ 101 ​ 011 ​ 011 ​

Therefore, (1111011101011011) 2 = (173533) 8

0011 undefined 0101 undefined 1101 undefined 0111 undefined \underlinesegment{0011} \quad \underlinesegment{0101} \quad \underlinesegment{1101} \quad \underlinesegment{0111} 0011 ​ 0101 ​ 1101 ​ 0111 ​

Therefore, (11010111010111) 2 = (35D7) 16

011 undefined 010 undefined 111 undefined 010 undefined 111 undefined \underlinesegment{011} \quad \underlinesegment{010} \quad \underlinesegment{111} \quad \underlinesegment{010} \quad \underlinesegment{111} 011 ​ 010 ​ 111 ​ 010 ​ 111 ​

Therefore, (11010111010111) 2 = (32727) 8

0001 undefined 0101 undefined 1011 undefined 0111 undefined \underlinesegment{0001} \quad \underlinesegment{0101} \quad \underlinesegment{1011} \quad \underlinesegment{0111} 0001 ​ 0101 ​ 1011 ​ 0111 ​

Therefore, (1010110110111) 2 = (15B7) 16

001 undefined 010 undefined 110 undefined 110 undefined 111 undefined \underlinesegment{001} \quad \underlinesegment{010} \quad \underlinesegment{110} \quad \underlinesegment{110} \quad \underlinesegment{111} 001 ​ 010 ​ 110 ​ 110 ​ 111 ​

Therefore, (1010110110111) 2 = (12667) 8

0010 undefined 1101 undefined 1101 undefined 1011 undefined \underlinesegment{0010} \quad \underlinesegment{1101} \quad \underlinesegment{1101} \quad \underlinesegment{1011} 0010 ​ 1101 ​ 1101 ​ 1011 ​

Therefore, (10110111011011) 2 = (2DDB) 16

010 undefined 110 undefined 111 undefined 011 undefined 011 undefined \underlinesegment{010} \quad \underlinesegment{110} \quad \underlinesegment{111} \quad \underlinesegment{011} \quad \underlinesegment{011} 010 ​ 110 ​ 111 ​ 011 ​ 011 ​

Therefore, (10110111011011) 2 = (26733) 8

1111 undefined 1011 undefined 1010 undefined 1111 undefined \underlinesegment{1111} \quad \underlinesegment{1011} \quad \underlinesegment{1010} \quad \underlinesegment{1111} 1111 ​ 1011 ​ 1010 ​ 1111 ​

Therefore, (1111101110101111) 2 = (FBAF) 16

001 undefined 111 undefined 101 undefined 110 undefined 101 undefined 111 undefined \underlinesegment{001} \quad \underlinesegment{111} \quad \underlinesegment{101} \quad \underlinesegment{110} \quad \underlinesegment{101} \quad \underlinesegment{111} 001 ​ 111 ​ 101 ​ 110 ​ 101 ​ 111 ​

Therefore, (1111101110101111) 2 = (175657) 8

Checkpoint 2.2

Multiple choice questions.

The value of radix in binary number system is ..........

The value of radix in octal number system is ..........

The value of radix in decimal number system is ..........

The value of radix in hexadecimal number system is ..........

Which of the following are not valid symbols in octal number system ?

Which of the following are not valid symbols in hexadecimal number system ?

Which of the following are not valid symbols in decimal number system ?

The hexadecimal digits are 1 to 0 and A to ..........

The binary equivalent of the decimal number 10 is ..........

Question 10

ASCII code is a 7 bit code for ..........

• other symbol
• all of these ✓

Question 11

How many bytes are there in 1011 1001 0110 1110 numbers?

Question 12

The binary equivalent of the octal Numbers 13.54 is.....

• 1101.1110 ✓
• None of these

Question 13

The octal equivalent of 111 010 is.....

Question 14

The input hexadecimal representation of 1110 is ..........

Question 15

Which of the following is not a binary number ?

Question 16

Convert the hexadecimal number 2C to decimal:

Question 17

UTF8 is a type of .......... encoding.

• extended ASCII

Question 18

UTF32 is a type of .......... encoding.

Question 19

Which of the following is not a valid UTF8 representation?

• 2 octet (16 bits)
• 3 octet (24 bits)
• 4 octet (32 bits)
• 8 octet (64 bits) ✓

Question 20

Which of the following is not a valid encoding scheme for characters ?

Fill in the Blanks

The Decimal number system is composed of 10 unique symbols.

The Binary number system is composed of 2 unique symbols.

The Octal number system is composed of 8 unique symbols.

The Hexadecimal number system is composed of 16 unique symbols.

The illegal digits of octal number system are 8 and 9 .

Hexadecimal number system recognizes symbols 0 to 9 and A to F .

Each octal number is replaced with 3 bits in octal to binary conversion.

Each Hexadecimal number is replaced with 4 bits in Hex to binary conversion.

ASCII is a 7 bit code while extended ASCII is a 8 bit code.

The Unicode encoding scheme can represent all symbols/characters of most languages.

The ISCII encoding scheme represents Indian Languages' characters on computers.

UTF8 can take upto 4 bytes to represent a symbol.

UTF32 takes exactly 4 bytes to represent a symbol.

Unicode value of a symbol is called code point .

True/False Questions

A computer can work with Decimal number system. False

A computer can work with Binary number system. True

The number of unique symbols in Hexadecimal number system is 15. False

Number systems can also represent characters. False

ISCII is an encoding scheme created for Indian language characters. True

Unicode is able to represent nearly all languages' characters. True

UTF8 is a fixed-length encoding scheme. False

UTF32 is a fixed-length encoding scheme. True

UTF8 is a variable-length encoding scheme and can represent characters in 1 through 4 bytes. True

UTF8 and UTF32 are the only encoding schemes supported by Unicode. False

Type A: Short Answer Questions

What are some number systems used by computers ?

The most commonly used number systems are decimal, binary, octal and hexadecimal number systems.

What is the use of Hexadecimal number system on computers ?

The Hexadecimal number system is used in computers to specify memory addresses (which are 16-bit or 32-bit long). For example, a memory address 1101011010101111 is a big binary address but with hex it is D6AF which is easier to remember. The Hexadecimal number system is also used to represent colour codes. For example, FFFFFF represents White, FF0000 represents Red, etc.

What does radix or base signify ?

The radix or base of a number system signifies how many unique symbols or digits are used in the number system to represent numbers. For example, the decimal number system has a radix or base of 10 meaning it uses 10 digits from 0 to 9 to represent numbers.

What is the use of encoding schemes ?

Encoding schemes help Computers represent and recognize letters, numbers and symbols. It provides a predetermined set of codes for each recognized letter, number and symbol. Most popular encoding schemes are ASCI, Unicode, ISCII, etc.

Discuss UTF-8 encoding scheme.

UTF-8 is a variable width encoding that can represent every character in Unicode character set. The code unit of UTF-8 is 8 bits called an octet. It uses 1 to maximum 6 octets to represent code points depending on their size i.e. sometimes it uses 8 bits to store the character, other times 16 or 24 or more bits. It is a type of multi-byte encoding.

How is UTF-8 encoding scheme different from UTF-32 encoding scheme ?

UTF-8 is a variable length encoding scheme that uses different number of bytes to represent different characters whereas UTF-32 is a fixed length encoding scheme that uses exactly 4 bytes to represent all Unicode code points.

What is the most significant bit and the least significant bit in a binary code ?

In a binary code, the leftmost bit is called the most significant bit or MSB. It carries the largest weight. The rightmost bit is called the least significant bit or LSB. It carries the smallest weight. For example:

1 M S B 0 1 1 0 1 1 0 L S B \begin{matrix} \underset{\bold{MSB}}{1} & 0 & 1 & 1 & 0 & 1 & 1 & \underset{\bold{LSB}}{0} \end{matrix} MSB 1 ​ ​ 0 ​ 1 ​ 1 ​ 0 ​ 1 ​ 1 ​ LSB 0 ​ ​

What are ASCII and extended ASCII encoding schemes ?

ASCII encoding scheme uses a 7-bit code and it represents 128 characters. Its advantages are simplicity and efficiency. Extended ASCII encoding scheme uses a 8-bit code and it represents 256 characters.

What is the utility of ISCII encoding scheme ?

ISCII or Indian Standard Code for Information Interchange can be used to represent Indian languages on the computer. It supports Indian languages that follow both Devanagari script and other scripts like Tamil, Bengali, Oriya, Assamese, etc.

What is Unicode ? What is its significance ?

Unicode is a universal character encoding scheme that can represent different sets of characters belonging to different languages by assigning a number to each of the character. It has the following significance:

• It defines all the characters needed for writing the majority of known languages in use today across the world.
• It is a superset of all other character sets.
• It is used to represent characters across different platforms and programs.

What all encoding schemes does Unicode use to represent characters ?

Unicode uses UTF-8, UTF-16 and UTF-32 encoding schemes.

What are ASCII and ISCII ? Why are these used ?

ASCII stands for American Standard Code for Information Interchange. It uses a 7-bit code and it can represent 128 characters. ASCII code is mostly used to represent the characters of English language, standard keyboard characters as well as control characters like Carriage Return and Form Feed. ISCII stands for Indian Standard Code for Information Interchange. It uses a 8-bit code and it can represent 256 characters. It retains all ASCII characters and offers coding for Indian scripts also. Majority of the Indian languages can be represented using ISCII.

What are UTF-8 and UTF-32 encoding schemes. Which one is more popular encoding scheme ?

UTF-8 is a variable length encoding scheme that uses different number of bytes to represent different characters whereas UTF-32 is a fixed length encoding scheme that uses exactly 4 bytes to represent all Unicode code points. UTF-8 is the more popular encoding scheme.

What do you understand by code point ?

Code point refers to a code from a code space that represents a single character from the character set represented by an encoding scheme. For example, 0x41 is one code point of ASCII that represents character 'A'.

What is the difference between fixed length and variable length encoding schemes ?

Variable length encoding scheme uses different number of bytes or octets (set of 8 bits) to represent different characters whereas fixed length encoding scheme uses a fixed number of bytes to represent different characters.

Type B: Application Based Questions

Convert the following binary numbers to decimal:

Equivalent decimal number = 1 + 4 + 8 = 13

Therefore, (1101) 2 = (13) 10

Equivalent decimal number = 2 + 8 + 16 + 32 = 58

Equivalent decimal number = 1 + 2 + 4 + 8 + 16 + 64 + 256 = 351

Convert the following binary numbers to decimal :

Equivalent decimal number = 4 + 8 = 12

(b) 10010101

(c) 11011100

Convert the following decimal numbers to binary:

Therefore, (0.25) 10 = (0.01) 2

Therefore, (122) 10 = (1111010) 2

(We stop after 5 iterations if fractional part doesn't become 0)

Therefore, (0.675) 10 = (0.10101) 2

Convert the following decimal numbers to octal:

Therefore, (122) 10 = (172) 8

Therefore, (0.675) 10 = (0.53146) 8

Convert the following hexadecimal numbers to binary:

(23D) 16 = (1000111101) 2

Convert the following binary numbers to hexadecimal:

(a) 1010110110111

(b) 10110111011011

(c) 0110101100

0001 undefined 1010 undefined 1100 undefined \underlinesegment{0001} \quad \underlinesegment{1010} \quad \underlinesegment{1100} 0001 ​ 1010 ​ 1100 ​

Therefore, (0110101100) 2 = (1AC) 16

Convert the following octal numbers to decimal:

Equivalent decimal number = 7 + 40 + 128 = 175

Therefore, (257) 8 = (175) 10

Equivalent decimal number = 7 + 16 + 320 + 1536 = 1879

Therefore, (3527) 8 = (1879) 10

Equivalent decimal number = 3 + 16 + 64 = 83

Therefore, (123) 8 = (83) 10

Integral part

Fractional part.

Equivalent decimal number = 5 + 384 + 0.125 + 0.0312 = 389.1562

Therefore, (605.12) 8 = (389.1562) 10

Convert the following hexadecimal numbers to decimal:

Equivalent decimal number = 6 + 160 = 166

Therefore, (A6) 16 = (166) 10

Equivalent decimal number = 11 + 48 + 256 + 40960 = 41275

Therefore, (A13B) 16 = (41275) 10

Equivalent decimal number = 5 + 160 + 768 = 933

Therefore, (3A5) 16 = (933) 10

Equivalent decimal number = 9 + 224 = 233

Therefore, (E9) 16 = (233) 10

Equivalent decimal number = 3 + 160 + 3072 + 28672 = 31907

Therefore, (7CA3) 16 = (31907) 10

Convert the following decimal numbers to hexadecimal:

Therefore, (132) 10 = (84) 16

Therefore, (2352) 10 = (930) 16

Therefore, (122) 10 = (7A) 16

Therefore, (0.675) 10 = (0.ACCCC) 16

Therefore, (206) 10 = (CE) 16

Therefore, (3619) 10 = (E23) 16

Convert the following hexadecimal numbers to octal:

(38AC) 16 = (11100010101100) 2

011 undefined   100 undefined   010 undefined   101 undefined   100 undefined \underlinesegment{011}\medspace\underlinesegment{100}\medspace\underlinesegment{010}\medspace\underlinesegment{101}\medspace\underlinesegment{100} 011 ​ 100 ​ 010 ​ 101 ​ 100 ​

(38AC) 16 = (34254) 8

(7FD6) 16 = (111111111010110) 2

111 undefined   111 undefined   111 undefined   010 undefined   110 undefined \underlinesegment{111}\medspace\underlinesegment{111}\medspace\underlinesegment{111}\medspace\underlinesegment{010}\medspace\underlinesegment{110} 111 ​ 111 ​ 111 ​ 010 ​ 110 ​

(7FD6) 16 = (77726) 8

(ABCD) 16 = (1010101111001101) 2

001 undefined   010 undefined   101 undefined   111 undefined   001 undefined   101 undefined \underlinesegment{001}\medspace\underlinesegment{010}\medspace\underlinesegment{101}\medspace\underlinesegment{111}\medspace\underlinesegment{001}\medspace\underlinesegment{101} 001 ​ 010 ​ 101 ​ 111 ​ 001 ​ 101 ​

(ABCD) 16 = (125715) 8

Convert the following octal numbers to binary:

Therefore, (123) 8 = ( 001 undefined   010 undefined   011 undefined \bold{\underlinesegment{001}}\medspace\bold{\underlinesegment{010}}\medspace\bold{\underlinesegment{011}} 001 ​ 010 ​ 011 ​ ) 2

Therefore, (3527) 8 = ( 011 undefined   101 undefined   010 undefined   111 undefined \bold{\underlinesegment{011}}\medspace\bold{\underlinesegment{101}}\medspace\bold{\underlinesegment{010}}\medspace\bold{\underlinesegment{111}} 011 ​ 101 ​ 010 ​ 111 ​ ) 2

Therefore, (705) 8 = ( 111 undefined   000 undefined   101 undefined \bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{000}}\medspace\bold{\underlinesegment{101}} 111 ​ 000 ​ 101 ​ ) 2

Therefore, (7642) 8 = ( 111 undefined   110 undefined   100 undefined   010 undefined \bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{110}}\medspace\bold{\underlinesegment{100}}\medspace\bold{\underlinesegment{010}} 111 ​ 110 ​ 100 ​ 010 ​ ) 2

Therefore, (7015) 8 = ( 111 undefined   000 undefined   001 undefined   101 undefined \bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{000}}\medspace\bold{\underlinesegment{001}}\medspace\bold{\underlinesegment{101}} 111 ​ 000 ​ 001 ​ 101 ​ ) 2

Therefore, (3576) 8 = ( 011 undefined   101 undefined   111 undefined   110 undefined \bold{\underlinesegment{011}}\medspace\bold{\underlinesegment{101}}\medspace\bold{\underlinesegment{111}}\medspace\bold{\underlinesegment{110}} 011 ​ 101 ​ 111 ​ 110 ​ ) 2

Convert the following binary numbers to octal

111 undefined 010 undefined \underlinesegment{111} \quad \underlinesegment{010} 111 ​ 010 ​

Therefore, (111010) 2 = (72) 8

(b) 110110101

110 undefined 110 undefined 101 undefined \underlinesegment{110} \quad \underlinesegment{110} \quad \underlinesegment{101} 110 ​ 110 ​ 101 ​

Therefore, (110110101) 2 = (665) 8

(c) 1101100001

001 undefined 101 undefined 100 undefined 001 undefined \underlinesegment{001} \quad \underlinesegment{101} \quad \underlinesegment{100} \quad \underlinesegment{001} 001 ​ 101 ​ 100 ​ 001 ​

Therefore, (1101100001) 2 = (1541) 8

011 undefined 001 undefined \underlinesegment{011} \quad \underlinesegment{001} 011 ​ 001 ​

Therefore, (11001) 2 = (31) 8

(b) 10101100

010 undefined 101 undefined 100 undefined \underlinesegment{010} \quad \underlinesegment{101} \quad \underlinesegment{100} 010 ​ 101 ​ 100 ​

Therefore, (10101100) 2 = (254) 8

(c) 111010111

111 undefined 010 undefined 111 undefined \underlinesegment{111} \quad \underlinesegment{010} \quad \underlinesegment{111} 111 ​ 010 ​ 111 ​

Therefore, (111010111) 2 = (727) 8

Add the following binary numbers:

(i) 10110111 and 1100101

1 1 0 1 1 1 0 1 1 1 1 1 1 + 1 1 0 0 1 0 1 1 0 0 0 1 1 1 0 0 \begin{matrix} & & \overset{1}{1} & \overset{1}{0} & 1 & 1 & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & 1 \\ + & & & 1 & 1 & 0 & 0 & 1 & 0 & 1 \\ \hline & \bold{1} & \bold{0} & \bold{0} & \bold{0} & \bold{1} & \bold{1} & \bold{1} & \bold{0} & \bold{0} \end{matrix} + ​ 1 ​ 1 1 0 ​ 0 1 1 0 ​ 1 1 0 ​ 1 0 1 ​ 0 1 0 1 ​ 1 1 1 1 ​ 1 1 0 0 ​ 1 1 0 ​ ​

Therefore, (10110111) 2 + (1100101) 2 = (100011100) 2

(ii) 110101 and 101111

1 1 1 1 0 1 1 1 0 1 1 + 1 0 1 1 1 1 1 1 0 0 1 0 0 \begin{matrix} & & \overset{1}{1} & \overset{1}{1} & \overset{1}{0} & \overset{1}{1} & \overset{1}{0} & 1 \\ + & & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline & \bold{1} & \bold{1} & \bold{0} & \bold{0} & \bold{1} & \bold{0} & \bold{0} \end{matrix} + ​ 1 ​ 1 1 1 1 ​ 1 1 0 0 ​ 0 1 1 0 ​ 1 1 1 1 ​ 0 1 1 0 ​ 1 1 0 ​ ​

Therefore, (110101) 2 + (101111) 2 = (1100100) 2

(iii) 110111.110 and 11011101.010

0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 . 1 1 1 0 + 1 1 0 1 1 1 0 1 . 0 1 0 1 0 0 0 1 0 1 0 1 . 0 0 0 \begin{matrix} & & \overset{1}{0} & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & \overset{1}{1} & . & \overset{1}{1} & 1 & 0 \\ + & & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 1 & . & 0 & 1 & 0 \\ \hline & \bold{1} & \bold{0} & \bold{0} & \bold{0} & \bold{1} & \bold{0} & \bold{1} & \bold{0} & \bold{1} & \bold{.} & \bold{0} & \bold{0} & \bold{0} \end{matrix} + ​ 1 ​ 0 1 1 0 ​ 0 1 1 0 ​ 1 1 0 0 ​ 1 1 1 1 ​ 0 1 1 0 ​ 1 1 1 1 ​ 1 1 0 0 ​ 1 1 1 1 ​ . . . ​ 1 1 0 0 ​ 1 1 0 ​ 0 0 0 ​ ​

Therefore, (110111.110) 2 + (11011101.010) 2 = (100010101) 2

(iv) 1110.110 and 11010.011

0 1 1 1 1 1 1 0 1 . 1 1 1 0 + 1 1 0 1 0 . 0 1 1 1 0 1 0 0 1 . 0 0 1 \begin{matrix} & & \overset{1}{0} & \overset{1}{1} & \overset{1}{1} & 1 & \overset{1}{0} & . & \overset{1}{1} & 1 & 0 \\ + & & 1 & 1 & 0 & 1 & 0 & . & 0 & 1 & 1 \\ \hline & \bold{1} & \bold{0} & \bold{1} & \bold{0} & \bold{0} & \bold{1} & \bold{.} & \bold{0} & \bold{0} & \bold{1} \end{matrix} + ​ 1 ​ 0 1 1 0 ​ 1 1 1 1 ​ 1 1 0 0 ​ 1 1 0 ​ 0 1 0 1 ​ . . . ​ 1 1 0 0 ​ 1 1 0 ​ 0 1 1 ​ ​

Therefore, (1110.110) 2 + (11010.011) 2 = (101001.001) 2

Question 21

Given that A's code point in ASCII is 65, and a's code point is 97. What is the binary representation of 'A' in ASCII ? (and what's its hexadecimal representation). What is the binary representation of 'a' in ASCII ?

Binary representation of 'A' in ASCII will be binary representation of its code point 65.

Converting 65 to binary:

Therefore, binary representation of 'A' in ASCII is 1000001.

Converting 65 to Hexadecimal:

Therefore, hexadecimal representation of 'A' in ASCII is (41) 16 .

Similarly, converting 97 to binary:

Therefore, binary representation of 'a' in ASCII is 1100001.

Question 22

Convert the following binary numbers to decimal, octal and hexadecimal numbers.

(i) 100101.101

Decimal Conversion of integral part:

Decimal Conversion of fractional part:

Equivalent decimal number = 1 + 4 + 32 + 0.5 + 0.125 = 37.625

Therefore, (100101.101) 2 = (37.625) 10

Octal Conversion

100 undefined 101 undefined . 101 undefined \underlinesegment{100} \quad \underlinesegment{101} \quad \bold{.} \quad \underlinesegment{101} 100 ​ 101 ​ . 101 ​

Therefore, (100101.101) 2 = (45.5) 8

Hexadecimal Conversion

0010 undefined 0101 undefined   .   1010 undefined \underlinesegment{0010} \quad \underlinesegment{0101} \medspace . \medspace \underlinesegment{1010} 0010 ​ 0101 ​ . 1010 ​

Therefore, (100101.101) 2 = (25.A) 16

(ii) 10101100.01011

Equivalent decimal number = 4 + 8 + 32 + 128 + 0.25 + 0.0625 + 0.03125 = 172.34375

Therefore, (10101100.01011) 2 = (172.34375) 10

010 undefined 101 undefined 100 undefined . 010 undefined 110 undefined \underlinesegment{010} \quad \underlinesegment{101} \quad \underlinesegment{100} \quad \bold{.} \quad \underlinesegment{010} \quad \underlinesegment{110} 010 ​ 101 ​ 100 ​ . 010 ​ 110 ​

Therefore, (10101100.01011) 2 = (254.26) 8

1010 undefined 1100 undefined   .   0101 undefined   1000 undefined \underlinesegment{1010} \quad \underlinesegment{1100} \medspace . \medspace \underlinesegment{0101} \medspace \underlinesegment{1000} 1010 ​ 1100 ​ . 0101 ​ 1000 ​

Therefore, (10101100.01011) 2 = (AC.58) 16

Decimal Conversion:

Equivalent decimal number = 2 + 8 = 10

001 undefined 010 undefined \underlinesegment{001} \quad \underlinesegment{010} 001 ​ 010 ​

Therefore, (1010) 2 = (12) 8

(iv) 10101100.010111

Equivalent decimal number = 4 + 8 + 32 + 128 + 0.25 + 0.0625 + 0.03125 + 0.015625 = 172.359375

Therefore, (10101100.010111) 2 = (172.359375) 10

010 undefined 101 undefined 100 undefined . 010 undefined 111 undefined \underlinesegment{010} \quad \underlinesegment{101} \quad \underlinesegment{100} \quad \bold{.} \quad \underlinesegment{010} \quad \underlinesegment{111} 010 ​ 101 ​ 100 ​ . 010 ​ 111 ​

Therefore, (10101100.010111) 2 = (254.27) 8

1010 undefined 1100 undefined   .   0101 undefined   1100 undefined \underlinesegment{1010} \quad \underlinesegment{1100} \medspace . \medspace \underlinesegment{0101} \medspace \underlinesegment{1100} 1010 ​ 1100 ​ . 0101 ​ 1100 ​

Therefore, (10101100.010111) 2 = (AC.5C) 16

Data representation exercises

Exercises not as directly relevant to this year’s class are marked with ⚠️.

DATAREP-1. Sizes and alignments

QUESTION DATAREP-1A. True or false: For any non-array type X, the size of X ( sizeof(X) ) is greater than or equal to the alignment of type X ( alignof(X) ).

True. This also mostly true for arrays. The exception is zero-length arrays: sizeof(X[0]) == 0 , but alignof(X[0]) == alignof(X) .

QUESTION DATAREP-1B. True or false: For any type X, the size of struct Y { X a; char newc; } is greater than the size of X.

QUESTION DATAREP-1C. True or false: For any types A1 ... An (with n ≥ 1), the size of struct Y is greater than the size of struct X , given:

struct X { A1 a1; ... An an; };

struct Y { A1 a1; ... An an; char newc; };

False (example: A1 = int , A2 = char )

QUESTION DATAREP-1D. True or false: For any types A1 ... An (with n ≥ 1), the size of struct Y is greater than the size of union X , given:

union X { A1 a1; ... An an; };

struct Y { A1 a1; ... An an; };

False (if n = 1 )

QUESTION DATAREP-1E. Assume that structure struct Y { ... } contains K char members and M int members, with K ≤ M , and nothing else. Write an expression defining the maximum sizeof(struct Y) .

QUESTION DATAREP-1F. You are given a structure struct Z { T1 a; T2 b; T3 c; } that contains no padding. What does (sizeof(T1) + sizeof(T2) + sizeof(T3)) % alignof(struct Z) equal?

QUESTION DATAREP-1G. Arrange the following types in increasing order by size. Sample answer: “1 < 2 = 4 < 3” (choose this if #1 has smaller size than #2, which has equal size to #4, which has smaller size than #3).

• struct minipoint { uint8_t x; uint8_t y; uint8_t z; }
• unsigned short[1]

#6 < #1 < #4 < #2 < #3 < #5

DATAREP-2. Expressions

QUESTION DATAREP-2A. Here are eight expressions. Group the expressions into four pairs so that the two expressions in each pair have the same value, and each pair has a different value from every other pair. There is one unique answer that meets these constraints. m has the same type and value everywhere it appears (there’s one unique value for m that meets the problem’s constraints). Assume an x86-32 machine: a 32-bit architecture in which pointers are 32 bits long.

• sizeof(&m)
• 16 >> 2

1—5; 2—7; 3—8; 4—6 1—5 is easy. m + ~m + 1 == m + (-m) == 0 , and m & ~m == 0 , giving us 3—8. Now what about the others? m & -m (#3) is either 0 or a power of 2, so it cannot be -1 (#2). The remaining possiblities are m and 1 . If (m & -m) == m , then the remaining pair would be 1 and -1, which clearly doesn’t work. Thus m & -m matches with 1, and m == -1 .

DATAREP-3. Hello binary

This problem locates 8-bit numbers horizontally and vertically in the following 16x16 image. Black pixels represent 1 bits and white pixels represent 0 bits. For horizontal arrangements, the most significant bit is on the left as usual. For vertical arrangements, the most significant bit is on top.

Examples : The 8-bit number 15 (hexadecimal 0x0F, binary 0b00001111) is located horizontally at 3,4, which means X=3, Y=4.

• The pixel at 3,4 is white, which has bit value 0.
• 4,4 is white, also 0.
• 5,4 is white, also 0.
• 6,4 is white, also 0.
• 7,4 is black, which has bit value 1.
• 8,4, 9,4, and 10,4 are black, giving three more 1s.
• Reading them all off, this is 0b00001111, or 15.

15 is also located horizontally at 7,6.

The 8-bit number 0 is located vertically at 0,0. It is also located horizontally at 0,0 and 1,0.

The 8-bit number 134 (hexadecimal 0x86, binary 0b10000110) is located vertically at 8,4.

QUESTION DATAREP-3A. Where is 3 located vertically? (All questions refer to 8-bit numbers.)

QUESTION DATAREP-3B. Where is 12 located horizontally?

QUESTION DATAREP-3C. Where is 255 located vertically?

DATAREP-4. Hello memory

Shintaro Tsuji wants to represent the image of Question DATAREP-3 in computer memory. He stores it in an array of 16-bit unsigned integers:

Row Y of the image is stored in integer cute[Y] .

QUESTION DATAREP-4A. What is sizeof(cute) , 2, 16, 32, or 64?

QUESTION DATAREP-4B. printf("%d\n", cute[0]); prints 16384 . Is Shintaro’s machine big-endian or little-endian?

Little-endian

DATAREP-5. Hello program

Now that Shintaro has represented the image in memory as an array of unsigned short objects, he can manipulate the image using C. For example, here’s a function.

Running swap produces the following image:

Shintaro has written several other functions. Here are some images (A is the original):

For each function, what image does that function create?

QUESTION DATAREP-5A.

H. The code flips all bits in the input.

QUESTION DATAREP-5B.

QUESTION DATAREP-5C.

The following programs generated the other images. Can you match them with their images?

f3 —I; f4 —B; f5 —C; f6 —F; f7 —G; f8 —A; f9 —E

DATAREP-6. Memory regions

Consider the following program:

This program allocates objects a through g on the heap and then stores those pointers in some stack and global variables. We recommend you draw a picture of the state setup creates.

QUESTION DATAREP-6A. Assume that (uintptr_t) a == 0x8300000 , and that malloc returns increasing addresses. Match each address to the most likely expression with that address value. The expressions are evaluated within the context of main . You will not reuse an expression.

1—D; 2—C; 3—E; 4—B; 5—A Since p has automatic storage duration, it is located on the stack, giving us 5—A. The global variable has static storage duration, and so does its component global.y ; so the pointer &global.y has an address that is below all heap-allocated pointers. This gives us 2—C. The remaining expressions go like this: global.y == e ; p.y == &e[1] , so *p.y == e[1] == (int) &d[100000] , and (int *) *p.y == &d[100000] ; p.x == g , so p.x[0] == g[0] == *g == c , and *p.x[0] == *c == (int) a . Address #4 has value 0x8300000, which by assumption is a ’s address; so 4—B. Address #3 is much larger than the other heap addresses, so 3—E. This leaves 1—D.

DATAREP-7. ⚠️ Garbage collection ⚠️

⚠️ Here is the top-level function for the conservative garbage collector we wrote in class.

This garbage collector is not correct because it doesn’t capture all memory roots.

Consider the program from the previous section, and assume that an object is reachable if do_stuff can access an address within the object via variable references and memory dereferences without casts or pointer arithmetic . Then:

QUESTION DATAREP-7A. Which reachable objects will m61_collect() free? Circle all that apply.

b , f . The collector searches the stack for roots. This yields just the values in struct ptrs p (the only pointer-containing variable with automatic storage duration at the time m61_collect is called). The objects directly pointed to by p are g and e . The collector then recursively marks objects pointed to by these objects. From g , it finds c . From e , it finds nothing. Then it checks one more time. From c , it finds the value of a ! Now, a is actually not a pointer here—the type of *c is int —so by the definition above, a is not actually reachable. But the collector doesn’t know this. Putting it together, the collector marks a , c , e , and g . It won’t free these objects; it will free the others ( b , d , and f ). But b and f are reachable from global .

QUESTION DATAREP-7B. Which unreachable objects will m61_collect() not free? Circle all that apply.

QUESTION DATAREP-7C. Conservative garbage collection in C is often slower than precise garbage collection in languages such as Java. Why? Circle all that apply.

• C is generally slower than other languages.
• Conservative garbage collectors must search all reachable memory for pointers. Precise garbage collectors can ignore values that do not contain pointers, such as large character buffers.
• C programs generally use the heap more than programs in other languages.
• None of the above.

DATAREP-8. Memory errors

The following function constructs and returns a lower-triangular matrix of size N . The elements are random 2-dimensional points in the unit square. The matrix is represented as an array of pointers to arrays.

This code is running on an x86- 32 machine ( size_t is 32 bits , not 64). You may assume that the machine has enough free physical memory and the process has enough available virtual address space to satisfy any memory allocation request.

QUESTION DATAREP-8A. Give a value of N so that, while make_random_lt_matrix(N) is running, no new fails, but a memory error (such as a null pointer dereference or an out-of-bounds dereference) happens on Line A. The memory error should happen specifically when i == 1 .

(This problem is probably easier when you write your answer in hexadecimal.)

We are asked to produce a value of N so that no memory error happens on Line A when i == 0 , but a memory error does happen when i == 1 . So reason that through. What memory errors could happen on Line A if malloc() returns non- nullptr ? There’s only one memory operation, namely the dereference m[i] . Perhaps this dereference is out of bounds. If no memory error happens when i == 0 , then a m[0] dereference must not cause a memory error. So the m object must contain at least 4 bytes. But a memory error does happen on Line A when i == 1 . So the m object must contain less than 8 bytes. How many bytes were allocated for m ? sizeof(point2_vector) * N == sizeof(point2 *) * N == 4 * N . So we have: (4 * N) ≥ 4 (4 * N) < 8 It seems like the only possible answer is N == 1 . But no, this doesn’t cause a memory error, because the loop body would never be executed with i == 1 ! The key insight is that the multiplications above use 32-bit unsigned computer arithmetic. Let’s write N as X + 1 . Then these inequalities become: 4 ≤ 4 * (X + 1) = 4 * X + 4 < 8 0 ≤ (4 * X) < 4 (Multiplication distributes over addition in computer arithmetic.) What values of X satisfy this inequality? It might be easier to see if we remember that multiplication by powers of two is equivalent to shifting: 0 ≤ (X << 2) < 4 The key insight is that this shift eliminates the top two bits of X . There are exactly four values for X that work: 0 , 0x40000000 , 0x80000000 , and 0xC0000000 . For any of these, 4 * X == 0 in 32-bit computer arithmetic, because 4× X = 0 (mod 2 32 ) in normal arithmetic. Plugging X back in to N , we see that N ∈ {0x40000001, 0x80000001, 0xC0000001} . These are the only values that work. Partial credit was awarded for values that acknowledged the possibility of overflow.

QUESTION DATAREP-8B. Give a value of N so that no new fails, and no memory error happens on Line A, but a memory error does happen on Line B.

If no memory error happens on Line A, then N < 2 30 (otherwise overflow would happen as seen above). But a memory error does happen on Line B. Line B dereferences m[i][j] , for 0 ≤ j ≤ i ; so how big is m[i] ? It was allocated on Line A with size `sizeof(point2) (i + 1) == 2 * sizeof(double) * (i + 1) == 16 * (i + 1) . If i + 1 ≥ 2<sup>32</sup> / 16 = 2<sup>28</sup>, this multiplication will overflow. Since i < N , we can finally reason that any N greater than or equal to 2<sup>28</sup> = 0x10000000 and less than 2<sup>30</sup> = 0x40000000` will cause the required memory error.

DATAREP-9. Data representation

Assume a 64-bit x86-64 architecture unless explicitly told otherwise.

Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.

QUESTION DATAREP-9A. Arrange the following values in increasing numeric order. Assume that x is an int with value 8192.

A possible answer might be “a < b < c = d < e < f < g < h.”

h < a = d = f < b < c < e < g

For each of the remaining questions, write one or more arguments that, when passed to the provided function, will cause it to return the integer 61 (which is 0x3d hexadecimal ). Write the expected number of arguments of the expected types.

QUESTION DATAREP-9B.

QUESTION DATAREP-9C.

"61"

QUESTION DATAREP-9D. Your answer should be different from the previous answer.

" 0x3d" , " 61 " , etc.

QUESTION DATAREP-9E. For this problem, you will also need to define a global variable. Give its type and value.

This code was compiled from: int f4 ( int a, int b) { extern unsigned char y; return (a & 5 ) * 2 + b - y; } A valid solution is a =0, b =61, unsigned char y =0.

DATAREP-10. Sizes and alignments

QUESTION DATAREP-10A. Use the following members to create a struct of size 16, using each member exactly once, and putting char a first; or say “impossible” if this is impossible.

• char a; (we’ve written this for you)
• unsigned char b;

QUESTION DATAREP-10B. Repeat Part A, but create a struct with size 12.

abdc, acbd, acdb, adbc, adcb, …

QUESTION DATAREP-10C. Repeat Part A, but create a struct with size 8.

QUESTION DATAREP-10D. Consider the following structs:

Give definitions for T, U, and V so that there is one byte of padding in struct x after x2 , and two bytes of padding in struct y after y1 .

Example: T = short[2] , U = char , V = int

DATAREP-11. Dynamic memory allocation

QUESTION DATAREP-11A. True or false?

• free(nullptr) is an error.
• malloc(0) can never return nullptr .

False, False

QUESTION DATAREP-11B. Give values for sz and nmemb so that calloc(sz, nmemb) will always return nullptr (on a 32-bit x86 machine), but malloc(sz * nmemb) might or might not return null.

(size_t) -1, (size_t) -1 —anything that causes an overflow

Consider the following 8 statements. ( p and q have type char* .)

• q = nullptr;
• p = (char*) malloc(12);
• q = (char*) malloc(8);

QUESTION DATAREP-11C. Put the statements in an order that would execute without error or evoking undefined behavior. Memory leaks count as errors. Use each statement exactly once. Sample answer: “abcdefgh.”

cdefghab (and others). Expect “OK”

QUESTION DATAREP-11D. Put the statements in an order that would cause one double-free error, and no other error or undefined behavior (except possibly one memory leak). Use each statement exactly once.

efghbcad (and others). Expect “double-free + memory leak”

QUESTION DATAREP-11E. Put the statements in an order that would cause one memory leak (one allocated piece of memory is not freed), and no other error or undefined behavior. Use each statement exactly once.

efghadbc (and others). Expect “memory leak”

QUESTION DATAREP-11F. Put the statements in an order that would cause one boundary write error, and no other error or undefined behavior. Use each statement exactly once.

eafhcgbd (and others). Expect “out of bounds write”

DATAREP-12. Pointers and debugging allocators

You are debugging some students’ m61 code from Problem Set 1. The codes use the following metadata:

Their linked-list manipulations in m61_malloc are similar.

But their linked-list manipulations in m61_free differ.

Alice’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next != nullptr ) { m -> next -> prev = m -> prev; } if (m -> prev == nullptr ) { mhead = nullptr ; } else { m -> prev -> next = m -> next; } ... }

Bob’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next) { m -> next -> prev = m -> prev; } if (m -> prev) { m -> prev -> next = m -> next; } ... }

Chris’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; m -> next -> prev = m -> prev; m -> prev -> next = m -> next; ... }

Donna’s code: void m61_free ( void * ptr, ...) { ... meta * m = (meta * ) ptr - 1 ; if (m -> next) { m -> next -> prev = m -> prev; } if (m -> prev) { m -> prev -> next = m -> next; } else { mhead = m -> next; } ... }

You may assume that all code not shown is correct.

QUESTION DATAREP-12A. Whose code will segmentation fault on this input? List all students that apply.

QUESTION DATAREP-12B. Whose code might report something like “ invalid free of pointer [ptr1], not allocated ” on this input? (Because a list traversal starting from mhead fails to find ptr1 .) List all students that apply. Don’t include students whose code would segfault before the report.

QUESTION DATAREP-12C. Whose code would improperly report something like “ LEAK CHECK: allocated object [ptr1] with size 1 ” on this input? (Because the mhead list appears not empty, although it should be.) List all students that apply. Don’t include students whose code would segfault before the report.

QUESTION DATAREP-12D. Whose linked-list code is correct for all inputs? List all that apply.

DATAREP-13. Arena allocation

Chimamanda Ngozi Adichie is a writing a program that needs to allocate and free a lot of nodes, where a node is defined as follows:

She uses an arena allocator variant. Here’s her code.

QUESTION DATAREP-13A. True or false?

• This allocator never has external fragmentation.
• This allocator never has internal fragmentation.

QUESTION DATAREP-13B. Chimamanda’s frenemy Paul Auster notices that if many nodes are allocated right in a row, every 1024th allocation seems much more expensive than the others. The reason is that every 1024th allocation initializes a new group, which in turn adds 1024 nodes to the free list. Chimamanda decides instead to allow a single element of the free list to represent many contiguous free nodes . The average allocation might get a tiny bit slower, but no allocation will be much slower than average. Here’s the start of her idea:

Complete this function by writing code to replace // ??? .

if (n -> key == 1 ) { a -> frees = n -> right; } else { a -> frees = n + 1 ; a -> frees -> key = n -> key - 1 ; a -> frees -> right = n -> right; } Another solution: if (n -> right) { a -> frees = n -> right; } else if (n -> key == 1 ) { a -> frees = NULL ; } else { a -> frees = n + 1 ; a -> frees -> key = n -> key - 1 ; }

QUESTION DATAREP-13C. Write a node_free function that works with the node_alloc function from the previous question.

void node_free (arena * a, node * n) { n -> right = a -> frees; n -> key = 1 ; a -> frees = n; } Or, if you use the solution above: void node_free (arena * a, node * n) { n -> right = a -> frees; a -> frees = n; }

QUESTION DATAREP-13D. Complete the following new function.

arena_group * node_find_group (arena * a, node * n) { for (arena_group * g = a -> groups; g; g = g -> next_group) { if ((uintptr_t) & g -> nodes[ 0 ] <= (uintptr_t) n && (uintptr_t) n <= (uintptr_t) & g -> nodes[ 1023 ]) { return g; } } return nullptr ; }

QUESTION DATAREP-13E. Chimamanda doesn’t like that the node_find_group function from part D takes O ( G ) time, where G is the number of allocated arena_groups. She remembers a library function that might help, posix_memalign :

The function posix_memalign() allocates size bytes and places the address of the allocated memory in *memptr . The address of the allocated memory will be a multiple of alignment , which must be a power of two and a multiple of sizeof(void*) . ...

“Cool,” she says, “I can use this to speed up node_find_group !” She now allocates a new group with the following code:

Given this allocation strategy, write a version of node_find_group that takes O (1) time.

arena_group * node_find_group (arena * a, node * n) { uintptr_t n_addr = (uintptr_t) n; return (arena_group * ) (n_addr - n_addr % 32768 ); }

DATAREP-14. Data representation

Sort the following expressions in ascending order by value, using the operators <, =, >. For example, if we gave you:

• int B = 0x6;

you would write C < A = B .

• unsigned char a = 0x191;
• char b = 0x293;
• unsigned long c = 0xFFFFFFFF;
• int d = 0xFFFFFFFF;
• int e = d + 3;
• size_t g = sizeof(*s) (given short *s )
• long h = 256;
• i = 0b100000000000000000000000000000000000 (binary)
• unsigned long j = 0xACE - 0x101;

b < d < e = g < a < h < j < c < f < i

DATAREP-15. Memory

For the following questions, select the part(s) of memory from the list below that best describes where you will find the object.

• between the heap and the stack
• in a read-only data segment
• in a text segment starting at address 0x08048000
• in a read/write data segment
• in a register

Assume the following code, compiled without optimization.

QUESTION DATAREP-15A. The value 0xdeadbeef, when we are returning from main.

7, in a register

QUESTION DATAREP-15B. The variable maxitems

4, in a read-only data segment

QUESTION DATAREP-15C. The structure s

6, in a read/write data segment

QUESTION DATAREP-15D. The structure at sp[9]

QUESTION DATAREP-15E. The variable u

2, stack, or 7, in a register

QUESTION DATAREP-15F. main

5, in a text segment starting at address 0x08048000

QUESTION DATAREP-15G. printf

3, between the heap and the stack

QUESTION DATAREP-15H. argc

QUESTION DATAREP-15I. The number the user enters

QUESTION DATAREP-15J. The variable L

DATAREP-16. Memory and pointers

⚠️ This question may benefit from Unit 4, kernel programming. ⚠️

If multiple processes are sharing data via mmap , they may have the file mapped at different virtual addresses. In this case, pointers to the same object will have different values in the different processes. One way to store pointers in mmapped memory so that multiple processes can access them consistently is using relative pointers. Rather than storing a regular pointer, you store the offset from the beginning of the mmapped region and add that to the address of the mapping to obtain a real pointer. An alternative representation is called self-relative pointers. In this case, you store the difference in address between the current location (i.e., the location containing the pointer) and the location to which you want to point. Neither representation addresses pointers between the mmapped region and the rest of the address space; you may assume such pointers do not exist.

QUESTION DATAREP-16A. State one advantage that relative pointers have over self-relative pointers.

The key thing to understand is that both of these approaches use relative pointers and both can be used to solve the problem of sharing a mapped region among processes that might have the region mapped at different addresses. Possible advantages: Within a region, you can safely use memcpy as moving pointers around inside the region does not change their value. If you copy a self relative pointer to a new location, its value has to change. That is, imagine that you have a self-relative pointer at offset 4 from the region and it points to the object at offset 64 from the region. The value of the self relative pointer is 60. If I copy that pointer to the offset 100 from the region, I have to change it to be -36. If you save the region as a uintptr_t or a char * , then you can simply add the offset to the region; self-relative-pointers will always be adding/subtracting from the address of the location storing the pointer, which may have a type other than char * , so you'd need to cast it before performing the addition/subtraction. You can use a larger region: if we assume that we have only N bits to store the pointer, then in the base+offset model, offset could be an unsigned value, which will be larger than the maximum offset possible with a signed pointer, which you need for the self-relative case. That is, although the number of values that can be represented by signed and unsigned numbers differs by one, the implementation must allow for a pointer from the beginning of the region to reference an item at the very last location of the region -- thus, your region size is limited by the largest positive number you can represent.

QUESTION DATAREP-16B. State one advantage that self-relative pointers have over relative pointers.

You don't have to know the address at which the region is mapped to use them. That is, given a location containing a self-relative pointer, you can find the target of that pointer.

For the following questions, assume the following setup:

QUESTION DATAREP-16C. Propose a type for TYPE1 and give 1 sentence why you chose that type.

A good choice is ptrdiff_t , which represents differences between pointers. Other reasonable choices include uintptr_t and unsigned long .

QUESTION DATAREP-16D. Write a C expression to generate a (properly typed) pointer to the element referenced by the r_next field of ll1 .

(ll1*) (region + node1.r_next)

QUESTION DATAREP-16E. Propose a type for TYPE2 and give 1 sentence why you chose that type.

The same choices work; again ptrdiff_t is best.

QUESTION DATAREP-16F. Write a C expression to generate a (properly typed) pointer to the element referenced by the sr_next field of ll2 .

(ll2*) ((char*) &node2.sr_next + node2.sr_next)

DATAREP-17. Data representation: Allocation sizes

How much user-accessible space is allocated on the stack and/or the heap by each of the following statements? Assume x86-64.

QUESTION DATAREP-17A. union my_union { ... };

0; this declares the type , not any object

QUESTION DATAREP-17B. void* p = malloc(sizeof(char*));

16: 8 on the heap plus 8 on the stack

QUESTION DATAREP-17C. my_union u;

16 (on the stack)

QUESTION DATAREP-17D. my_union* up = &u;

8 (on the stack)

DATAREP-18. Data representation: ENIAC

Professor Kohler has been developing Eddie’s NIfty Awesome Computer (ENIAC). When he built the C compiler for ENIAC, he assigned the following sizes and alignments to C’s fundamental data types. (Assume that every other fundamental type has the same size and alignment as one of these.)

QUESTION DATAREP-18A. This set of sizes is valid: it obeys all the requirements set by C’s abstract machine. Give one different size assignment that would make the set as a whole invalid.

Some examples: sizeof(char) = 0 ; sizeof(char) = 2 ; sizeof(short) = 8 (i.e., longer than int ); sizeof(int) = 2 (though not discussed in class, turns out that C++ requires ints are at least 2 bytes big); etc.

QUESTION DATAREP-18B. What alignment must the ENIAC malloc guarantee?

For the following two questions, assume the following struct on the ENIAC:

QUESTION DATAREP-18C. What is sizeof(struct s) ?

f1 is 7 bytes. f2 is 16 bytes with 16-byte alignment, so add 9B padding. f3 is 4 bytes (and is already aligned). f4 is 8 bytes with 8-byte alignment, so add 4B padding. That adds up to 7 + 9 + 16 + 4 + 4 + 8 = 16 + 16 + 16 = 48 bytes. That’s a multiple of the structure’s alignment, which is 16, so no need for any end padding.

QUESTION DATAREP-18D. What is alignof(struct s) ?

The remaining questions refer to this structure definition:

Indicate for each statement whether the statement is always true, possibly true, or never true on the ENIAC.

QUESTION DATAREP-18E : sizeof(outer) > sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18F : sizeof(outer) is a multiple of sizeof(inner) (Always / Possibly / Never)

QUESTION DATAREP-18G : alignof(outer) > alignof(struct inner) (Always / Possibly / Never)

QUESTION DATAREP-18H : sizeof(outer) - sizeof(inner) < 4 (Always / Possibly / Never)

QUESTION DATAREP-18I : sizeof(outer) - sizeof(inner) > 32 (Always / Possibly / Never)

QUESTION DATAREP-18J : alignof(inner) == 2 (Always / Possibly / Never)

DATAREP-19. Undefined behavior

Which of the following expressions, instruction sequences, and code behaviors cause undefined behavior? For each question, write Defined or Undefined. (Note that the INT_MAX and UINT_MAX constants have types int and unsigned , respectively.)

QUESTION DATAREP-19A. INT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19B. UINT_MAX + 1 (Defined / Undefined)

QUESTION DATAREP-19C.

(Defined / Undefined)

Defined (only C++ programs can have undefined behavior; the behavior of x86-64 instructions is always defined)

QUESTION DATAREP-19D. Failed memory allocation, i.e., malloc returns nullptr (Defined / Undefined)

QUESTION DATAREP-19E. Use-after-free (Defined / Undefined)

QUESTION DATAREP-19F. Here are two functions and a global variable:

C’s undefined behavior rules would allow an aggressive optimizing compiler to simplify the code generated for f . Fill in the following function with the simplest C code you can, under the constraint that an aggressive optimizing compiler might generate the same object code for f and f_simplified .

return i * 2;

DATAREP-20. Bit manipulation

It’s common in systems code to need to switch data between big-endian and little-endian representations. This is because networks represent multi-byte integers using big-endian representation, whereas x86-family processors store multi-byte integers using little-endian representation.

QUESTION DATAREP-20A. Complete this function, which translates an integer from big-endian representation to little-endian representation by swapping bytes. For instance, big_to_little(0x01020304) should return 0x04030201 . Your return statement must refer to the u.c array, and must not refer to x . This function is compiled on x86-64 Linux (as every function is unless we say otherwise).

return (u.c[ 0 ] << 24 ) | (u.c[ 1 ] << 16 ) | (u.c[ 2 ] << 8 ) | u.c[ 3 ];

QUESTION DATAREP-20B. Complete the function again, but this time write a single expression that refers to x (you may refer to x multiple times, of course).

return ((x & 0xFF ) << 24 ) | ((x & 0xFF00 ) << 8 ) | ((x & 0xFF0000 ) >> 8 ) | (x >> 24 );

QUESTION DATAREP-20C. Now write the function little_to_big , which will translate a little-endian integer into big-endian representation. You may introduce helper variables or even call big_to_little if that’s helpful.

return big_to_little (x);

DATAREP-21. Computer arithmetic

Bitwise operators and computer arithmetic can represent vectors of bits, which in turn are useful for representing sets . For example, say we have a function bit that maps elements to distinct bits; thus, bit(X) == (1 << i) for some i . Then a set {X0, X1, X2, …, Xn} can be represented as bit(X0) | bit(X1) | bit(X2) | … | bit(Xn) . Element Xi is in the set with integer representation z if and only if (bit(Xi) & z) != 0 .

QUESTION DATAREP-21A. What is the maximum number of set elements that can be represented in a single unsigned variable on an x86 machine?

QUESTION DATAREP-21B. Match each set operation with the C operator(s) that could implement that operation. (Complement is a unary operation.)

intersection & equality == complement ~ union | toggle membership ^

QUESTION DATAREP-21C. Complete this function, which should return the set difference between the sets with representations a and b . This is the set containing exactly those elements of set a that are not in set b .

Any of these work: return a & ~ b; return a - (a & b); return a & ~ (a & b);

QUESTION DATAREP-21D. Below we’ve given a number of C++ expressions, some of their values, and some of their set representations for a set of elements. For example, the first row says that the integer value of expression 0 is just 0, which corresponds to an empty set. Fill in the blanks. This will require figuring out which bits correspond to the set elements A , B , C , and D , and the values for the 32-bit int variables a , x , and s . No arithmetic operation overflows; abs(x) returns the absolute value of x (that is, x < 0 ? -x : x ).

Expression e Integer value Represented set 0 0 {} a == a 1 {A} (unsigned) ~a < (unsigned) a 1 {A} a < 0 1 {A} (1 << (s/2)) - 1 15 {A,B,C,D} a * a 4 {C} abs(a) 2 {D} x & (x - 1) 0 {} x - 1 3 {A,D} x 4 {C} s 8 {B}

DATAREP-22. Bit Tac Toe

Brenda Bitdiddle is implementing tic-tac-toe using bitwise arithmetic. (If you’re unfamiliar with tic-tac-toe, see below.) Her implementation starts like this:

Each position on the board is assigned a distinct bit.

Tic-tac-toe, also known as noughts and crosses, is a simple paper-and-pencil game for two players, X and O. The board is a 3x3 grid. The players take turns writing their symbol (X or O) in an empty square on the grid. The game is won when one player gets their symbol in all three squares in one of the rows, one of the columns, or one of the two diagonals. X goes first; played perfectly, the game always ends in a draw. You may access the Wikipedia page for tic-tac-toe .

QUESTION DATAREP-22A. Brenda’s current code doesn’t check whether a move reuses a position. Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3.

Lots of people misinterpreted this to mean the player reused their own position and ignored the other player. That mistake was allowed with no points off. The code below checks whether any position was reused by either player. if ((b -> moves[XS] | b -> moves[OS]) & ttt_values[row][col]) { return - 1 ; } OR if ((b -> moves[XS] | b -> moves[OS] | ttt_values[row][col]) == (b -> moves[XS] | b -> moves[OS])) { return - 1 ; } OR if ((b -> moves[XS] + b -> moves[OS]) & ttt_values[row][col]) { return - 1 ; } OR if ((b -> moves[p] ^ ttt_values[row][col]) < b -> moves[p]) { return - 1 ; } etc.

QUESTION DATAREP-22B. Complete the following function. You may use the following helper function:

• int popcount(unsigned n) Return the number of 1 bits in n . (Stands for “population count”; is implemented on recent x86 processors by a single instruction, popcnt .)

For full credit, your code should consist of a single “ return ” statement with a simple expression, but for substantial partial credit write any correct solution.

return popcount (b -> moves[XS] | b -> moves[OS]);

QUESTION DATAREP-22C. Write a simple expression that, if nonzero, indicates that player XS has a win on board b across the main diagonal (has marks in positions 0,0 , 1,1 , and 2,2 ).

(b -> moves[XS] & 0x421 ) == 0x421

Lydia Davis notices Brenda’s code and has a brainstorm. “If you use different values,” she suggests, “it becomes easy to detect any win.” She suggests:

QUESTION DATAREP-22D. Repeat part A for Lydia’s values: Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3 in Brenda’s code.

The same answers as for part A work.

QUESTION DATAREP-22E. Repeat part B for Lydia’s values: Use popcount to complete tictactoe_nmoves .

Either of: return popcount ((b -> moves[ 0 ] | b -> moves[ 1 ]) & 0x777 ); return popcount ((b -> moves[ 0 ] | b -> moves[ 1 ]) & 0x777000 );

QUESTION DATAREP-22F. Complete the following function for Lydia’s values. For full credit, your code should consist of a single “ return ” statement containing exactly two constants, but for substantial partial credit write any correct solution.

return (b -> moves[p] + 0x11111111 ) & 0x88888888 ; // Another amazing possibility (Allen Chen and others): return b -> moves[p] & (b -> moves[p] << 1 ) & (b -> moves[p] << 2 );

DATAREP-23. Memory and Pointers

Two processes are mapping a file into their address space. The mapped file contains an unsorted linked list of integers. As the processes cannot ensure that the file will be mapped at the same virtual address, they use relative pointers to link elements in the list. A relative pointer holds not an address, but an offset that user code can use to calculate a true address. Our processes define the offset as relative to the start of the file.

Thus, each element in the linked list is represented by the following structure:

offset == (size_t) -1 indicates the end of the list. Other offset values represent the position of the next item in the list, calculated relative to the start of the file.

QUESTION DATAREP-23A. Write a function to find an item in the list. The function's prototype is:

The mapped_file parameter is the address of the mapped file data; the list parameter is a pointer to the first node in the list; and the value parameter is the value for which we are searching. The function should return a pointer to the linked list element if the value appears in the list or nullptr if the value is not in the list.

ll_node * find_element ( void * mapped_file, ll_node * list, int value) { while ( 1 ) { if (list -> value == value) return list; if (list -> offset == (size_t) - 1 ) return NULL ; list = (ll_node * ) (( char * ) mapped_file + list -> offset); } }

DATAREP-24. Integer representation

Write the value of the variable or expression in each problem, using signed decimal representation.

For example, if we gave you:

• int i = 0xA;
• int j = 0xFFFFFFFF;

you would write A) 10 B) -1.

QUESTION DATAREP-24A. int i = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

2 16 - 1 or 65535

QUESTION DATAREP-24B. short s = 0xFFFF; (You may write this either in decimal or as an expression using a power of 2)

QUESTION DATAREP-24C. unsigned u = 1 << 10;

1024 or 2 10

QUESTION DATAREP-24D. ⚠️ From WeensyOS: unsigned long l = PTE_P | PTE_U;

QUESTION DATAREP-24E. int j = ~0;

QUESTION DATAREP-24F. ⚠️ From WeensyOS: sizeof(x86_64_pagetable);

4096 or 2 12

QUESTION DATAREP-24G. Given this structure:

This expression: sizeof(ps);

TRICK QUESTION! 8

QUESTION DATAREP-24H. Using the structure above: sizeof(*ps);

QUESTION DATAREP-24I. unsigned char u = 0xABC;

0xBC == 11*16 + 12 == 160 + 16 + 12 == 188

QUESTION DATAREP-24J. signed char c = 0xABC;

0xBC has most-significant bit on, so the value as a signed char is less than zero. We seek x so that 0xBC + x == 0x100 . The answer is 0x44: 0xBC + 4 == 0xC0 , and 0xC0 + 0x40 == 0x100 . So −0x44 == −4*16 − 4 == −68 .

DATAREP-25. Data representation

In gdb, you observe the following values for a set of memory locations.

For each C expression below, write its value in hexadecimal. For example, if we gave you:

the answer would be 0xa0 .

Assume the following structure and union declarations and variable definitions.

QUESTION DATAREP-25A. cp[4] =

QUESTION DATAREP-25B. cp + 7 =

0x100001027

QUESTION DATAREP-25C. s1 + 1 =

0x100001038

QUESTION DATAREP-25D. s1->i =

0xd3c2b1a0 (-742215264)

QUESTION DATAREP-25E. sizeof(s1) =

QUESTION DATAREP-25F. &s2->s =

0x100001028

QUESTION DATAREP-25G. &u->s =

0x100001020

QUESTION DATAREP-25H. s1->l =

0x9f8e7d6c5b4a3928 (-6949479270644565720)

QUESTION DATAREP-25I. s2->s.s =

0xf201 (-3583)

QUESTION DATAREP-25J. u->l =

0x1706f5e4d3c2b1a0 (1659283875886707104)

DATAREP-26. Sizes and alignments

Here’s a test struct with n members. Assume an x86-64 machine, where each Ti either is a basic x86-64 type (e.g., int , char , double ) or is a type derived from such types (e.g., arrays, structs, pointers, unions, possibly recursively), and assume that ai ≤8 for all i .

In these questions, you will compare this struct with other structs that have the same members, but in other orders.

QUESTION DATAREP-26A. True or false: The size of struct test is minimized when its members are sorted by size. In other words, if s1 ≤ s2 ≤…≤ sn , then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample (i.e., concrete types for T1 , …,  Tn that do not minimize sizeof(struct test) ).

False. T1 = char , T2 = int , T3 = char[5]

QUESTION DATAREP-26B. True or false: The size of struct test is minimized when its members are sorted by alignment. In other words, if a1 ≤ a2 ≤…≤ an , then sizeof(struct test) is less than or equal to the struct size for any other member order.

If true, briefly explain your answer; if false, give a counterexample.

True. Padding only occurs between objects with different alignments, and is limited by the second alignment; sorting by alignment therefore minimizes padding.

QUESTION DATAREP-26C. True or false: The alignment of struct test is minimized when its members are sorted in increasing order by alignment. In other words, if a1 ≤ a2 ≤…≤ an , then alignof(struct test) is less than or equal to the struct alignment for any other member order.

True. It’s all the same; alignment is max alignment of every component, and is independent of order.

QUESTION DATAREP-26D. What is the maximum number of bytes of padding that struct test could contain for a given n ? The answer will be a pretty simple formula involving n . (Remember that ai ≤8 for all i .)

Alternating char and long gives the most padding, which is 7*(n/2) when n is even and 7*(n+1)/2 otherwise.

QUESTION DATAREP-26E. What is the minimum number of bytes of padding that struct test could contain for a given n ?

DATAREP-27. Undefined behavior

QUESTION DATAREP-27A. Sometimes a conforming C compiler can assume that a + 1 > a , and sometimes it can’t. For each type below, consider this expression:

and say whether the compiler:

• Must reject the expression as a type error.
• May assume that the expression is true (that a + (int) 1 > a for all a ).
• Must not assume that the expression is true.
• unsigned char a
• struct {int m;} a

1—May assume; 2—Must not assume; 3—May assume; 4—May assume (in fact due to integer promotion, this statement really is always true, even in mathematical terms); 5—Must reject.

QUESTION DATAREP-27B. The following code checks its arguments for sanity, but not well: each check can cause undefined behavior.

Rewrite these checks to avoid all undefined behavior. You will likely add one or more casts to uintptr_t . For full credit, write each check as a single comparison (no && or || , even though the current ptr_into_array check uses || ).

array_size check:

ptr_into_array check:

array_size check: (uintptr_t) array + 4 * array_size < (uintptr_t) array ptr_into_array check: (uintptr_t) ptr_into_array - (uintptr_t) array > 4 * array_size

QUESTION DATAREP-27C. In lecture, we discussed several ways to tell if a signed integer x is negative. One of them was the following:

But this is incorrect: it has undefined behavior. Correct it by adding two characters.

(x & (1UL << (sizeof(x) * CHAR_BIT - 1))) != 0

DATAREP-28. ⚠️ Memory errors and garbage collection ⚠️

⚠️ We didn’t discuss garbage collectors in class this year.

Recall that a conservative garbage collector is a program that can automatically free dynamically-allocated memory by detecting when that memory is no longer referenced. Such a GC works by scanning memory for currently-referenced pointers, starting from stack and global memory, and recursing over each referenced object until all referenced memory has been scanned. We built a conservative garbage collector in lecture datarep6.

QUESTION DATAREP-28A. An application program that uses conservative GC, and does not call free directly, will avoid certain errors and undefined behaviors. Which of the following errors are avoided? List all that apply.

• Use-after-free
• Double free
• Signed integer overflow
• Boundary write error
• Unaligned access

QUESTION DATAREP-28B. Write a C program that leaks unbounded memory without GC, but does not do so with GC. You should need less than 5 lines. (Leaking “unbounded” memory means the program will exhaust the memory capacity of any machine on which it runs.)

while ( 1 ) { ( void ) malloc( 1 ); }

QUESTION DATAREP-28C. Not every valid C program works with a conservative GC, because the C abstract machine allows a program to manipulate pointers in strange ways. Which of the following pointer manipulations might cause the conservative GC from class to inappropriately free a memory allocation? List all that apply.

Storing the pointer in a uintptr_t variable

Writing the pointer to a disk file and reading it back later

Using the least-significant bit of the pointer to store a flag:

Storing the pointer in textual form:

Splitting the pointer into two parts and storing the parts in an array:

DATAREP-29. Bitwise

QUESTION DATAREP-29A. Consider this C fragment:

Or, shorter:

Write a single expression that evaluates to the same value, but that does not use the conditional ?: operator. You will use the fact that a < b always equals 0 or 1. For full credit, do not use expensive operators (multiply, divide, modulus).

Examples: (a < b) * x , (-(uintptr_t) (a < b)) & x

QUESTION DATAREP-29B. This function returns one more than the index of the least-significant 1 bit in its argument, or 0 if its argument is zero.

This function runs in O ( B ) time, where B is the number of bits in an unsigned long . Write a version of ffs that runs instead in O (log  B ) time.

int ffs ( unsigned long x) { if ( ! x) { return 0 ; } int ans = 1 ; if ( ! (x & 0x00000000FFFFFFFFUL )) { ans += 32 ; x >>= 32 ; } if ( ! (x & 0x0000FFFF )) { ans += 16 ; x >>= 16 ; } if ( ! (x & 0x00FF )) { ans += 8 ; x >>= 8 ; } if ( ! (x & 0x0F )) { ans += 4 ; x >>= 4 ; } if ( ! (x & 0x3 )) { ans += 2 ; x >>= 2 ; } return ans + (x & 0x1 ? 0 : 1 ); }

DATAREP-30. Data representation

QUESTION DATAREP-30A. Write a type whose size is 19,404,329 times larger than its alignment.

char[19404329]

QUESTION DATAREP-30B. Consider a structure type T with N members, all of which have nonzero size. Assume that sizeof(T) == alignof(T) . What is N ?

QUESTION DATAREP-30C. What is a C type that obeys (T) -1 == (T) 255 on x86-64?

char (or unsigned char or signed char )

Parts D–G use this code. The architecture might or might not be x86-64.

Assume that (uintptr_t) s2 - (uintptr_t) s1 == 4 and *s1 > *s2 .

QUESTION DATAREP-30D. What is sizeof(a) ?

QUESTION DATAREP-30E. What is sizeof(unsigned) on this architecture?

QUESTION DATAREP-30F. Is this architecture big-endian or little-endian?

QUESTION DATAREP-30G. Might the architecture be x86-64?

DATAREP-31. Memory errors

Mavis Gallant is starting on her debugging memory allocator. She’s written code that aims to detect invalid frees, where a pointer passed to m61_free was not returned by an earlier m61_malloc .

Help her track down bugs.

QUESTION DATAREP-31A. What is sizeof(struct m61_metadata) ?

QUESTION DATAREP-31B. Give an m61_ function call (function name and arguments) that would cause both unsigned integer overflow and invalid memory accesses.

m61_malloc((size_t) -15) . This turns into malloc(1) and the dereference of meta->magic becomes invalid.

QUESTION DATAREP-31C. Give an m61_ function call (function name and arguments) that would cause integer overflow, but no invalid memory access within the m61_ functions . (The application might or might not make an invalid memory access later.)

m61_malloc((size_t) -1)

QUESTION DATAREP-31D. These functions have some potential null pointer dereferences. Fix one such problem, including the line number(s) where your code should go.

C3: if (p) { memset(p, 0, sz * count); }

QUESTION DATAREP-31E. Put a single line of C code in the blank. The resulting program should (1) be well-defined with no memory leaks when using default malloc / free / calloc , but (2) always cause undefined behavior when using Mavis’s debugging malloc / free / calloc .

free(nullptr);

QUESTION DATAREP-31F. A double free should print a different message than an invalid free. Write code so Mavis’s implementation does this; include the line numbers where the code should go.

F4: fprintf(stderr, meta->magic == 0xB0B0B0B0 ? "double free of %p" : "invalid free of %p", ptr) after F6: meta->magic = 0xB0B0B0B0;

DATAREP-32. Memory word search

QUESTION DATAREP-32A. What is decimal 61 in hexadecimal?

0x3d, 2 pts

The following is a partial dump of an x86-64 Linux program’s memory. Note that each byte is represented as a hexadecimal number. Memory addresses increase from top to bottom and from left to right.

QUESTION DATAREP-32B. What memory segment contains the memory dump?

Data segment (globals), 2 pts

For questions 3C–3I, give the last two digits of the address of the given object in this memory dump (so for the object located at address 0x6010a8, you would write “a8”). There’s a single best answer for every question, and all questions have different answers .

QUESTION DATAREP-32C. A long (64 bits) of value 61.

QUESTION DATAREP-32D. A long of value -61.

QUESTION DATAREP-32E. An int of value 61.

QUESTION DATAREP-32F. A pointer to an object in the heap.

QUESTION DATAREP-32G. A pointer to a local variable.

QUESTION DATAREP-32H. A pointer that points to an object present in the memory dump.

QUESTION DATAREP-32I. The first byte of a C string comprising at least 4 printable ASCII characters. (Printable ASCII characters have values from 0x20 to 0x7e.)

DATAREP-33. Architecture

QUESTION DATAREP-33A. Write a C++ expression that will evaluate to false on all typical 32-bit architectures and true on all typical 64-bit architectures.

3pts sizeof(void*) == 8

QUESTION DATAREP-33B. Give an integer value that has the same representation in big-endian and little-endian, and give its C++ type. Assume the same type sizes as x86-64.

2pts ex: int x = 0

QUESTION DATAREP-33C. Repeat question B, but with a different integer value.

2pts ex: int x = -1 :)

QUESTION DATAREP-33D. Complete this C++ function, which should return true iff it is called on a machine with little-endian integer representation. Again, you may assume the same type sizes as x86-64.

3pts bool is_little_endian () { union { int a; char c[ 4 ]; } u; u.a = 0 ; u.c[ 0 ] = 1 ; return u.a == 1 ; }

DATAREP-34. Undefined behavior

The following code is taken from the well-known textbook Mastering C Pointers (with some stylistic changes). Assume it is run on x86-64.

QUESTION DATAREP-34A. List all situations in which this program will not execute undefined behavior. (There is at least one.)

3pts If malloc returns nullptr .

QUESTION DATAREP-34B. True or false? The expression ++x could be replaced with ++y without changing the meaning of the program.

3pts True! The undefined behavior is the same either way.

Here’s an updated version of the program.

QUESTION DATAREP-34C. True or false? The expression *(x + y) could be replaced with x[y] without changing the meaning of the program.

QUESTION DATAREP-34D. True or false? The expression *(x + y) could be replaced by * (int*) ((uintptr_t) x + y) without changing the meaning of the program.

3pts False (address arithmetic isn’t the same for pointer arithmetic, except for pointers with type equivalent to char )

DATAREP-35. Odd alignments

QUESTION DATAREP-35A. Write a struct definition that contains exactly seven bytes of padding on x86-64.

3pts struct {long a; char b;}

QUESTION DATAREP-35B. Can an x86-64 struct comprise more than half padding? Give an example if so, or explain briefly why not.

3pts Yes. struct {char a; long b; char c;} has size 24 and 14 bytes of padding.

The remaining questions consider a new architecture called x86-64-rainbow , which is like x86-64 plus special support for a fundamental data type called color . A color is a three-byte data type with red, green, and blue components, kind of like this:

But unlike struct color on x86-64, which has size 3 and alignment 1, color on x86-64-rainbow has size 3 and alignment 3 . All the usual rules for C abstract machine sizes and alignments still hold.

QUESTION DATAREP-35C. What is the alignment of pointers returned by malloc on x86-64-rainbow?

QUESTION DATAREP-35D. Give an example of an x86-64-rainbow struct that ends with more than 16 bytes of padding.

2pts struct { long a[2]; color b[3]; } has alignment lcm(8, 3) = 24 and size 8 + 8 + 3 + 3 + 3 = 25, so it ends with 23 bytes of padding!

DATAREP-36. Debugging allocators

In problem set 1, you built a debugging allocator that could detect many kinds of error. Some students used exclusively internal metadata , where the debugging allocator’s data was stored within the same block of memory as the payload. Some students used external metadata , such as a separate hash table mapping payload pointers to metadata information.

QUESTION DATAREP-36A. Which kind of error mentioned by the problem set could not be detected by external metadata alone?

2pts Boundary write errors.

The problem set requires the m61 library to detect invalid frees, which includes double frees. However, double frees are so common that a special double-free error message can help users. Jia Tolentino wants to print such a message. Her initial idea is to keep a set of recently freed pointers:

QUESTION DATAREP-36B. What eviction policy is used for the recently_freed array?

2pts FIFO (round-robin).

Jia uses these helpers in m61_free as follows. (You may assume that is_invalid_free(ptr) returns true for every invalid or double free.)

She has not yet changed m61_malloc , though she knows she needs to. Help her evaluate whether her design achieves the following mandatory and desirable (that is, optional) requirements.

Note : As you saw in tests 32 and 33 in pset 1, aggressive attacks from users can corrupt metadata arbitrarily. You should assume for the following questions that such aggressive attacks do not occur. The user might free something that was never allocated, and might double-free something, but will never overwrite metadata.

QUESTION DATAREP-36C. Mandatory : The design must not keep unbounded, un-reusable state for pointers that have been freed. Write “Achieved” or “Not achieved” and explain briefly.

6 pts for C-E together. +5 if one serious error; +3 if two serious errors Achieved. The design only keeps space for 10 recently-freed pointers.

QUESTION DATAREP-36D. Desirable : The design should report a double-free as a double-free, not an invalid free. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. If a pointer falls off the list after 10 frees, Jia’s design will report a double-free of that pointer as an invalid free.

QUESTION DATAREP-36E. Mandatory : The design must never report valid frees as double-frees or invalid frees. Write “Achieved” or “Not achieved” and explain briefly.

Not achieved. A recently-freed pointer can be reused by malloc, but she hasn’t accounted for that. So if (1) a pointer is freed, (2) a malloc returns the same pointer, (3) the user frees that pointer again, that valid free will be reported as a double free.

QUESTION DATAREP-36F. Describe code to be added to m61_malloc that will achieve all mandatory requirements, if any are required.

3pts Here’s the cleanest solution to the 4E problem. Remove returned pointers from recently_freed . Add this code to malloc before return ptr : for ( int i = 0 ; i != 10 ; ++ i) { if (recently_freed[i] == ptr) { recently_freed[i] = nullptr ; } }

DATAREP-37. Representations

Your job in the following questions is to complete each C++ program so that it prints 61 to standard output when run. Your answer should fill in the blank _________ , and you may assume system calls execute without error. If a question cannot be answered so that the program reliably prints 61 with no undefined behavior, say so and explain briefly.

To compile these programs, use a command line such as c++ -std=gnu++17 -pthread x.cc .

QUESTION DATAREP-37A.

QUESTION DATAREP-37B.

61L or (long) 61 are best; 61 will cause a compiler warning, because it’s an int and the format expects a long .

QUESTION DATAREP-37C.

6 * 16 + 1 , 0x61 , 97

QUESTION DATAREP-37D.

157 , - x + 61 , 96 + 61

QUESTION DATAREP-37E.

char c[61];

QUESTION DATAREP-37F.

This cannot be done. struct sixtyfun has minimum alignment of 4 (because int has alignment 4), so its size must be a multiple of 4.

QUESTION DATAREP-37G.

Anything with size 20, such as char c[20]; or int x[5]; .

QUESTION DATAREP-37H.

int a = 255, b = 0, c = 61; int a = -1, b = 0 (or anything ≤31), c = 61; unsigned a = 0x10000, b = 12, c = 0xFF; int a = 32, b = 1, c = 63; There are many other possibilities!

QUESTION DATAREP-37I.

This cannot be done without undefined behavior, because y is computed using an uninitialized variable.

QUESTION DATAREP-37J.

Anything that adds 15 total to x[0] … x[2] . For example, 5

QUESTION DATAREP-37K.

{ "echo", "61", nullptr }

QUESTION DATAREP-37L.

dup2(pfd[0], 0); close(pfd[0]); close(pfd[1]); The sleep(3) , which is not waitpid , makes many other solutions work too. dup2(pfd[0], 0); works; pipe hygiene isn't important because the parent exits. printf("61\n"); almost works, but something weird happens on Mac OS X.

QUESTION DATAREP-37M.

waitpid(p, nullptr, 0)

QUESTION DATAREP-37N. Note that there are three blanks to fill in with code (you may also leave them empty).

#1, #3: nothing. #2: std::unique_lock<std::mutex> guard(m); If the lock is in #1 (and there is no unlock in #3), that causes deadlock.

NCERT Books and Solutions for all classes

Data Representation Class 11 Computer Science Exam Questions

Please refer to Data Representation Class 11 Computer Science Exam Questions provided below. These questions and answers for Class 11 Computer Science have been designed based on the past trend of questions and important topics in your class 11 Computer Science books. You should go through all Class 11 Computer Science Important Questions provided by our teachers which will help you to get more marks in upcoming exams.

Class 11 Computer Science Exam Questions Data Representation

Class 11 Computer Science students should read and understand the important questions and answers provided below for Data Representation which will help them to understand all important and difficult topics.

Very Short answer Type Questions

Question: Covert the following Decimal numbers to binary – (a) 23 (b) 100 (c) 161 (d) 145 Answer:  (a) 10111 (b) 1100100 (c) 10100001 (d) 10010001

Question: Convert 111110111101012 to octal. Answer:  37365

Question: Covert the following Octal numbers to Binary – (a) 456 (b) 26 (c) 751 (d) 777 Answer:  (a) 100101110 (b) 010110 (c) 111101001 (d)111111111

Question: Covert the following binary numbers to Hexadecimal – (a)101000001 (b) 11100011 (c) 10101111 (d) 101101111 Answer:  (a) 141 (b) E3 (c) AF (d)16F

Question: Covert the following binary numbers to decimal – (a)1010 (b) 111000 (c) 10101111 (d) 10110 Answer:  (a) 10 (b) 56 (c) 175 (d) 22

Question: Add the binary numbers (a) 110101 and 101111 (b) 10110 and 1101 Answer:  (a) 1100100 (b) 100011

Question:  Covert the following Hexadecimal numbers to Binary – (a) BE (b) BC9 (c) A07 (d) 7AB4 Answer:  (a)10111110 (b) 101111001001 (c) 101000000111 (d) 0111101010110100

Question: Convert the following: (a) 4468 to ( )16 (b) 47.58 to ( )10 (c) 45.910 to ( )2 Answer:  (a) 126 (b) 39.625 (c) 101101.1110

Short Answer Type Questions  

Question: How UTF-8 encoding scheme different from UTF-32 encoding scheme? Answer:  UTF-8: Variable-width encoding, backwards compatible with ASCII. ASCII characters (U+0000 to U+007F) take 1 byte, code points U+0080 to U+07FF take 2 bytes, code points U+0800 to U+FFFF take 3 bytes, code points U+10000 to U+10FFFF take 4 bytes. Good for English text, not so good for Asian text. UTF-32 uses 32-bit values for each character. That allows them to use a fixed-width code for every character. UTF-32 is opposite, it uses the most memory (each character is a fixed 4 bytes wide), but on the other hand, you know that every character has this precise length, so string manipulation becomes far simpler. You can compute the number of characters in a string simply from the length in bytes of the string. You can’t do that with UTF-8.

Question: What are ASCII and extended ASCII schemes? Answer:The standard ASCII  character set uses just 7 bits for each character. There are severallarger character sets that use 8 bits, which gives them 128 additional characters. The extra characters are used to represent non-English characters, graphics symbols, and mathematical symbols.

The extended ASCII  character set uses 8 bits, which gives it an additional 128 characters. The extra characters represent characters from foreign languages and special symbols for drawing pictures.

Question: What is the use of encoding schemes? Answer:  A character encoding provides a key to unlock (ie. crack) the code. It is a set of mappingsbetween the bytes in the computer and the characters in the character set. Without the key, thedata looks like garbage. So, when you input text using a keyboard or in some other way, the character encoding mapscharacters you choose to specific bytes in computer memory, and then to display the text itreads the bytes back into characters. Unfortunately, there are many different character sets and character encodings, ie. many different ways of mapping between bytes, code points and characters. The section Additional information provides a little more detail for those who are interested.

Question: What is Unicode? What is its significance? Answer:  Unicode is a character encoding standard that has widespread acceptance. Microsoft software uses Unicode at its core. Whether you realize it or not, you are using Unicode already! Basically, ―computers just deal with numbers. They store letters and other characters by assigning a number for each one. Before Unicode was invented, there were hundreds of different encoding systems for assigning these numbers. No single encoding could contain enough characters.1‖ This has been the problem we, in SIL, have often run into. If you are using a legacy encodingyour font conflicts with the font someone in another area of the world uses. You might have an in your font while someplace else someone used a at the same codepoint. Your files are  incompatible. Unicode provides a unique number for every character and so you do not have this problem if you use Unicode. If your document calls for U+0289 it will be clear to any computer program what the character should be

Question: Discuss UTF-8 encoding Scheme. Answer:  UTF-8 is a compromise character encoding that can be as compact as ASCII (if the file is just plain English text) but can also contain any unicode characters (with some increase in file size). UTF stands for Unicode Transformation Format. The ‘8’ means it uses 8-bit blocks to represent a character.

Question: What is the utility of ISCII encoding schemes? Prepared By: Sanjeev Bhadauria & Neha Tyagi Answer:  ISCII is a bilingual character encoding (not glyphs) scheme. Roman characters and punctuation marks as defined in the standard lower-ASCII take up the first half the character set (first 128 slots). Characters for indie languages are allocated to the upper slots (128-255). T

Question: What are ASCII and ISCII? Why are these used? Answer:  ASCII uses a 7-bit encoding and ISCII uses an 8-bit which is an extension of ASCII. These are encoding schemes to represent character set in s computer system.

Question: What do you understand by code point and code unit? Answer:  A code point is the atomic unit of information. … Each code point is a number which is given meaning by the Unicode standard. A code unit is the unit of storage of a part of anencoded code point. In UTF-8 this means 8-bits, in UTF-16 this means 16-bits.

Question: What is code space? How is it related to code point? Answer:  In computing, Code space may refer to: In memory address space: code space, where machine code is stored. For a character encoding: code space (or code space), the range of code points.

Question: Compare UTF-8 and UTF-32 encoding schemes. Which one is most popular scheme? Answer: UTF-8:  Variable-width encoding, backwards compatible with ASCII. ASCII characters (U+0000 to U+007F) take 1 byte, code points U+0080 to U+07FF take 2 bytes, code points U+0800 to U+FFFF take 3 bytes, code points U+10000 to U+10FFFF take 4 bytes. Good for English text, not so good for Asian text. UTF-32  uses 32-bit values for each character. That allows them to use a fixed-width code for every character. UTF-32 is opposite, it uses the most memory (each character is a fixed 4 bytes wide), but on the other hand, you know that every character has this precise length, so string manipulation becomes far simpler. You can compute the number of characters in a string simply from the length in bytes of the string. You can’t do that with UTF-8.

We hope you liked the above provided Data Representation Class 11 Computer Science Exam Questions. If you have any further questions please put them in the comments section below so that our teachers can provide you an answer.

Related Posts:

Related Posts

Plant growth and development class 11 biology exam questions, transport in plants class 11 biology exam questions.

Table Creation And Data Manipulation Commands Class 11 Computer Science Exam Questions

Have an account?

GCSE Computer Science Data Representatio...

GCSE Computer Science Data Representation

25 questions

Introducing new   Paper mode

No student devices needed.   Know more

• 1. Multiple Choice Edit 30 seconds 1 pt Convert 254 to binary 11110000 11111100 11111111 11111110
• 2. Multiple Choice Edit 20 seconds 1 pt Convert 00010001 to decimal 17 27 37 47
• 3. Multiple Choice Edit 20 seconds 1 pt Convert 11111111 to decimal 255 245 235 225
• 4. Multiple Choice Edit 1 minute 12 pts Convert 01000100 to decimal 58 68 78 88
• 5. Multiple Choice Edit 10 seconds 1 pt What two digits are used in binary? 0 & 2 1&2 0&1 1&1
• 6. Multiple Choice Edit 10 seconds 1 pt Binary is also known as Base 1 Base 2 Base 10 Base jumping
• 7. Multiple Choice Edit 10 seconds 1 pt A single 0 or 1 is known as a Bit Byte Nibble Binary
• 8. Multiple Choice Edit 10 seconds 1 pt How many bits are there in a byte? 2 4 8 10
• 9. Multiple Choice Edit 20 seconds 1 pt The numbers we normally use are called ________ numbers and have 10 different values. denary binary digital integers
• 10. Multiple Choice Edit 30 seconds 1 pt A9 1010 1011 1010 1001 1001 1001 1110 0101
• 11. Multiple Choice Edit 30 seconds 1 pt 1101 1110 ED DE EC CE
• 12. Multiple Choice Edit 1 minute 1 pt Convert 85 into Hexadecimal 01010101 55 5A A5
• 13. Multiple Choice Edit 1 minute 1 pt What is the answer to 0110 + 0101? 1011 1101 1110 1111
• 14. Multiple Choice Edit 30 seconds 1 pt How does increasing colour depth affect an image file? Increases number of colours in image Increases resolution of image Increases image width Decreases metadata for an image 
• 15. Multiple Choice Edit 45 seconds 1 pt What sample rate do most CDs have? 44.1kHz 50,000Hz 40.2kHz 4Hz
• 16. Multiple Choice Edit 1 minute 1 pt What is bit depth? Number of bits assigned to each sample Rate at which the binary is calculated How deep the sound can go The speed of the sound wave
• 17. Multiple Choice Edit 10 seconds 1 pt What is ASCII? How the internet displays images A character set A programming language Binary information on the computer
• 18. Multiple Choice Edit 10 seconds 1 pt ASCII stands for… What doesn't it stand for? All Symbolic Computer Instructions Interchange Alternative Standard Computers Interchange Internet American Standard Code for Information Interchange
• 19. Multiple Choice Edit 30 seconds 1 pt What is a pixel? Tiny squares of colour on a screen. A fairy like creature thatlives in a forest. A whole picture. A binary code.
• 20. Multiple Choice Edit 30 seconds 1 pt The higher the colour depth, the _________the image file size. Smaller Larger

How many megabytes in a gigabyte?

Which of these is accurate for smallest to largest?

Kilobyte, Megabyte, Gigabyte, Terabyte

Megabyte, Kilobyte, Terabyte, Gigabyte

Gigabyte, Kilobyte, Terabyte, Megabyte

Terabyte, Gigabyte, Megabyte, Kilobyte

• 23. Multiple Choice Edit 45 seconds 1 pt Makes the file smaller by deleting parts of the file permanently (forever) Lossy Compression Lossless Compression
• 24. Multiple Choice Edit 30 seconds 1 pt Data compression usually works by.. Finding repeating patterns. Deleting random bits data
• 25. Multiple Choice Edit 30 seconds 1 pt What type of compression would you use to compress a text file? Lossy Lossless

Explore all questions with a free account

Continue with email

Continue with phone

JOIN ADRE 2.0 Telegram Group

By gkseries see more questions, data representation | computer system organization objective questions with answers.

• Computer Science /
• data representation

Computer Organization multiple choice questions and answers set contain 5 mcqs on number system and data representation in computer science. Each quiz objective question has 4 options as possible answers. Choose your option and check it with the given correct answer.

View Answer Comment

Answer: Option [C]

23D -> 0010 0011 1101 and 9AA -> 1001 1010 1010

So the sum of two hexadecimal numbers is 1011 1110 0111 i.e. BE7

Answer: Option [D]

37 H means 00110111

17 H means 00010111

On division of 37 H by 17 H the remainder is 09 H

DOWNLOAD CURRENT AFFAIRS PDF FROM APP

• 10 Important Books for UPSC Preparation
• 10 Important Books For SSC CGL, CPO, CHSL, and GD CONSTABLE Exam Preparation

Answer: Option [A]

31 can be represented by 5 bits and the 1 bit needed for sign bit.

2 n -1 is the largest integer in 2's complement representation using n bits.

Answer: Option [B]

-2 15 is the least negative value for the two 8-bit 2's complement numbers.

ADRE 2.0 Free Mock Tests

Adre 2.0 full length mock test, take mock tests.

• Digital Logic Circuits
• Digital Components
• Data Representation
• Register Transfer and Microoperations
• Assembly Language Programming
• Central Processing Unit
• Pipeline and Vector Processing
• Computer Arithmetic
• Input-Output Organization
• Memory Organization

Random GK Questions

Advertisement.

Computer Science Data Representation Quiz Questions & Answers - 1

• computer-quiz
• computer quiz
• computer organisation

Question: 1

To convert a decimal number into its octal equivalent

(A) the decimal number is divided by 8

(B) the decimal number is multiplied by 8

(C) the decimal number is divided by 16

(D) the decimal number is multiplied by 16

the decimal number is divided by 8

Question: 2

What is the base or radix of the decimal number system?

Question: 3

(D) 10 bits

Question: 4

Which is not a valid memory unit?

Question: 5

The binary numbers are ____ used in Binary Numeral System.

Error Report!

• data communication
• Computer Science Data Representation Quiz Questions & Answers
• Top 1000+ Computer Aptitude Notes for Bank Exams Pdf
• Top 1000+ Computer Capsule for IBPS, SBI, RRB, RBI, PO, Clerk Mains

REGISTER TO GET FREE UPDATES

2024 © MeritNotes

Help | Advanced Search

Computer Science > Computation and Language

Title: can large language models make the grade an empirical study evaluating llms ability to mark short answer questions in k-12 education.

Abstract: This paper presents reports on a series of experiments with a novel dataset evaluating how well Large Language Models (LLMs) can mark (i.e. grade) open text responses to short answer questions, Specifically, we explore how well different combinations of GPT version and prompt engineering strategies performed at marking real student answers to short answer across different domain areas (Science and History) and grade-levels (spanning ages 5-16) using a new, never-used-before dataset from Carousel, a quizzing platform. We found that GPT-4, with basic few-shot prompting performed well (Kappa, 0.70) and, importantly, very close to human-level performance (0.75). This research builds on prior findings that GPT-4 could reliably score short answer reading comprehension questions at a performance-level very close to that of expert human raters. The proximity to human-level performance, across a variety of subjects and grade levels suggests that LLMs could be a valuable tool for supporting low-stakes formative assessment tasks in K-12 education and has important implications for real-world education delivery.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .