Verwisselen van bits [C++]

[JoZ1]

Hallo,

Ik heb er lang naar gekeken maar ik kom niet uit de volgende opgaven:

Opgave 1
Lees een geheel getal in. In de interne binaire representatie hiervan staat bit 0 uiterst rechts, daarnaast bit 1, enzovoort. Verwissel hierin

bit 0 met bit 7,
bit 1 met bit 6,
bit 2 met bit 5,
bit 3 met bit 4

en druk het resultaat af.
Aanwijzing:

Gebruik hexadecimale invoer en uitvoer. Alleen de rechter acht bits moeten gewijzigd worden; de overige moeten ongewijzigd in de uitvoer verschijnen. Is bijvoorbeeld de invoer F703, dan wordt de uitvoer F7C0, omdat 03 = 0000 0011 en C0=1100 0000.

En deze:

Opgave 2
Als opgave 1, maar nu moeten de bits 0 tot en met 7 één positie naar links geroteerd worden, dus

bit 0 verhuist naar bit 1,
(de oorspronkelijke waarde van) bit 1 verhuist naar bit 2,
...
(de oorspronkelijke waarde van) bit 6 verhuist naar bit 7,
(de oorspronkelijke waarde van) bit 7 verhuist naar bit 0.

Zie de aanwijzing bij opgave 1. Is bijvoorbeeld de invoer FA83, dan wordt de uitvoer FA07.

Ik hoop dat iemand me een duwtje in de juiste richting kan geven.

 

[sentmen]

Hallo JoZ,

Op het moment dat het opgaves zijn ga ik er vanuit dat dit gaat om een school/studie opdracht en wij gaan hier niet bij helpen. Ook heb je niet opgave 3.7 erbij gezet wat aanwijzingen geven...

Groetjes sentmen.

 

[JoZ1]

Het zijn geen huiswerkopgaven
Ik ben een boek aan het lezen over C++ (geheel uit vrije wil), en daarin staan opgaven (zonder uitwerking).

Opgave 3.7 moet hier opgave 1 zijn (in het boek is het 3.7).

Bovendien mág er wel geholpen worden met huiswerk, mits niet gewoon de opgave wordt gemaakt zonder dat de TS erover meegedacht heeft.

 

[Supersnail]

Ik ken wel een methode. Ik weet alleen niet of dat de meest efficiënte methode is. Ik zou 8 kopieën van het getal maken (evt. kan je die opslaan in een array). Bij elke kopie gebruik je dan enkele shifts om de bit die je wilt behouden (bij kopie1 is dat bit 0, bij kopie2 is dat bit 1, etc.) te isoleren (als je een getal 1 keer naar rechts shift en vervolgens 1 keer naar links is de meest rechter bit altijd 0, ook als deze voor het shiften 1 was, hetzelfde geldt voor het andersom shiften). Zo krijg je 8 getallen die elk bestaan uit alleen maar nullen, behalve de bit die je wilt verwisselen, die kan 1 of 0 zijn. Deze bits shift je dan naar de juiste positie en voeg je op eenzelfde wijze als in je vorige vraag samen tot 1 int.

 

[JoZ1]

Hartstikke bedankt weer Supersnail! Ik ga er naar kijken.
Stom dat ik er zelf niet aan heb gedacht.

 

[Arjan B]

Je kunt voor opgave 1 ook het volgende doen:
* Converteer je hexadecimale getal naar het binaire getal en stop dit in een string
* Keer de string om
* Converteer dit binaire getal terug om naar een hexadecimaal getal

Voor opgave 2:
* Converteer
* Haal het eerste karakter van de string af en stop die er achteraan weer bij
* Converteer terug

 

[JoZ1]

Bedankt alletwee! Ik ben toch voor Supersnails oplossing gedaan omdat ik een string niet naar een boolarray kon converteren .

Deze werkt (voor zover ik heb getest):
[cpp]//Opgave 3.7
#include <iostream>
using namespace std;
int PackBools (bool* v, int n);

