Bit-Shift auffüllen mit Einsen/Nullen

[Shifter (Gast)]

Hallo zusammen,
um Bits für ein 32-Bit Schieberegister "vorzubereiten" möchte ich eine 
32-Bit Variable bitweise (nach rechts) verschieben. Dafür sollten die 
links weggeschobenen Bits mit Einsen aufgefüllt werden. Bisher rücken 
Nullen nach.
Wie kann ich das ändern bzw. gibt es einen weiteren Bitshift-Operator 
als >> der mit Einsen auffüllt?
Ich nutze den GCC mit AtmelStudio 6, Controller ist ein ATmega328.

Danke und Gruß,
shifter

[Dr. Sommer (Gast)]

uint32_t x = ...;
x = (1UL << 31) | (x >> 1);

[Ralf G. (ralg)]

Dr. Sommer schrieb:
> uint32_t x = ...;
> x = (1UL << 31) | (x >> 1);

Da wird tatsächlich als erstes nach rechts geschoben?

[Michael R. (Firma: Brainit GmbH) (fisa)]

der "arithmetic shift right" macht fast was du willst: der 
berücksichtigt nämlich das Vorzeichen. Wenn das höchste Bit 1 ist, wird 
mit 1 aufgefüllt, sonst mit 0

allerdings müsstest du den ersten Shift "normal" ausführen und dann das 
höchste Bit "zu Fuß" auf 1 setzen.

arithmetic shift sollte vom Compiler automatisch beim shiften von signed 
ints verwendet werden.

[Shifter (Gast)]

Hallo!

Dr. Sommer schrieb:
> uint32_t x = ...;
> x = (1UL << 31) | (x >> 1);

Das funktioniert in meinem Fall leider nicht, ich möchte beispielsweise 
so eine Bitfolge um x Bits nach rechts verschieben:

uint32_t shiftedVar = 0b11000111000111111111111111111111 >> x;

(Und raus kommt dann blöderweise so etwas (x=2):

0b00110001110001111111111111111111

)

[Shifter (Gast)]

Michael Reinelt schrieb:
> der "arithmetic shift right" macht fast was du willst: der
> berücksichtigt nämlich das Vorzeichen. Wenn das höchste Bit 1 ist, wird
> mit 1 aufgefüllt, sonst mit 0
>
> allerdings müsstest du den ersten Shift "normal" ausführen und dann das
> höchste Bit "zu Fuß" auf 1 setzen.

