Gewichtung einer Binärzahl

[Simon (Gast)]

Guten Tag

Ich habe ein kleines Problem mit der Gewichtung einer Variabel.
Das Ziel ist es mit einem möglichst kleinem Code-Aufwand (in C oder C++) 
herauszufinden ob bei einer Variabel ein Bit = 1 ist.
Eine Lösung ist zum Beispiel bei einer 4Bit Variabel:


if((sample==1)||(sample==2)||(sample==4)||(sample==8))
  {
  }
else
  {
  }


Bei einer 8Bit Variabel gibt es dabei schon viel zu schreiben.
Ist das die Lösung oder gibt es noch einen „schöneren“ Weg dies zu 
Lösen?

Vielen Dank und mit freundlichen Grüssen

Simon

[NurEinGast (Gast)]

>   if((sample==1)||(sample==2)||(sample==4)||(sample==8))

Darf wirklich nur genau 1 Bit eins sein ?

Ansonsten :

if ( sample & 0x0F )
{
}

[Martin (Gast)]

Deine Fragestellung passt nicht ganz zum Beispiel:

Fragestellung: "ein Bit = 1"
Beispiel: "ein einziges Bit = 1"

Willst Du "reines" C oder was geht auch Plattformabhängiges? Welche 
Plattform?

[Simon (Gast)]

Die Meinung ist nur ein einziges Bit (so wie im Beispiel)

Die Gewichtung soll = 1 sein.

Also z.B. 0b00000100  => TRUE
          0b00101000  => FALSE
          0b01000000  => TRUE


Ich programmiere auf MPLAB und soweit ich weiss reines C.

[Walter T. (nicolas)]

Du willst also wissen, ob die Anzahl der gesetzten Bits == 1 ist?

[Jürgen H. (juh)]

Wie wär's dann mit:

if( sample & (sample-1) ) //  genau ein Bit in Sample gesetzt?
  {
  ...
  }
else // nicht ein einzelnes Bit gesetzt (null oder mehr als eins)
  {
  ...
  }

'x & ( x - 1)' setzt das jeweils niedrigste Bit des Wertes auf 0,
dieser wird also 0, wenn nur ein Bit gesetzt war...

[Jürgen H. (juh)]

Natürlich genau falschherum gepostet.....

if( sample & (sample-1) ) //  NICHT genau ein Bit in Sample gesetzt?
  {
  ...
  }
else // GENAU ein einzelnes Bit gesetzt 
  {
  ...
  }

'x & ( x - 1)' setzt das jeweils niedrigste Bit des Wertes auf 0,
dieser wird also 0, wenn nur ein Bit gesetzt war...

[Peter II (Gast)]

Jürgen Hilker schrieb:
> 'x & ( x - 1)' setzt das jeweils niedrigste Bit des Wertes auf 0,
> dieser wird also 0, wenn nur ein Bit gesetzt war...

x = 1
x & 0 = 0

x = 2
x & 1 = 0


irgdenwie stimmt das aber nicht.

[NurEinGast (Gast)]

Wieso - passt doch

x = 1  // 1 Bit
x & 0 = 0

x = 2  // 1 Bit
x & 1 = 0

x = 3  // 2 Bits gesetzt
x & 2 = 1

@ Jürgen Hilker

Danke für die Idee.
Kannte ich nicht.

[Klaus W. (mfgkw)]

Liefert 1, wenn in i genau 1 Bit gesetzt, sonst 0 
(Feldgrenzenüberschreitung, wenn i<0 oder i>255):

"\x0\x1\x1\x0\x1\x0\x0\x0\x1\x0\x0\x0\x0\x0\x0\x0\x1\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x1\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x1\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x1\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0"[i]

[zebra (Gast)]

Peter, erst denken, dann posten.
Sind schon wieder Schulferien?

[Peter II (Gast)]

zebra schrieb:
> Peter, erst denken, dann posten.
> Sind schon wieder Schulferien?

ja sorry, hatte mich vertan. Schule ist leider schon seit jahren vorbei

[zebra (Gast)]

x=0 ist ein Sonderfall.

[Klaus W. (mfgkw)]

Alternative ohne Feld:

        ( ( (i & 0x01)!=0 )
          +
          ( (i & 0x02)!=0 )
          +
          ( (i & 0x04)!=0 )
          +
          ( (i & 0x08)!=0 )
          +
          ( (i & 0x10)!=0 )
          +
          ( (i & 0x20)!=0 )
          +
          ( (i & 0x40)!=0 )
          +
          ( (i & 0x80)!=0 )
          ) == 1