int main()
{
int x, y;
cout << "Geef een hexadecimaal getal: 0x"; cin >> hex >> x;
y = x & 0xFF; //Laatste 8 bits

//stop alle getallen in een bool-array
bool a[8];
for (int i = 0; i < 8; i++){
short z = y;
z >>= i; //verplaats bit naar rechtse uithoek
z <<= (15); //verplaats bit naar linkse uithoek (byte = 0000... of 10000...)
a = z;//impliciete conversie van short > bool en in omgekeerde volgorde
}

//draai array om (omdat PackBools de array omdraait)
int z = 7;
for (int i = 0; i < 4; i++){
bool temp = a;
a = a[i+z]; //wissel
a[i+z] = temp; //wissel
z -= 2;
}

cout << "De output is: 0x" << hex << PackBools(a, 8) + (x - y);

system("PAUSE>NUL");
return 0;
}

int PackBools (bool* v, int n)
{
int mask = 1, result = 0;
for (int i=0; i<n; i++, mask <<= 1) //mask schuift 1 plek naar links
{
if (v == true) result |= mask; //verander zonodig naar true
}
return result;
}[/cpp]

Maar ik ben nog niet uit de andere opgave:

[cpp]//Opgave 3.8
#include <iostream>
#include <bitset>
using namespace std;

int PackBools (bool* v, int n);
void bin(int n);

int main()
{
int x, y;
cout << "Geef een hexadecimaal getal: 0x"; cin >> hex >> x;
y = x & 0xFF; //Laatste 8 bits

//stop alle getallen in een bool-array
bool a[8], b[8];
for (int i = 0; i < 8; i++){
short z = y;
z >>= i; //verplaats bit naar rechtse uithoek
z <<= (15); //verplaats bit naar linkse uithoek (byte = 0000... of 10000...)
a = b = z; //impliciete conversie van short -> bool
}
//draai array om
int v = 7;
for (int i = 0; i < 4; i++){
bool temp = a;
a = a[i+v]; //wissel
a[i+v] = temp; //wissel
v -= 2;
}

//TIJDELIJK: Geef array weer
for (int i = 0; i < 8; i++)
cout << a;
cout << endl;

//schuif array op
for (int i = 0; i < 8; i++) //van rechts naar links
a = b[i < 7 ? i + 1 : 0];

//TIJDELIJK: Geef array weer
for (int i = 0; i < 8; i++)
cout << a;
cout << endl;

cout << "De output is: 0x" << hex << PackBools(a, 8) + (x - y);

system("PAUSE>NUL");
return 0;
}

int PackBools (bool* v, int n)
{
int mask = 1, result = 0;
for (int i=0; i<n; i++, mask <<= 1) //mask schuift 1 plek naar links
{
if (v == true) result |= mask; //verander zonodig naar true
}
return result;
}

void bin(int n){
cout << bitset<numeric_limits<unsigned short>::digits>(n) << endl;
}[/cpp]

(Ik gebruik de functie bin tijdelijk om de binaire representatie van een getal weer te geven)

Het probleem is als volgt:

Ik voer bijv. 0xFA83 in. De output zou 0xFA07 moeten zijn.
(0x83 = 1000 0011, 0x07 = 0000 0111)

Maar de output is: 0xFAC1. De array heeft de waarden:
1100 0001
1000 0011

Er wórdt dus wel naar links geschoven. Maar de éérste waarde van de array is onjuist (1100 0001 = 0xC1).
En de tweede waarde is 0x83 (de input) ?

Heeft iemand een idee hoe dit mogelijk is?

 

[CoD_NL]

Ik ben toch voor Supersnails oplossing gedaan omdat ik een string niet naar een boolarray kon converteren

Hint: std::bitset ->

[cpp]
void SwapBits(std:bitset<32> &bs, unsigned int p1, unsigned int p2)
{
bool b1 = bs[p1];
bs[p1] = bs[p2];
bs[p2] = b1;
}
[/cpp]

