Erstes Bit setzen

[Christian Havel]

Hi,

ich habe folgendes Byte: 0x84 und möchte das höchstwertige Bit umsetzen,
d.h. 0x04.
Wie mache ich dies?
Christian

[Frank Dzaebel]

Hallo Christian,

Post by Christian Havel
ich habe folgendes Byte: 0x84 und möchte das
höchstwertige Bit umsetzen, d.h. 0x04. Wie mache ich dies?

aus :
http://groups.google.com/group/microsoft.public.de.german.entwickler.dotnet.vb/msg/95fd20225087f977
kannst Du ersehen, das es da verschiedene Möglichkeiten gibt.
Du könntest also ToggleBits hier meinen:
Sei: byte b = 0x84; // dann zum Beispiel:
- Toggle-Semantik: b ^= (byte)128;
- Off-Semantik: b &= (byte)127;


ciao Frank

[Frank Dzaebel]

Post by Frank Dzaebel
- Toggle-Semantik: b ^= (byte)128;
- Off-Semantik: b &= (byte)127;
- Toggle-Semantik: b ^= 128;
- Off-Semantik: b &= 127;

ciao Frank

[Alain Boss]

Und mit bitwise OR kannst du das Bit einschalten:

also:
Byte b = 0x84;

b |= 0x80; // einschalten
b &= 0x7F; // auschalten
b ^= 0x80; // toggeln

gruss
alain

[Christian Havel]

Danke Alain und Frank!

Eine Frage habe ich aber noch:
Wie kann ich ermitteln, wieviele der Bits innerhalb eines Byte gesetzt sind?
Christian

Post by Alain Boss
Byte b = 0x84;
b |= 0x80; // einschalten
b &= 0x7F; // auschalten
b ^= 0x80; // toggeln
gruss
alain

[Thomas Scheidegger]

Hallo Christian

Post by Christian Havel
ermitteln, wieviele der Bits innerhalb eines Byte gesetzt sind?

da gibt es etliche Ansätze,
bei Bytes etwa auch per Lookup-Table [auf Kosten Speicher],
oder (inbesondere bei breiteren Datentypen)
einige äusserst raffinierte Tricks (C++ Src):
<URL:http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable>

[Frank Dzaebel]

Hallo Alain,
ja, wurde bereits in meinem Link gesagt.
Allerdings will er es hier zurücksetzen (0x84 -> 0x04),
da kommt dann eher:
- Toggle-Semantik: b ^= 128;
- Off-Semantik: b &= 127;

zum tragen.


ciao Frank

[Frank Dzaebel]

Post by Christian Havel
Wie kann ich ermitteln, wieviele der Bits innerhalb eines Byte gesetzt
sind?

Beispielsweise wie in meinem Link die Methode IsBitSet:
Würde ich es für Performance etwa so machen:

private int AnzahlBitsSet(byte b)
{
int anz = ((b & Bit1) == Bit1) ? 1 : 0;
anz += ((b & Bit2) == Bit2) ? 1 : 0;
anz += ((b & Bit3) == Bit3) ? 1 : 0;
anz += ((b & Bit4) == Bit4) ? 1 : 0;
anz += ((b & Bit5) == Bit5) ? 1 : 0;
anz += ((b & Bit6) == Bit6) ? 1 : 0;
anz += ((b & Bit7) == Bit7) ? 1 : 0;
anz += ((b & Bit8) == Bit8) ? 1 : 0;
return anz;
}

private void Form1_Load(object sender, EventArgs e)
{
byte b = 0x84;
int anz = AnzahlBitsSet(b);
}

Es ginge auch eine foreach-Schleife, die
mit 2 mal nimmt, die dann geringfügig
langsamer, aber vielleicht kürzer wäre.


ciao Frank

[Josef Poetzl]

Hallo!

Post by Frank Dzaebel

Post by Christian Havel
Wie kann ich ermitteln, wieviele der Bits innerhalb eines Byte gesetzt
sind?

private int AnzahlBitsSet(byte b)
{
int anz = ((b & Bit1) == Bit1) ? 1 : 0;
anz += ((b & Bit2) == Bit2) ? 1 : 0;
anz += ((b & Bit3) == Bit3) ? 1 : 0;
anz += ((b & Bit4) == Bit4) ? 1 : 0;
anz += ((b & Bit5) == Bit5) ? 1 : 0;
anz += ((b & Bit6) == Bit6) ? 1 : 0;
anz += ((b & Bit7) == Bit7) ? 1 : 0;
anz += ((b & Bit8) == Bit8) ? 1 : 0;
return anz;
}

[...]