Das hört sich gut an, aber wenn ich die Variable signed deklariere geht 
mir mein 32. Bit verloren :-(

[(prx) A. K. (prx)]

Michael Reinelt schrieb:
> der "arithmetic shift right" macht fast was du willst:

"fast" ist richtig. De fakto ist das zwar so, das Verhalten ist bei 
negativen Werten aber nicht formal festgeschrieben (implementation 
defined).

[Dr. Sommer (Gast)]

Shifter schrieb:
> Das funktioniert in meinem Fall leider nicht, ich möchte beispielsweise
> so eine Bitfolge um x Bits nach rechts verschieben:
Ach du möchtest um mehrere Bit schieben. Dann kannst du einfach mit 
einer Schleife mehrfach um 1 Bit schieben (denn nichts anderes macht der 
Compiler aus einem Shift um mehrere Bits, da AVR immer nur um 1 bit 
shiften kannst).
Just for fun hier aber eine Variante die auch mehrere Bits kann:

uint32_t multishift (uint32_t in, uint8_t bits) {
  uint32_t mask = (bits == 32) ? 0xFFFFFFFF : ((((uint32_t) 1) << bits) - 1);
  return (in >> bits) | (mask << (32-bits));
}

[(prx) A. K. (prx)]

Shifter schrieb:
> Das funktioniert in meinem Fall leider nicht, ich möchte beispielsweise
> so eine Bitfolge um x Bits nach rechts verschieben:

#define ShiftersShift(x,n) (~((~(x)) >> (n)))

[Michael R. (Firma: Brainit GmbH) (fisa)]

Shifter schrieb:
> Das hört sich gut an, aber wenn ich die Variable signed deklariere geht
> mir mein 32. Bit verloren :-(

Nein, nicht unbedingt. Dir wird nur (tmeporär) der Wert negativ.

ich glaube aber dass die Lösung von Dr. Sommer schöner ist, du musst die 
Schleife halt "zu Fuß" ausprogrammieren. Das ist aber kein 
(Performance-) Nachteil, da der AVR ohnehin keinen Barrel-Shifter hat.

so in etwa

uint32 shift_me(uint32_t val, uint8_t x)
{
   while (x-- > 0) {
      val = (val >> 1) | (1UL << 31);
   }
   return val;
}

[(prx) A. K. (prx)]

A. K. schrieb:
> #define ShiftersShift(x,n) (~((~(x)) >> (n)))

Falls das zu unübersichtlich ist:
  Alle Bits invertieren
  Shiften mit einlaufenden Nullen
  Alle Bits invertieren

[Andreas R. (andreasr)]

Do könntest Deinen Wert auch invertiert ablegen.
Dann kannst Du normal shiften.
Vor der Ausgabe bildest Du dann noch mal das Komplement in einer temp. 
Variable.

Andreas

[Michael R. (Firma: Brainit GmbH) (fisa)]

A. K. schrieb:
> #define ShiftersShift(x,n) (~((~(x)) >> (n)))

Der sieht natürlich ziemlich cool aus, Respekt!

und nachdem der AVR ja einen COM (One's Complement) befehl hat, dürfte 
das sogar recht effizient sein.

[Shifter (Gast)]

Alle drei Lösungen sollten passen, A.K.s finde ich besonders kreativ ;-)
Werde das heute nachmittag mal testen.

Danke Euch,
shifter

[(prx) A. K. (prx)]

Michael Reinelt schrieb:
> und nachdem der AVR ja einen COM (One's Complement) befehl hat, dürfte
> das sogar recht effizient sein.

Das Problem sind nicht die einlaufenden Bits, sondern der Shift. Ein 
32-Bit Shift wird bei AVRs recht gern zur Schleife, weshalb das Setzen 
des obersten Bits auch nicht viel an der Sache ändert. Optimal übersetzt 
sind das bei unbekanntem n in deiner Version 8*n statt 7*n+8, und ist 
kürzer.

[Lothar M. (Firma: Titel) (lkmiller) (Moderator)]

A. K. schrieb:
> Ein 32-Bit Shift wird bei AVRs recht gern zur Schleife
Da hilft es dann auch nichts, wenn alles hübsch in 1 einzige C-Zeile 
passt...

Weil der AVR 1. ein 8-Bit Prozessor ist und 2. keinen Barrelshifter hat, 
ist es sowieso oft sinnvoll zu fragen, ob so ein (variabler) 
Schiebevorgang schon nötig ist, oder ob sich das nicht anders lösen 
lässt.

[Michael R. (Firma: Brainit GmbH) (fisa)]

A. K. schrieb:
> Ein
> 32-Bit Shift wird bei AVRs recht gern zur Schleife

nicht nur recht gern, sondern eigentlich (fast) immer (siehe 
Beitrag "GCC optimiert 32bit Bitoperationen schlecht/gar nicht?") und in seinem Fall mit 
Variable sowieso.

A. K. schrieb:
> in deiner Version 8*n statt 7*n+8

Aber deine sieht so lässig aus, das kompensiert mindestens 27 Zyklen ;-)

[Johnny B. (johnnyb)]

Lieber lesbaren/verständlichen Code als nur "coolen" Code produzieren. 
;-)

[Michael R. (Firma: Brainit GmbH) (fisa)]

Johnny B. schrieb:
> Lieber lesbaren/verständlichen Code als nur "coolen" Code produzieren.

Für mich ist der sehr lesbar und verständlich. Das Coole daran ist (für 
mich) die Idee dahinter. Auf die doppelte Negation muss man erstmal 
kommen.