Task: Sets
You will solve the exercises starting from the sets.asm
file located in the tasks/sets
directory.
You need to implement operations on sets that can contain elements between 0 and 31. An efficient way to do this (both in terms of space and speed) would be to represent sets so that a register represents a set. Each bit in the register represents an element in the set (if bit i is set, then the set contains element i).
TIP: For example: if
eax
contains the representation of the set{0, 2, 4}
, the register value would be2^0 + 2^2 + 2^4 = 1 + 4 + 16 = 21
. Educate yourself about the available instructions on the x86 architecture.
-
You have two defined sets. What values do they contain? You do not need to make the code print the actual values stored in the sets. Perform the union of the two sets.
-
Use the
or
instruction to add two new elements to the first set (the set stored in theeax
register).
NOTE: Do not reset the
eax
register after this exercise. Its new value will be the one used by the checker for further evaluation.TIP: Take advantage of the fact that the current sets, although they have “space” for 32 bits, only use 8 bits. If you
or
with a number greater than 255 (0xff
,2^8-1
) which has two active bits, you will effectively add two new elements to the set.
-
Perform the intersection of the two sets.
-
Determine the elements missing from the
eax
set for it to be complete.
TIP: You need to take the complement of the number using the
not
instruction.
- Remove an element from the first set (the set stored in the
eax
register).
NOTE: Do not reset the
eax
register after this exercise. Its new value will be the one used by the checker for further evaluation.
- Find the difference between the sets.
NOTE: In order for the checker to be able to check your results, you should be displaying the values in the order they are stated here.
To test the implementation, enter the tests/
directory and run:
./run_all_tests.sh
test_reunion ........................ passed ... 10
test_add_value_in_first_set ........................ passed ... 20
test_intersection ........................ passed ... 10
test_missing_elements_first_set ........................ passed ... 20
test_remove_element_first_set ........................ passed ... 20
test_difference ........................ passed ... 20
========================================================================
Total: 100/100
NOTE : If you wish to test for various sets, just change their values at line
6
and7
respectively insupport/sets.asm
to whatever you desire (that whatever should fit in 4 bytes, of course :-) ).
If you’re having difficulties solving this exercise, go through this reading material.