Das Berechnen per 2er-Log. ist aus Performance-Sicht nicht brauchbar?
long p = (long)Math.Truncate(Math.Log(b,2));

mfg
Josef

[Frank Dzaebel]

Hallo Josef,

Post by Josef Poetzl

Post by Christian Havel
Wie kann ich ermitteln, wieviele der Bits innerhalb
eines Byte gesetzt sind?

Beispielsweise [...]

Das Berechnen per 2er-Log. ist aus Performance-Sicht nicht brauchbar?
long p = (long)Math.Truncate(Math.Log(b,2));

Nein, das wäre aus funktionaler Sicht nicht gebrauchbar.
Denn bei 0x84 würde es 7 ergeben.
Ergebnis sollte aber 2 sein, denn das Bit für 128 und
das Bit für 4 ist gesetzt. In meinem ersten Link
ist auch eine Methode ShowBits, die Du zur Veranschaulichung
mal benutzen kannst.

private void ShowBits(byte number)
{
StringBuilder sb = new StringBuilder(); int bit = 128;
while (bit != 0)
{
sb.Append(((number & bit) == bit) ? '1' : '0');
bit = bit >> 1;
}
MessageBox.Show(sb.ToString());
}


ciao Frank

[Josef Poetzl]

Hallo!

Post by Frank Dzaebel

Post by Josef Poetzl

Post by Christian Havel
Wie kann ich ermitteln, wieviele der Bits innerhalb
eines Byte gesetzt sind?

Beispielsweise [...]

Das Berechnen per 2er-Log. ist aus Performance-Sicht nicht brauchbar?
long p = (long)Math.Truncate(Math.Log(b,2));

Nein, das wäre aus funktionaler Sicht nicht gebrauchbar.
Denn bei 0x84 würde es 7 ergeben.
Ergebnis sollte aber 2 sein, denn das Bit für 128 und
das Bit für 4 ist gesetzt.

hoppla, wer lesen kann ... ;-)
Es wurde nach der _Anzahl_ gefragt. Ich ging davon aus, dass das
"höchste" Bit ermittelt werden sollte, um dann dieses zu ändern.


Da ich erst beim Einarbeiten in .net bin, erlaube ich mir trotzdem
noch auf das 1. Posting dieses Thread anzuschließen, bei dem - so wie
ich es verstanden habe - das höchste gesetzte bit auf 0 geändert
werden sollte.
Ich hätte das z.B. derzeit so gelöst:

| long z = 0x84;
|
| // "höchstes gesetztes Bit" bestimmten
| long p = (long)Math.Truncate(Math.Log(z,2));
|
| //r = 2^p = Zahlenwert des höchstes Bit
| long x = (long)Math.Pow(2, p);
|
| // höchstes Bit von z entfernen
| long e = z ^ x; //oder: e = z & (x - 1);

Ist das aus ".net-Sicht" passend, oder gibt es eine viel einfachere
Lösung mit weniger Rechenoperationen?

mfg
Josef

[Frank Dzaebel]

Hallo Josef,

Post by Josef Poetzl

Post by Frank Dzaebel
Ergebnis sollte aber 2 sein, denn das Bit für 128 und
das Bit für 4 ist gesetzt.

hoppla, wer lesen kann ... ;-)
Es wurde nach der _Anzahl_ gefragt. Ich ging davon aus, dass das
"höchste" Bit ermittelt werden sollte, um dann dieses zu ändern.

no problem - ja die Anzahl meinte Christian wohl.

Post by Josef Poetzl
noch auf das 1. Posting dieses Thread anzuschließen, bei dem - so wie
ich es verstanden habe - das höchste gesetzte bit auf 0 geändert

Das höchste Bit hat einen Namen bei der Bit-Berechnung,
man nennt es MSB, im Gegensatz zu LSB (Most- und Least
Significant Bit). Bei einem Byte läge das fest auf 128, egal,
was für eine Zahl benutzt wird. Aber es hätte durchaus sein
können, das das gemeint wäre, was Du jetzt geantwortet
hast, nur hat ja Christian schon positiv zu meinen Antworten
gepostet, sodass wohl unsere Interpretation auch die richtige
und dieser Teil der Frage beantwortet ist.

Post by Josef Poetzl
| long x = (long)Math.Pow(2, p);

kann man ggf. performanter mit Shift-Operationen ausdrücken.
Das muss im Einzelfall getestet werden.


ciao Frank

[Frank Dzaebel]

