Vergleich zweier bit Zustände

Hi! Ich habe hier 6 verschiedene Bitmasken: 0x10, 0x20, 0x40, 0x80, 0x100 und 0x200.
Binär gesehen wird für die nächste Maske einfach nur ein bit weiter geschoben. Wie kann ich effizient herausfinden um wie viele bits zwei werte verschoben sind?

Beispiele:
0x10 und 0x20 -> 1
0x10 und 0x40 -> 2
0x11 und 0x20 -> 1
0x11 und 0x23 -> 1
0x80 und 0x40 -> -1
0x103 und 0x42 -> -2
0x200 und 0x208 -> 0

Müsste eigentlich die letzen vier bits abschneiden und dann schauen dann schauen um wie viel es verschoben ist oder? Wie mache ich das am besten mit möglichst wenig Operationen?

Vielen Dank!

DocShoe

Ist in jeder Bitmaske immer nur ein Bit gesetzt?

Ja.

Bitmaskenshift schrieb:

Müsste eigentlich die letzen vier bits abschneiden

var = var & 0xFFFFFF00;

und dann schauen dann schauen um wie viel es verschoben ist oder? Wie mache ich das am besten mit möglichst wenig Operationen?

Vielen Dank!

den größeren so lange durch 2 teilen, bis er gleich dem kleineren ist.

bevor jemand meckert: 0xFFFFFFF0

void diffTest() {
	//Anfangswerte
	int state0 = 0x11;
	int state1 = 0x43; 

	//Letzten 4 bits abschneiden
	state0 &= 0x3F0;
	state1 &= 0x3F0;

	//Merken ob negativ oder nicht
	bool isNegative = false;
	if (state0 < state1) {
		isNegative = true;
		swap(state0, state1);
	}

	int diff = 0;
	while (state0 > state1) {
		diff++;
		state0 >>= 1;
	}

	if (isNegative) diff *= -1;
}

Das geht doch bestimmt eleganter und kürzer...

SeppJ

Eleganter und kürzer wäre eine Division, weil dann log_2(Divisionsergebnis) direkt die Verschiebung ist. Schneller wird das aber nicht, eher im Gegenteil.

Caligulaminus

uint32_t diff(uint32_t a, uint32_t b)
{
	if(b > a) std::swap(a, b);
	auto c = a - b;
	c = (c & 0x55555555) + ((c >> 1) & 0x55555555);
	c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
	c = (c & 0x0f0f0f0f) + ((c >> 4) & 0x0f0f0f0f);
	c = (c & 0x00ff00ff) + ((c >> 8) & 0x00ff00ff);
	return (c & 0x0000ffff) + ((c >> 16) & 0x0000ffff);
}

camper

int diff(unsigned a, unsigned b) {
    static const char lut[] = {
        0, 0, 1, 0, 2, 1, 9, 0,
        3, 2, 9, 1, 9, 9, 9, 0,
        4, 3, 9, 2, 9, 9, 9, 1,
        9, 9, 9, 9, 9, 9, 9, 0,
        5, 4, 9, 3, 9, 9, 9, 2,
        9, 9, 9, 9, 9, 9, 9, 1 };

    a &= 0x3f0;
    b &= 0x3f0;
    assert((a | b) != 0 && lut[(a | b) / 16 - 1] != 9);

    return a < b ? -lut[(a | b) / 16 - 1] : lut[(a | b) / 16 - 1];
}