Berechnungsvorschrift Hashing

Jasch

Hallo zusammen,

ich sitze an einer Aufgabe bei der es darum geht einen String in einen Hash umzuwandeln und diese in eine Datenbank einzulesen, allerdings hapert es bei mir schon daran die Berechnungsvorschrift zu verstehen.
Diese lautet wie folgt:
1. string_hash("") = 0b00000000
(Der Hash eines leeren Strings ist ein Null-byte)
2. string_hash(str) = ROT(string_hash(head) XOR tail)
Wobei str der String ist, der durch Anfügen der Bytes tail an den String head entsteht
XOR ein bitweises Exkulsives-Oder
ROT eine linksrum-Rotation eines Bytes um einen Byte ist
(Beispiel: ROT(0b10000000) == 0b00000001)

Mein bisheriger Code:

unsigned char string_hash(std::string s) {
	char ret = 0;
	for (int i = 0; i < s.length(); i++){
                if((s.length()-i) == i)
                    break;
		int temp= s[s.length()-i]^s[i];
		ret = temp << 1;
	}
	// weil später ein char als key verwendet wird, muss hier noch ein cast durchgeführt werden
	return (unsigned char)ret;
}

Hat jemand eine Idee dazu? Wie genau funktioniert das mit der Linksrotation?
Mit dem links-shift ist es ja nicht getan
Danke schon mal

SeppJ

Hast du schon einmal den Begriff "Rekursion" gehört?

Jasch

Der Begriff "Rekursion" ist mir bekannt. In der Besprechung der letzten Übungsaufgaben wurde allerdings gesagt, dass dies hier auch einfach iterativ zu lösen ist.

hustbaer

Jasch schrieb:

Wie genau funktioniert das mit der Linksrotation?
Mit dem links-shift ist es ja nicht getan

Beim Links-Shiften fliegen die Bits die links keinen Platz mehr haben raus, und von rechts kommen 0-Bits dazu.
Beim Links-Rotieren werden die Bits die links keinen Platz mehr haben von rechts wieder reingeschoben.

Also z.B.

ABCDEFGH
um 2 nach links rotiert, bei Registerbreite 8, ergibt
CDEFGHAB

C++ hat da dummerweise keinen Operator dafür. Man kann Rotieren aber natürlich mit mehreren Shifts + einer von mehreren Rechenoperationen (z.B. XOR, OR, Addition) nachbilden.