Post by Frank Dzaebel
Das höchste Bit hat einen Namen bei der Bit-Berechnung,
man nennt es MSB, im Gegensatz zu LSB (Most- und Least

hierzu auch ein paar Algorithmen aus Wikipedia,
wenn es in dieser Bedeutung gemeint wäre:

[Most significant bit - Wikipedia, the free encyclopedia]
http://en.wikipedia.org/wiki/Most_significant_bit

->

// C# code to return the index of the MSB. MSB(0)=0
public static int MostSignificantBit (UInt32 n)
{
int b = 0;
if (0 != (n & (~0u << (1 << 4)))) { b |= (1 << 4); n >>= (1 << 4); }
if (0 != (n & (~0u << (1 << 3)))) { b |= (1 << 3); n >>= (1 << 3); }
if (0 != (n & (~0u << (1 << 2)))) { b |= (1 << 2); n >>= (1 << 2); }
if (0 != (n & (~0u << (1 << 1)))) { b |= (1 << 1); n >>= (1 << 1); }
if (0 != (n & (~0u << (1 << 0)))) { b |= (1 << 0); }
return b;
}


ciao Frank

[Josef Poetzl]

Hallo!

Post by Frank Dzaebel

Post by Josef Poetzl
| long x = (long)Math.Pow(2, p);

kann man ggf. performanter mit Shift-Operationen ausdrücken.

.. und würde auch "inhaltlich" gut zum Thema passen.
(wenn schon "e = z ^ x" dann auch gleich "x = 1 << p") ;-)

Danke für die Ausführungen.

mfg
Josef

[René König]

Hallo!

Post by Frank Dzaebel
Es ginge auch eine foreach-Schleife, die
mit 2 mal nimmt, die dann geringfügig
langsamer, aber vielleicht kürzer wäre.

Das ist ganz bestimmt kürzer. Zudem klappt es dann auch mit größeren
Typen. Ich denke auch, dass das nicht notwendigerweise langsamer ist. Je
nach gesetzten Bits stelle ich mir das sogar noch schneller vor.

private int AnzahlBitsSet(long b)
{
int cnt;

for (cnt = 0; b != 0; b >>= 1)
if ((b & 1) != 0)
++cnt;

return cnt;
}

Gruß,
René

[Frank Dzaebel]

Hallo René,

Post by René König
Das ist ganz bestimmt kürzer. Zudem klappt es dann auch mit größeren
Typen. Ich denke auch, dass das nicht notwendigerweise langsamer ist.

Ne, ist durchaus vergleichbar, ist genauso eine
gute Möglichkeit. Es gibt auch noch andere Verfahren,
aber der Unterschied ist oft dermassen gering,
dass ein Tuning hier nur in sehr seltenen Fällen
Sinn macht.


ciao Frank

[Frank Dzaebel]

Hallo René,

Post by Frank Dzaebel

Post by René König
Das ist ganz bestimmt kürzer. Zudem klappt es dann auch mit größeren
Typen. Ich denke auch, dass das nicht notwendigerweise langsamer ist.

Ne, ist durchaus vergleichbar, ist genauso eine
gute Möglichkeit. Es gibt auch noch andere Verfahren, [...]

Etwa soetwas, was noch mal um die Hälfte schneller
ist, als Dein Vorschlag. Hat halt alles Vor-und Nachteile:

int[] BitsSetByte = new int[]
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

private int AnzahlBitsSet(byte b)
{
return BitsSetByte[b];
}


ciao Frank

[Herfried K. Wagner [MVP]]

Post by Frank Dzaebel

Post by Christian Havel
Wie kann ich ermitteln, wieviele der Bits innerhalb eines Byte gesetzt
sind?

private int AnzahlBitsSet(byte b)
{
int anz = ((b & Bit1) == Bit1) ? 1 : 0;
anz += ((b & Bit2) == Bit2) ? 1 : 0;
anz += ((b & Bit3) == Bit3) ? 1 : 0;
anz += ((b & Bit4) == Bit4) ? 1 : 0;
anz += ((b & Bit5) == Bit5) ? 1 : 0;
anz += ((b & Bit6) == Bit6) ? 1 : 0;
anz += ((b & Bit7) == Bit7) ? 1 : 0;
anz += ((b & Bit8) == Bit8) ? 1 : 0;
return anz;

Eine Addition von 0 ist semantisch nicht besonders sinnvoll und müßte auch
vom Compiler/CLR "wegoptimiert" werden. Da wäre es m.E. passender, nur dann
1 zu addieren, wenn das Bit gesetzt ist, und ansonsten keine Addition
durchzuführen. Soll jetzt aber keine Grundsatzdiskussion werden ;-).

[Frank Dzaebel]

Hallo Herfried,