Je hoeft overigens niet per se gebruik te maken van een bitset om bits te swappen. Wellicht helpt het als je de onderstaande informatie in acht neemt:

- je kan een specifieke bit ophalen d.m.v.: waarde & (1 << positie)
- je kan een bit op 0 zetten d.m.v.: waarde & ~(1 << positie)
- je kan een bit op 1 zetten d.m.v.: waarde | (1 << positie)

Met de bovenstaande informatie zou je al snel tot iets als het onderstaande moeten kunnen komen:

[cpp]
void SwapBits(unsigned int &v, unsigned int p1, unsigned int p2)
{
// haal bit @ p1 op (iets als: unsigned int b1 = (v & 1 << p1) ? 1 : 0)
// haal bit @ p2 op

// 'swap' de bits indien deze niet gelijk zijn aan elkaar (al ze wel gelijk zijn heeft het swappen immers geen nut)
// Iets als: v = (!b1 ? (v & ~(1 << p2)) : (v | 1 << p2))
}
[/cpp]

Al kan het uiteraard nog efficienter:

[cpp]
void SwapBits(unsigned int &v, unsigned int p1, unsigned int p2)
{
unsigned int m = ((v >> p1) ^ (v >> p2)) & 0x01;
v ^= ((m << p1) | (m << p2));
}
[/cpp]

(niet zelf uitgepuzzeld, maar ooit nodig gehad en onthouden )

Voor de tweede opgave hoef je dan enkel een for-loop te schrijven in de vorm van 'for (int i = 1; i < 8; i++) SwapBits(x, 0, i)'.

 

[Arjan B]

Volgens mij hoef je voor de tweede opgave niet per se alle bitjes apart te swappen.
Onderstaande code is dan een beetje een spoiler, maar ik weet het anders niet goed uit te leggen.

[CPP]
Shift(const int hex) {
// splits in rechter byte en andere bytes
const int mask = (1 << 8) - 1; // .. 1111 1111
const int rightByte = hex & mask;
const int otherBytes = hex - rightByte;

// verschuif alle bits eentje naar links, carry de 1 op bit 7 als dat nodig is
const int bit7mask = (1 << 7); // .. 1000 0000
int shifted;
if (rightByte & bit7mask) { // als bit 7 == 1
shifted = (rightByte << 1) + 1;
} else { // hoeven de 1 niet te carry-en
shifted = rightByte << 1;
}
shifted &= mask;

// plak alle bytes weer aan elkaar en retourneer
return otherBytes + shifted;
}
[/CPP]

 

[CoD_NL]

Je hebt inderdaad gelijk dat het niet noodzakelijk is om de bits apart te swappen, maar gezien de method 'SwapBits'er toch al in mijn voorbeeld stond was dit wel het eenvoudigste (vond ik).

Gezien de tweede opgave in principe gewoon een ROR (ROtate Right) is, kan de code een stuk korter door deze instructie zelf te implementeren (of door gebruik te maken van inline assembly, maar dat is nogal afhankelijk van de compiler). Door deze instructie zelf te implementeren heb ik het tot het onderstaande kunnen verkorten::

[cpp]
int Shift2(int h)
{
unsigned char b = h & 0xff;
return h & ~(b) | /* ROR instructie -> ror b, 7: */ (unsigned char)((b >> 7) | (b << 1));
}
[/cpp]

 

[JoZ1]

Hartstikke bedankt! Tweede opgave dus als volgt:

[cpp]#include <iostream>
using namespace std;

int main()
{
int x;
cout << "Geef een hexadecimaal getal: 0x"; cin >> hex >> x;
unsigned char b = x & 0xff;
cout << hex << (x & ~(b) | /* ROR instructie -> ror b, 7: */ (unsigned char)((b >> 7) | (b << 1)));

system("pause>nul");
return 0;
}[/cpp]