CSCI 2122 Lab 3: Bit Manipulation
Objective:
In this lab, you will write and use some bit manipulation routines to practice your C programming skills.
Preparation
1. Complete Assignment 0 or ensure that the tools you would need to complete it are installed.
2. Locate the man pages for these Standard C Library functions and bookmark them for the lab
• scanf()
• printf()
3. Clone your lab repository:
https://git.cs.dal.ca/courses/2023-fall/csci-2122/lab-03/????.git
where ???? is your CSID. Please see instructions in Assignment 0 and the tutorials on Brightspace if you are not sure how.
Inside the repository there are three directories: problem1, problem2, and problem3, in which the code is to be written. Inside each of these directories there is a tests directory that contains tests that will be executed each time you submit your code. Please do not modify the tests directories or the .gitlab-ci.yml file that is found in the root directory. Modifying these files may break the tests. These files will be replaced with originals when the lab is graded.
Resources
Tutorials on Brightspace
The Man pages on timberlea or https://man7.org/linux/man-pages/man3/intro.3.html
Procedure
Set-up
1. Each of the directories, problem1, problem2, and problem3 contains a problem to be solved in this lab. Prepare these directories for writing code, just like you did for Lab 1.
2. Prepare to work on Problem 1.
Part 1: Problem 1: Implement a bitmap
3. Read the description of Problem 1 below and solve the problem by writing the bitmap module in bitmap.c in the problem1 directory. A test program (main.c) is provided for you to test your code. The files bitmap.c and bitmap.h are set up for you to use.
4. Commit and push your submission.
5. Check if your program is working by looking at the tests in gitlab:
https://git.cs.dal.ca/courses/2023-fall/csci-2122/lab-03/????/-/pipelines where ???? is your CSID.
6. If any of the tests 0 – 4 fail, fix bitmap.c and resubmit before moving to the next part.
Part 2: Use the bitmaps
7. Copy the files bitmap.c and bitmap.h that you wrote in Problem 1 into problem2 the directory.
8. Read the description of Problem 2 below and solve the problem by writing the C program in main.c in the problem2 directory. For this problem you will need to use scanf() and printf(), as well as the bitmap routines.
9. Commit and push your submission.
10. Check if your program is working by looking at the tests in gitlab:
https://git.cs.dal.ca/courses/2023-fall/csci-2122/lab-03/????/-/pipelines where ???? is your CSID.
11. If any of the tests 5 – 9 fail, fix your program and resubmit before moving to the next part.
Part 3: Longest Sequence
12. Copy the files bitmap.c and bitmap.h that you wrote in Problem 1 into problem3 the directory.
13. Read the description of Problem 3 below and solve the problem by writing the C program in main.c in the problem3 directory. For this problem you will also use scanf() and printf(), and the bitmap routines. Hint: The input processing is the same as Problem 2.
14. Commit and push your submission.
15. Check if your program is working by looking at the tests in gitlab:
https://git.cs.dal.ca/courses/2023-fall/csci-2122/lab-03/????/-/pipelines where ???? is your CSID.
16. If any of the tests 10 – 14 fail, fix your program and resubmit.
17. You’re done!
Problem Descriptions
Problem 1
A bitmap is a simple compact data structure for storing sets of integers. A bitmap is a series of bits, stored in an array of bytes. A bitmap of N bits uses éN/8ù bytes to store the bits, where byte 0 … 7 is stored in byte 0, bit 8 … 15 is stored in byte 1, and so on.
A bitmap has several standard operations:
int bitmap_test(char *bitmap, int i): return value of bit i in bitmap.
void bitmap_set(char *bitmap, int i): set bit i in bitmap to 1.
void bitmap_reset(char *bitmap, int i): set bit i in bitmap to 0.
void bitmap_toggle(char *bitmap, int i): flip value of bit i in bitmap.
Implement these functions in bitmap.c. Note, the function
char *bitmap_new(int size)
is provided for you. A test program is provided that tests the bitmap. You do not need to modify the test program. This is what the test program does.
Test Program Input:
All input is done from stdin. The program reads commands from the console. The commands are:
• new <size> : create a new bitmap to store size bits.
• test <i> : print out bit i in the bitmap
• set <i> : set bit i to 1 in the bitmap
• reset <i> : set bit i to 0 in the bitmap
• toggle <i> : flip bit i in the bitmap
See example below.
Test Program Processing
For each command perform the corresponding operation on the bitmap.
Test Program Output
All output should be to stdout. For each command, except the test command, print out the bitmap by printing out the bytes in hexadecimal:
B0 B1 B2 … Bn
where Bi is byte i of the bitmap and terminate each line with newline (\n). For the test command, print out the value of the bit and terminate with a newline..
Input:
new 10
set 5
toggle 7
toggle 9
reset 5
test 7
Output: 00 00
20 00
a0 00
a0 02
80 02
1
Problem 2
Write a program called problem2 (in main.c) that reads in a set of integers and prints out all integers that appeared an odd number of times in the input.
Input:
All input is done from stdin. The input consists of
• Two integers, M the maximum integer to be read and N the number of integers to follow.
• Followed by N integers between 0 and M.
(See example.)
Processing
Your program should instantiate a bitmap (see Problem 1, main.c, for example). For each integer read, if the integer is not in the bitmap, it is inserted. If the integer is in the bitmap, it is removed from the bitmap. Once all the integers are processed, output the integers that are in the bitmap in increasing order.
Output
All output should be to stdout. Output a single line, terminated by a newline in the following
format:
Odd: i X2 … Xk
where Xi are the integers in the bitmap in increasing order.
Input:
10 7
2
1
2
4
5
4 Output:
Odd: 1 4 5
Problem 3
Write a program called problem3 (in main.c) that reads in a set of integers and prints out the longest continuous sequence contained in the set.
Input:
Same format as Problem 2.
Processing
Your program should instantiate a bitmap (see Problem 1, main.c, for example). For each integer read, the integer is added to the bitmap. Once all the integers are processed, output the longest continuous sequence of integers in increasing order. If there are two longest sequences, output the first one in numerical order.
Output
All output should be to stdout. Output a single line, terminated by a newline in the following
format:
Max sequence: X1 X2 … Xk where Xi are the integers from the sequence, listed in increasing order.
Example
Input
10 10
3
1
5
7
4
1
8
5
9
4
Output:
Max sequence: 3 4 5
Need help in CSCI 2122 Lab 3: Bit Manipulation Solution? Contact Us:
Call or WhatsApp at :
+91 - 995 3141 035 (For quick response)
Solution Includes: AI writing Detection and Plagiarism free report with 100% Accuracy.