Post by Herfried K. Wagner [MVP]
Eine Addition von 0 ist semantisch nicht besonders sinnvoll

auch physisch nicht ;-)

Also wenn man die Variante nehmen möchte,
und nicht die int-Array-Variante (von 15:46) ist
folgendes ggf. sinnvoller:

private int AnzahlBitsSet(byte b)
{
int anz = 0;
if ((b & Bit1) == Bit1) anz += 1;
if ((b & Bit2) == Bit2) anz += 1;
if ((b & Bit3) == Bit3) anz += 1;
if ((b & Bit4) == Bit4) anz += 1;
if ((b & Bit5) == Bit5) anz += 1;
if ((b & Bit6) == Bit6) anz += 1;
if ((b & Bit7) == Bit7) anz += 1;
if ((b & Bit8) == Bit8) anz += 1;
return anz;
}


ciao Frank

[Marvin Massih]

Hallo Frank,

Post by Frank Dzaebel
if ((b & Bit1) == Bit1) anz += 1;

Wäre ein "anz++" nicht effektiver?
Gibt es (theoretisch) einen Performance-Unterschied zwischen obigem Code
und:

if ((b & Bit1) != 0)

Müsste doch eigentlich auch effektiver sein, oder ("jump if zero" o.ä.)?

Gruß
Marvin

[Frank Dzaebel]

Hallo Marvin,

Post by Marvin Massih

Post by Frank Dzaebel
if ((b & Bit1) == Bit1) anz += 1;

Wäre ein "anz++" nicht effektiver?
Gibt es (theoretisch) einen Performance-Unterschied zwischen obigem Code

Nein, der Compiler setzt das letztlich im Release
eh beides als "anz++" um. Ist eher Geschmackssache,
ob man gerade die 1 im Code sehen will, oder nicht.

Post by Marvin Massih
if ((b & Bit1) != 0)
Müsste doch eigentlich auch effektiver sein, oder ("jump if zero" o.ä.)?

Du meinst, wegen des Prozessorbefehls [JNZ (jump if *not* zero)].
Ne, bringt in diesem Fall nichts. Ist beides gleich
schnell.


ciao Frank

[Marvin Massih]

Hallo Frank,

Post by Frank Dzaebel

Post by Marvin Massih
Wäre ein "anz++" nicht effektiver?
Gibt es (theoretisch) einen Performance-Unterschied zwischen obigem Code

Nein, der Compiler setzt das letztlich im Release
eh beides als "anz++" um. Ist eher Geschmackssache,
ob man gerade die 1 im Code sehen will, oder nicht.

Ok, hatte ich schon vermutet.

Post by Frank Dzaebel

Post by Marvin Massih
if ((b & Bit1) != 0)
Müsste doch eigentlich auch effektiver sein, oder ("jump if zero" o.ä.)?

Du meinst, wegen des Prozessorbefehls [JNZ (jump if *not* zero)].

Na, ich meinte, dass mit einem JZ die Addition übersprungen würde ;-).

Post by Frank Dzaebel
Ne, bringt in diesem Fall nichts. Ist beides gleich
schnell.

Weil nicht messbar oder auch theoretisch nicht?

Gruß
Marvin

[Frank Dzaebel]

Hallo Marvin,

Post by Marvin Massih

Post by Frank Dzaebel

Post by Marvin Massih
if ((b & Bit1) != 0)
Müsste doch eigentlich auch effektiver sein, oder ("jump if zero" o.ä.)?

Du meinst, wegen des Prozessorbefehls [JNZ (jump if *not* zero)].

Na, ich meinte, dass mit einem JZ die Addition übersprungen würde ;-).

? naja, es sollte eigentlich schon mit "!= 0" abgefragt werden.
Aber das Assembler-technisch keinen Unterschied.

Post by Marvin Massih

Post by Frank Dzaebel

Post by Marvin Massih
if ((b & Bit1) != 0)
Müsste doch eigentlich auch effektiver sein, oder ("jump if zero" o.ä.)?

Ne, bringt in diesem Fall nichts. Ist beides gleich
schnell.

Weil nicht messbar oder auch theoretisch nicht?

A) nicht messbar, ja.
B) Der Assembler ergibt etwa:

if (zahl == 5) anz++;
00000067 cmp dword ptr [ebp-40h],5
0000006b setne al
0000006e movzx eax,al
00000071 mov dword ptr [ebp-48h],eax
00000074 cmp dword ptr [ebp-48h],0
00000078 jne 0000007D
0000007a inc dword ptr [ebp-44h]

