C Bitoperatoren in C - shiften

[_mclaren_]

Hallo!

Folgendes zu tun.

Ein Bitmuster z.B. 1011 1111 0000 0000 soll um 3 stellen nach link rotiert werden - also jedes Bit das links verschwindet soll recht wieder kommen - ergibt daher 1111 1000 0000 0101.

Ich überleg hier scho ewig herum, wie ich das realisieren könnt. Wie merk ich mir die wegfallenden und kanns wieder ranfügen?

Hat jemand irgendnen Tipp?
Die verschiebung soll beliebig sein, also nicht immer 3.


danke für jeden hilfreichen Kommentar!

 

[IceMatrix]

ganz einfach..

links:
x = (x << 3) | (x >> (32 - 3))

rechts:
x = (x >> 3) | (x << (32 - 3))


die 32 steht jeweils für die bits des registers.. sizeof(int) ist z.b. 32 / 8 = 4.

alternativ kannste auch einfach solche APIs hier nutzen:
http://msdn.microsoft.com/en-us/library/5cc576c4(VS.80).aspx

im günstigsten fall optimiert der compiler den call weg und implementiert es inline im assembler das ist weit effizienter als das geshifte.

 

[Boron]

const int numOfShifts = 3;
int bitmuster = 498521578; // oder was auch immer
int bitsToRotate = 0;

bitsToRotate = bitmuster >> ((sizeof(int)*8)-numOfShifts);
bitmuster <<= numOfShifts;
bitmuster += bitsToRotate;

 

[_mclaren_]

ganz einfach..

links:
x = (x << 3) | (x >> (32 - 3))

x << 3 ergibt 1111 1000 0000 0000, aber was ergibt x >> 29 - sind das nicht lauter nuller?

das wäre ja nur einfaches shiften, aber keine Rotation
___

const int numOfShifts = 3;
int bitmuster = 498521578; // oder was auch immer
int bitsToRotate = 0;

bitsToRotate = bitmuster >> ((sizeof(int)*8)-numOfShifts);
bitmuster <<= numOfShifts;
bitmuster += bitsToRotate;

Verständnisfrage:

const int numOfShifts = 3;
int bitmuster = 1011 1110 0000 0000
int bitsToRotate = 0;

bitsToRotate = bitmuster >> ((sizeof(int)*8)-numOfShifts);
// bitsofRotate = 1011 1110 0000 0000 >> 32*8-3
// bitsofRotate = ?!? Was soll das sein?

bitmuster <<= numOfShifts;
// bitmuster = bitmuster << 3
// bitmuster = 1111 1000 0000 0000

bitmuster += bitsToRotate;
// bitmuster = bitmuster + bitisRotate
// ...

Danke!

 

[IceMatrix]

das wäre ja nur einfaches shiften, aber keine Rotation

in deinem speziellen fall schon. das problem hierbei ist, dass du von 16 bits ausgehst und nicht von 32. das lässt sich aber anpassen!

 

[Boron]

 1: const int numOfShifts = [COLOR="Red"]6[/COLOR];
 2: int bitmuster = 498521578;
 3: // binär: [COLOR="Red"]0001 11[/COLOR]01 1011 0110 1101 0101 1110 1010
 4: // Ziel nach rotieren: 0110 1101 1011 0101 0111 1010 10[COLOR="Red"]00 0111[/COLOR]
 5: int bitsToRotate = 0;
 6: 
 7: bitsToRotate = bitmuster >> ((sizeof(int)*8)-numOfShifts);
 8: // int ist 4 Byte groß und numOfShifts ist 6; also soll "bitmuster" um (4*8) - 6
 9: // = 32 - 6 = 26 Bit nach recht geschoben werden
10: // daraus folgt: bitToRotate == 0000 0000 0000 0000 0000 0000 00[COLOR="Red"]00 0111[/COLOR]
11: 
12: bitmuster <<= numOfShifts;
13: // obere 6 Bits nach "links rausschieben"; von rechts kommen Nullen rein
14: // bitmuster == 0110 1101 1011 0101 0111 1010 1000 0000
15: 
16: bitmuster += bitsToRotate;
17: // auf bitmuster die zu rotierenden Bits wieder draufaddieren
18: // bitmuster  == 0110 1101 1011 0101 0111 1010 10[COLOR="Red"]00 0111[/COLOR]

Das Zielbitmuster aus Zeile 4 ist mit dem berechneten Muster aus Zeile 18 identisch .

 

[_mclaren_]

*snip*

 

[gruffi]

Noch ein kleiner Tipp, vermeide Shifts von signed Werten. Das gibt nur Ärger. Vor allem, wenn das MSB gesetzt ist, also der Wert negativ ist. Verwende stattdessen unsigned Typen.

 

[_mclaren_]

das z und die Funktion selbst sind eh unsigned? Oder hab ich was anderes noch übersehen?

Mir ist grad aufgefallen ich muss die Schleife in die Funktion geben, sonst ist die Übergabe von n unnötig.

EDIT: achso du meinst das "lost" - stimmt, danke!!