EX01 - Programmation C/C++ – avec solutions
Exercice 1 : Opérations binaires
Pour cet exercice, vous pouvez installer un environnement de développement C/C++ sur votre machine, ou simplement utiliser un compilateur dans le “cloud” tel que sur : tutorialspoint.com.
Vous pouvez aussi utilise Visual Studio Code avec le “devcontainer” fourni dans le dépôt ex01-starter. Pour cette option vous aurez besoin des logiciels suivants sur votre machine :
CountBits
Écrivez une fonction en C++ qui compte le nombre de bits à “1” dans un entier positif La signature de cette méthode est :
int CountBits(uint32_t n);
Testez votre fonction avec un programme principal.
Solution
Première solution : une boucle sur les bits de l’entier :
int CountBits(uint32_t n)
{
int result = 0;
for (int i = 0; i < (int)sizeof(n)*8; i++)
{
if ((n & (1 << i)) != 0)
result++;
}
return result;
}
Deuxième solution, indépendente de la taille de l’entier :
int CountBits(uint32_t n)
{
int result = 0;
while (n != 0) {
if (n % 2 == 1) {
result++;
}
n = n / 2;
}
return result;
}
Troisième solution (astucieuse et rapide) :
int CountBits(uint32_t n)
{
uint32_t t = n;
t = (t & 0x55555555) + ((t & 0xaaaaaaaa) >> 1);
t = (t & 0x33333333) + ((t & 0xcccccccc) >> 2);
t = (t & 0x0f0f0f0f) + ((t & 0xf0f0f0f0) >> 4);
t = (t & 0x00ff00ff) + ((t & 0xff00ff00) >> 8);
t = (t & 0x0000ffff) + ((t & 0xffff0000) >> 16);
return (int)t;
}
MostSignificantBit
Écrivez une fonction en C++ qui détermine le bit le plus signifiant dans un entier positif La signature de cette méthode est :
int MostSignificantBit(uint32_t n);
Testez votre fonction avec un programme principal.
Solution
Première solution :
int MostSignificantBit(uint32_t n)
{
int result = 0;
while (n != 0) {
n = n >> 1;
result++;
}
return result;
}
Deuxième solution (astucieuse et aussi rapide) :
int MostSignificantBit(uint32_t n)
{
uint32_t t = n;
t |= (t >> 1);
t |= (t >> 2);
t |= (t >> 4);
t |= (t >> 8);
t |= (t >> 16);
return CountBits(t);
}
ReverseBits
Écrivez une fonction en C++ qui renverse les bits d’un entier positif. Le bit 31 (poids fort) est échangé avec le bit 0, le bit 30 est échangé avec le bit 1, etc.
La signature de cette méthode est :
uint32_t ReverseBits(uint32_t n);
Testez votre fonction avec un programme principal.
Solution
Première solution :
uint32_t ReverseBits(uint32_t n)
{
uint32_t result = 0;
for (int i = 0; i < (int)sizeof(n)*8; i++)
{
result = (result << 1) + (n % 2);
n /= 2;
}
return result;
}
Deuxième solution (astucieuse et aussi rapide) :
uint32_t ReverseBits(uint32_t n)
{
uint32_t t = n;
t = ((t >> 1) & 0x55555555) | ((t & 0x55555555) << 1);
t = ((t >> 2) & 0x33333333) | ((t & 0x33333333) << 2);
t = ((t >> 4) & 0x0f0f0f0f) | ((t & 0x0f0f0f0f) << 4);
t = ((t >> 8) & 0x00ff00ff) | ((t & 0x00ff00ff) << 8);
t = ((t >> 16) & 0x0000ffff) | ((t & 0x0000ffff) << 16);
return t;
}
Autres opérations binaires
Implémentez les fonctions ci-dessous conformément aux commentaires :
uint32_t SetBit(uint32_t n, int i); // returns n with bit i set
uint32_t ClearBit(uint32_t n, int i); // returns n with bit i cleared
uint32_t ToggleBit(uint32_t n, int i); // returns n with bit i inverted
bool TestBit(uint32_t n, int i); // tests if bit i of n is set
Testez vos fonctions avec un programme principal.
Solution
uint32_t SetBit(uint32_t n, int i) // returns n with bit i set
{
return n | (1 << i);
}
uint32_t ClearBit(uint32_t n, int i) // returns n with bit i cleared
{
return n & ~(1 << i);
}
uint32_t ToggleBit(uint32_t n, int i) // returns n with bit i inverted
{
return n ^ (1 << i);
}
bool TestBit(uint32_t n, int i) // tests if bit i of n is set
{
return (n & (1 << i)) != 0;
}
Exercice 2 : La fonction mystère
Implémentez l’algorithme suivant dans une fonction C++:
- soit \(n\) un nombre tel que \(n \leq 9999\) et qui ne soit pas composé de 4 fois le même chiffre (c’est-à-dire pas 0000, 1111, 2222, …)
- calculer \(max\) comme le plus grand nombre de 4 digits qu’on peut obtenir avec les digits de \(n\)
- calculer \(min\) comme le plus petit nombre de 4 digits qu’on peut obtenir avec les digits de \(n\)
- calculer \(d = max - min\)
- si \(d = n\) retourner \(d\) et l’algorithme est terminé
- sinon, assigner \(d\) à \(n\) et reprendre le point 2.
Pour cet exercice, nous vous recommandons d’utiliser des vecteurs et la fonction “std::sort” proposée
par la bibliothèque “algorithm”. Votre programme pourrait importer les bibliothèques suivantes :
#include <algorithm> // std::sort
#include <vector> // std::vector
Voici quelques opérations que vous pouvez faire avec un vecteur d’entiers :
std::vector<int> a;
a.insert(a.begin(), x); // insert x at the beginning of the vector
a.push_back(x); // append x at the end of the vector
std::sort(a.begin(), a.end()); // sort the vector a (ascending)
std::sort(a.begin(), a.end(), std::greater<int>()); // sort descending
Info
Si vous voulez savoir pourquoi votre méthode retourne toujours 6174, lisez l’article suivant sur Wikipedia :
Solution 1 (avec des "vectors")
#include <iostream> // std::cout
#include <algorithm> // std::sort
#include <vector> // std::vector
constexpr int kNumberOfDigits = 4;
std::vector<int> IntegerToVector(int n)
{
std::vector<int> res;
while (n != 0) {
res.insert(res.begin(), n % 10);
n = n / 10;
}
// complete vector with zeros
while (res.size() < kNumberOfDigits) {
res.insert(res.begin(), 0);
}
return res;
}
int VectorToInteger(std::vector<int> a)
{
int res = 0;
for (auto i : a) {
res = res * 10 + i;
}
return res;
}
int Step(int x)
{
auto r = IntegerToVector(x);
std::sort(r.begin(), r.end(), std::greater<int>());
int max = VectorToInteger(r);
std::sort(r.begin(), r.end());
int min = VectorToInteger(r);
return max - min;
}
int Mysterious(int n)
{
while (true) {
int x = Step(n);
if (x == n) {
return n;
}
n = x;
}
}
int main()
{
std::cout << Mysterious(4793) << std::endl;
}
Solution 2 (avec des "strings")
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char* argv[])
{
const int NB_CHAR = 4;
// check for argument
if (argc != 2) return 0;
// check for valid number within argument
string val = argv[1];
if (val.length() != NB_CHAR) return 0;
// check for valid input
char c = val[0];
bool ok = false;
for (auto v : val) {
if (v != c) ok = true;
}
if (!ok) return 0;
// compute 6174 (number)
int n=0;
int delta=0;
do {
n = stoi(val);
sort (val.begin(), val.end(), std::greater<char>());
int max = stoi(val);
sort (val.begin(), val.end());
int min = stoi(val);
delta = max - min;
val = to_string(delta);
printf("n:%4d, max:%4d, min:%4d, d:%4d\n", n, max, min, delta);
} while (delta != n);
return 0;
}
Exercice 3 : Affichage 7-segments
Écrivez un programme en C++ qui simule un affichage à sept segments.
L’interface publique de la classe Segments est donnée :
class Segments {
public:
Segments(int n = 1);
void Set(int v);
void Draw(int w = 3, int h = 2, int dx = 1);
private:
// TODO
};
L’argument du constructeur indique le nombre de “digits” qui compose
l’affichage. La méthode Set définit le nombre à afficher. La méthode
Draw simule l’affichage avec des segments horizontaux de w caractères,
des segments verticaux de h caractères et un espace de dx entre deux
segments.
Testez avec le programme principal suivant :
int main()
{
Segments s(4) ;
s.Set(639);
s.Draw();
}
Le résultat devrait ressembler à ça :
--- --- --- ---
| | | | | |
| | | | | |
--- --- ---
| | | | | |
| | | | | |
--- --- --- ---
Pour l’affichage, vous pouvez utiliser la classe Canvas que nous
vous donnons ci-dessous, mais vous pouvez aussi faire autrement si vous
voulez :
#include <vector>
#include <stdint.h>
class Canvas {
public:
Canvas (int w, int h);
virtual ~Canvas() {};
void Clear (char c = '.');
void HLine(int x, int y, int len, char c = '*');
void VLine(int x, int y, int len, char c = '*');
void Print();
private:
std::vector<std::vector<char>> canvas_;
};
Canvas::Canvas (int w, int h) {
canvas_.resize(h);
for (int y = 0; y < h; y++) {
canvas_[y].resize(w, ' ');
}
}
void Canvas::Clear (char c) {
for (int y = 0; y < canvas_.size(); y++) {
for (int x = 0; x < canvas_[y].size(); x++) {
canvas_[y][x] = c;
}
}
}
void Canvas::HLine(int x, int y, int len, char c) {
for (int i = 0; i < len; i++) {
canvas_[y][x+i] = c;
}
}
void Canvas::VLine(int x, int y, int len, char c) {
for (int i = 0; i < len; i++) {
canvas_[y+i][x] = c;
}
}
void Canvas::Print() {
for (auto row : canvas_) {
for (auto c : row) {
printf("%c", c);
}
printf("\n");
}
}
Solution
#include <iostream>
#include <vector>
#include <stdint.h>
typedef std::vector<std::vector<char> > canvas_t;
const uint8_t digits[] = {
0b00111111, // 0
0b00000110, // 1
0b01011011, // 2
0b01001111, // 3
0b01100110, // 4
0b01101101, // 5
0b01111101, // 6
0b00000111, // 7
0b01111111, // 8
0b01101111, // 9
};
class Canvas
{
public:
Canvas(int w, int h);
void Clear(char c = '.');
void HLine(int x, int y, int len, char c = '*');
void VLine(int x, int y, int len, char c = '*');
void Print();
private:
std::vector<std::vector<char> > canvas_;
};
Canvas::Canvas(int w, int h)
{
canvas_.resize(h);
for (int y = 0; y < h; y++)
{
canvas_[y].resize(w, ' ');
}
}
void Canvas::Clear(char c)
{
for (int y = 0; y < canvas_.size(); y++)
{
for (int x = 0; x < canvas_[y].size(); x++)
{
canvas_[y][x] = c;
}
}
}
void Canvas::HLine(int x, int y, int len, char c)
{
for (int i = 0; i < len; i++)
{
canvas_[y][x + i] = c;
}
}
void Canvas::VLine(int x, int y, int len, char c)
{
for (int i = 0; i < len; i++)
{
canvas_[y + i][x] = c;
}
}
void Canvas::Print()
{
for (int y = 0; y < canvas_.size(); y++)
{
for (int x = 0; x < canvas_[y].size(); x++)
{
std::cout << canvas_[y][x];
}
std::cout << std::endl;
}
}
class Segments
{
public:
Segments(int n = 1);
void Set(int v);
void Draw(int w = 3, int h = 2, int dx = 1);
private:
void DrawDigit(Canvas &canvas, int seg, int x, int y, int h, int w);
std::vector<uint8_t> seg_;
};
Segments::Segments(int n)
{
seg_.resize(n);
};
void Segments::Set(int v)
{
for (int i = seg_.size() - 1; i >= 0; i--)
{
this->seg_[i] = digits[v % 10];
v = v / 10;
}
}
void Segments::DrawDigit(Canvas &canvas, int seg, int x, int y, int w, int h)
{
if (seg & 0x01) canvas.HLine(x + 1, y + 0, w, '-');
if (seg & 0x02) canvas.VLine(x + w + 1, y + 1, h, '|');
if (seg & 0x04) canvas.VLine(x + w + 1, y + h + 2, h, '|');
if (seg & 0x08) canvas.HLine(x + 1, y + 2 * h + 2, w, '-');
if (seg & 0x10) canvas.VLine(x + 0, y + h + 2, h, '|');
if (seg & 0x20) canvas.VLine(x + 0, y + 1, h, '|');
if (seg & 0x40) canvas.HLine(x + 1, y + h + 1, w, '-');
}
void Segments::Draw(int w, int h, int dx)
{
Canvas canvas((2 + w) * seg_.size() + dx * (seg_.size() - 1), 3 + 2 * h);
canvas.Clear(' ');
for (int i = 0; i < seg_.size(); i++)
{
DrawDigit(canvas, seg_[i], (w + 2 + dx) * i, 0, w, h);
}
canvas.Print();
}
int main()
{
Segments s(4);
s.Set(639);
s.Draw();
}
Exercice 4 : CPU à accumulateur
Un CPU basé sur un accumulateur est un type d’architecture de processeur qui utilise un registre spécial, appelé accumulateur, pour la plupart des opérations arithmétiques et logiques. Dans cette conception, l’un des opérandes pour ces opérations est toujours l’accumulateur, et le résultat est stocké de nouveau dans l’accumulateur. Cette approche simplifie la conception du CPU en réduisant le nombre de registres et de chemins de données, ce qui en a fait un choix populaire pour les premiers ordinateurs et certains processeurs modernes à faible consommation ou spécialisés.
En vous basant sur la description ci-dessus, écrivez une classe C/C++ appelée
AccumulatorCpu représentant un CPU 32-bit. La classe doit avoir les éléments suivants :
- Une variable membre représentant l’accumulateur occupant 32 bits.
- Des méthodes pour les opérations suivantes :
load(pour charger une valeur dans l’accumulateur),addetsubtract(pour effectuer ces opérations avec l’accumulateur et un autre opérande), etstore(pour stocker la valeur de l’accumulateur dans une variable donnée).
- Une méthode
displaypour afficher la valeur actuelle de l’accumulateur.
Assurez-vous que votre classe encapsule correctement l’accumulateur et fournit
des méthodes d’accès appropriées. Vous pouvez également inclure une fonction
principale simple pour démontrer l’utilisation de votre classe AccumulatorCpu.
Exemple d’utilisation :
#include <stdio.h>
#include <stdint.h>
int main() {
AccumulatorCpu acccpu;
printf("\n=============================== \n");
printf("Accumulator Computation results \n");
printf("=============================== \n");
acccpu.load(128);
acccpu.add(18);
acccpu.subtract(0x18);
acccpu.display();
uint32_t result;
acccpu.store(result);
printf("Result of the computation is : %d\n", result);
return 0;
}
AccumulatorCpu est utilisée pour effectuer des
opérations arithmétiques de base et stocker les résultats. Le résultat obtenu
est le suivant :
===============================
Accumulator Computation results
===============================
Accumulator value: 0x007a
Result of the computation is : 122
Solution
class AccumulatorCPU {
public:
AccumulatorCPU() : accumulator(0) {}
void load(uint32_t value) {
accumulator = value;
}
void add(uint32_t value) {
accumulator += value;
}
void subtract(uint32_t value) {
accumulator -= value;
}
void store(uint32_t &target) const {
target = accumulator;
}
void display() const {
printf("Accumulator value: 0x%04x\n", accumulator);
}
private:
uint32_t accumulator;
};