Der große Klammerausdruck liefert die Anzahl Bits.

[avr (Gast)]

Am effektivsten wird immer noch Jürgens korrigierte Variante sein:

if(sample == 0 || sample & (sample-1) ) //  NICHT genau ein Bit in Sample gesetzt? 
{
  ...
}
else // GENAU ein einzelnes Bit gesetzt 
{
  ...
}

[Detlef _. (detlef_a)]

Yo, das geht aber auch schneller, so z.B.,  aus

http://www-graphics.stanford.edu/~seander/bithacks.html#ParityWith64Bits

Cheers
Detlef


Compute parity in parallel

unsigned int v;  // word value to compute the parity of
v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

The method above takes around 9 operations, and works for 32-bit words. 
It may be optimized to work just on bytes in 5 operations by removing 
the two lines immediately following "unsigned int v;". The method first 
shifts and XORs the eight nibbles of the 32-bit value together, leaving 
the result in the lowest nibble of v. Next, the binary number 0110 1001 
1001 0110 (0x6996 in hex) is shifted to the right by the value 
represented in the lowest nibble of v. This number is like a miniature 
16-bit parity-table indexed by the low four bits in v. The result has 
the parity of v in bit 1, which is masked and returned.

Thanks to Mathew Hendry for pointing out the shift-lookup idea at the 
end on Dec. 15, 2002. That optimization shaves two operations off using 
only shifting and XORing to find the parity.

[avr (Gast)]

Oder möglicherweise auch so, damit der Compiler versteht wie er 
optimieren soll:

uint8_t temp = sample - 1;
if(temp == 255 || sample & temp) //  NICHT genau ein Bit in Sample gesetzt? 
{
  ...
}
else // GENAU ein einzelnes Bit gesetzt 
{
  ...
}

[avr (Gast)]

Detlef _a schrieb:
> Yo, das geht aber auch schneller, so z.B.,  aus

Das ist definitiv langsamer als die zweite, Compiler-optimierte Variante 
(Beitrag "Re: Gewichtung einer Binärzahl"). Diese benötigt 
nur 6 Befehle inklusiv aller Sprungbefehle:

  uint8_t sample = PIND;
  a4:  80 b3         in  r24, 0x10  ; 16
  uint8_t temp = sample - 1;
  a6:  98 2f         mov  r25, r24
  a8:  91 50         subi  r25, 0x01  ; 1
  aa:  10 f0         brcs  .+4        ; 0xb0 <main+0xc>
  if(temp == 255 || sample & temp ) //  NICHT genau ein Bit in Sample gesetzt? 
  ac:  89 23         and  r24, r25
  ae:  11 f0         breq  .+4        ; 0xb4 <main+0x10>
  {
    PORTB = 0;
  b0:  18 ba         out  0x18, r1  ; 24
  b2:  02 c0         rjmp  .+4        ; 0xb8 <main+0x14>
  }
  else // GENAU ein einzelnes Bit gesetzt 
  {
    PORTB = 1;
  b4:  81 e0         ldi  r24, 0x01  ; 1
  b6:  88 bb         out  0x18, r24  ; 24

[zebra (Gast)]

Detlef _a schrieb:
> Yo, das geht aber auch schneller, so z.B.,  aus

Nein tut es nicht.

[Simon (Gast)]

Jürgen Hilker schrieb:
>if( sample & (sample-1) ) //  NICHT genau ein Bit in Sample gesetzt?
>   {
>   ...
>   }
> else // GENAU ein einzelnes Bit gesetzt
>   {
>   ...
>   }
>
> 'x & ( x - 1)' setzt das jeweils niedrigste Bit des Wertes auf 0,
> dieser wird also 0, wenn nur ein Bit gesetzt war...

Danke :-) genau eine solche Lösung habe ich gesucht.

[Andreas B. (andreas_b77)]

Mit GCC, und wenn es auch mal um etwas anderes als nur den Spezialfall 1 
Bit geht, ist am schnellsten vielleicht __builtin_popcount(x).

Hat den Vorteil, dass es eine entsprechende Maschineninstruktion 
verwendet, wenn die CPU so etwas bietet.