if (zahl != 0) anz++;
0000007d cmp dword ptr [ebp-40h],0
00000081 sete al
00000084 movzx eax,al
00000087 mov dword ptr [ebp-48h],eax
0000008a cmp dword ptr [ebp-48h],0
0000008e jne 00000093
00000090 inc dword ptr [ebp-44h]

Menü:Fenster/Debuggen/Disassembly.


ciao Frank

[Marvin Massih]

Hallo Frank,

Post by Frank Dzaebel

Post by Marvin Massih

Post by Frank Dzaebel

Post by Marvin Massih
if ((b & Bit1) != 0)
Müsste doch eigentlich auch effektiver sein, oder ("jump if zero" o.ä.)?

Du meinst, wegen des Prozessorbefehls [JNZ (jump if *not* zero)].

Na, ich meinte, dass mit einem JZ die Addition übersprungen würde ;-).

? naja, es sollte eigentlich schon mit "!= 0" abgefragt werden.
Aber das Assembler-technisch keinen Unterschied.

Meine rudimentären Assembler-Kenntnisse beschränken sich auf einen
emulierten Prozessor der Uni.
Ich dachte da an folgenden Pseudo-Code:

10 and b, Bit1
20 jz 40
30 inc b
40 ...

Gruß
Marvin

[Frank Dzaebel]

Hallo Marvin,

Post by Marvin Massih
Meine rudimentären Assembler-Kenntnisse beschränken sich auf einen
emulierten Prozessor der Uni.
10 and b, Bit1
20 jz 40
30 inc b
40 ...

ja, ich weiss, was Du meinst.
Selbst mit direkter Label-Syntax wird das
aber oft nicht mit jz sondern eher über jne umgesetzt.
Gut, ist jetzt ja aber auch nicht mehr direkt wichtig.
Können wir so beenden, denke ich.


ciao Frank

[Thomas Scheidegger]

Hallo Marvin

Post by Marvin Massih
Wäre ein "anz++" nicht effektiver?

MSIL hat keinen separaten Increment-Opcode.
C# generiert typ. eine MSIL-Sequenz wie:
ldloc.0
ldc.i4.1
add
stloc.0

Der x86-JITer (Release+Optimize) optimiert daraus jedoch möglichst:
inc reg

Post by Marvin Massih
if ((b & Bit1) != 0)
Müsste doch eigentlich auch effektiver sein

Ein Test auf <> 0 scheint mindestens 'kompakteren' Code
sowohl in MSIL wie x86-JITer zu erstellen:

// (b & 0x01) != 0

// MSIL:
ldc.i4.1
and
brfalse.s

// x86:
test ecx,1
je t



- - - - - wogegen

// (b & Bit1) == Bit1

// MSIL:
ldc.i4.1
and
ldc.i4.1
bne.un.s

// x86:
and eax,1
cmp eax,1
jne t


Jedoch der Performance-Unterschied scheint mit aktuellen CPUs
(welche heute auf Microcode-Ebene weiter optimieren & parallelisieren)
zu klein
(insbesondere da im sonstigen managed-Code Umfeld!)
um hier eine spürbare Rolle zu spielen.

[Frank Dzaebel]

Hallo Thomas,

Post by Thomas Scheidegger

Post by Marvin Massih
Wäre ein "anz++" nicht effektiver?

MSIL hat keinen separaten Increment-Opcode.

anz++ würdest Du nur in der Release-Assembly
über Reflector bei (anz += 1; oder anz++;) sehen.
Also quasi Pseudo-Code. Der Reflector übersetzt
dies aus einer Assembler-Sequenz. Das zeigt, das
eher kein Unterschied besteht. Der Compiler setzt
das meist in ein und dieselbe Anweisung, etwa:
inc esi
um. Eigentlich stimmen wir hier überein, nur, um das
"anz++" nocheinmal zu detaillieren, falls das falsch
verstanden wurde. Vielleicht nochmal für die anderen,
es ist sehr einfach, sich den Assembler über
Fenster/Debuggen/Disassembly anzuschauen.

Post by Thomas Scheidegger
Ein Test auf <> 0 scheint mindestens 'kompakteren' Code

Der Assembler-Code wurde schon von mir angegeben.
Daraus erkennt man ja schnell die Ähnlichkeit. Wichtig wäre
da auch eher die Taktzyklen-Gleichheit, als Kompaktheit.
Letztlich bleibt immer eine gewisse Compiler-Abhängigkeit;
wichtig: am Ende des Tages wäre ein eventueller
Unterschied zu marginal, als sich um ihn zu kümmern.
Zudem, ist die Umsetzung in Assembler auch nicht
gesichert, könnte sich also auch ändern.


ciao Frank