# Bitmaske



## Karplan (21. Januar 2018)

Hi, 
ich will eine Bitmaske (8 Bit) erstellen, dazu hab ich jetzt zwei werte eingescant.
Einmal die Position der ersten Eins und die Anzahl der Einsen, wie muss ich den dann weiter verfahren um eine Bitmaske zu erhalten oder ist das schon die Bitmaske?

Ich würde mich sehr über Erklärungen freuen, und falls jemand eine Quelle hat über die ich mehr Infos über das Thema Bitmaske und Bitmanipulation erhalten kann nätürlich auch.

Lg Karplan


----------



## sheel (21. Januar 2018)

Hi

fürs Verständnis, eine Bitmaske ist eigentlich nur eine Zahl (ohne Kommastellen). Der Name Bitmaske deutet nur auf eine bestimmte Anwendung davon hin, zB. eine andere Zahl so ändern, dass man binär hingeschrieben alle Stellen auf 0 ändert, wo die Maske binär auch 0 ist.
zB. könnte man eine "Maske" 175 haben, binär ist das 10101111, und eine (andere) Zahl 232 (11101000). Die oben beschriebene Anwendung, also in der Zahl alle 1 auf 0 setzen, wenn die Maske dort auch 0 ist, würde dann ergeben: 10101000, und das ist 168-
C bringt sowas auch schon als "Rechenart" mit, ähnlich zu + usw., mit & (nicht &&):

```
int maske = 175;
int zahl = 232;
zahl = zahl & maske;
//zahl ist jetzt 168
```

Analog dazu gibt es zB. "alles in der Zahl auf 1 setzen wenn es in der Maske 1 ist", mit |

(& und | können auch als eine Art von "Und" und "Oder" aufgefasst werden: Nur 1 in der Zahl wenn Zahl "und" Maske dort 1, bzw. wenn Zahl "Oder" Maske (oder beide) 1)

...

Es klingt jetzt jedenfalls danach, dass du eine Zahl zusammenbauen willst, die eine bestimmte Anzahl von 1en hintereinander hat (wenn binär aufgeschrieben). Fürs Erste ein paar Tips:

Was macht der binäre Oder-Operator von oben (also | ), wenn die Maske genau eine 1 hat? In der Zahl wird genau diese Stelle auch auf 1 gesetzt (egal ob es zuerst 0 oder 1 war).

Mit einem weiteren Operator, Links-Shift <<, kann man sich solche Zahlen (mit nur einer eins an verschiedenen Positionen) zusammenbauen. Ein paar Beispiele, mit denen es vermutlich klar wird:
1<<0 in C ist 1 und binär 00000001.
1<<1 ist 2 und binär 00000010.
1<<2 ist 4 und binär 00000100.
1<<3 ist 8 und binär 00001000.
1<<4 ist 16 und binär 00010000.
...
Nur aufpassen dass man nicht mehr Bit verwendet, als die Variable hat (int zB. 32 (mindestens), wobei das Erste aber für +/- sein kann, usw.)

Wenn du jetzt deine Startposition und Anzahl der Bits hast, in einer Schleife einfach Bit für Bit an den passenden Stellen auf 1 setzen...


----------



## Technipion (21. Januar 2018)

Hallo Karplan,
die alten C-ler werden gleich wieder ausflippen, aber im Prinzip spricht auf heutigen Systemen absolut nichts dagegen sowas hier zu machen:

```
bool mask[8];
```
Dabei "verschwendest" du zwar ein paar Byte, aber oft geht die Lesbarkeit dadurch hoch und die Komplexität runter. Hast du denn einen konkreten Anwendungsfall, bei dem du Bitmasken benötigst?
Ansonsten hat sheel im Prinzip schon alles gesagt.

Gruß Technipion


----------



## ComFreek (22. Januar 2018)

@Technipion Konzeptionell stimme ich dir vollkommen zu! Wenn man auf Bitmasken arbeitet, verhält sich der Integer (bzw. der Speicher/das Register, auf das er abgebildet wurde durch den Compiler) wie ein bool[sizeof(int) * 8].
In deinem Fall ist es jedoch aus der Programmierersicht komplizierter auf mindestens einen Wert zu prüfen: mask[0] || mask[1] || ... || mask[7]. Oder man hat bereits eine Maske gegeben und möchte prüfen, ob diese Maske eine (ggf. unechte) Teilmenge einer anderen Maske ist:

Maske a ist Teilmenge von Maske b, wenn für jedes Bit aus a gilt, dass es das jeweilige Bit von b impliziert: (a[0] => b[0]) && (a[1] => b[1]) && (a[2] => b[2]) && ...
(=> ist hier keine C-Syntax, sondern die Implikation)
(x => y) kann man allgemein durch (~x | y) ersetzen, d.h. wir prüfen nun: (~a[0] | b[0]) && (~a[1] | b[1]) oder äquivalent: (~a | b) == 111...111 (nur Einser)
Auf 0 testen könnte einfacher sein: ~(~a | b) == 0 oder äquivalent: (a & ~b) == 0
Wen Bit Twiddling noch mehr interessiert: https://graphics.stanford.edu/~seander/bithacks.html


----------



## cwriter (22. Januar 2018)

Technipion hat gesagt.:


> die alten C-ler werden gleich wieder ausflippen,


Alter C-ler, meldet sich zum Dienst! 

Bitfields aus bools sind für Computer schlecht. Die Grösse sorgt für geringere Cache-Lokalität, die Byte- statt Bitgrössen für mehrere Speicherzugriffe (von Caches abgefedert, aber dennoch), und die Iterationsnatur für mehr Cycles (hier helfen SIMD-Instruktionen, aber auch das ist eine Annahme. Zum Vergleich: Die meisten Linuxdistributionen zielen auf i586, damals gab es nicht nicht so viele Gimmicks).

Dazu kommt natürlich, dass Bitmasks normalerweise für Hardwareregister eingesetzt werden, die ausschliesslich mit Bits arbeiten.
Falls nur die Lesbarkeit ein Problem sein sollte, gibt es 2 Möglichkeiten:
1) Die Erweiterung der Bitfields:

```
struct bitfield {
    int bit0 : 1;
    int bit1 : 1;
    //...
} bitfield;
```
Wodurch die Syntax angeglichen wird (ganz normales Setzen der Bits mit = 1, der Compiler macht den Rest.
Der grosse Nachteil: Die Reihenfolge ist nicht standardisiert und generell kann jeder Compiler machen, was er will. In der Praxis gilt aber i.d.R. gcc, welcher (meines Wissens) mit dem 0. bit oben beginnt und nach unten wächst, zumindest unter LE.
Es ist aber empfehlenswert, immer zu testen!

Oder dann mittels enum / defines / Konsorten:

```
enum bitfield
{
    bit0 = (1 << 0),
    bit1 = (1 << 1),
    //...
};
```
Beide Varianten können kombiniert und direkt gesetzt werden, z.B. kann man im enum auch einzelne bitflags gruppieren, z.B. comb1 = bit1 | bit2 für die Maske 0b110.
Die Struct-Variante kann man relativ einfach auf primitive Typen umcasten, was vieles erleichtert.



Technipion hat gesagt.:


> Dabei "verschwendest" du zwar ein paar Byte, aber oft geht die Lesbarkeit dadurch hoch und die Komplexität runter.


Auf grossen, starken Systemen ist das in der Regel kein Problem, aber auf Mikrokontrollern kämpft man um jedes Byte und jede Instruktion.

Ansonsten wurde schon alles gesagt.

Gruss
cwriter


----------



## Karplan (25. Januar 2018)

Hallo,
@sheel @Technipion @ComFreek @cwriter 

danke für alle eure Antworten.
Was eine Bitmaske ist habe ich jetzt dank euch verstanden, ich hab jetzt auch schon ein Programm geschrieben bei dem ich eingebe kann an welcher stelle die erste 1 steht und die anzahl der Benachbarten 1sen.


```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main(void)


{
uint8_t index;
uint8_t length;
uint8_t mask[8] = { 0 };


printf ("Position der ersten 1 eingeben\n");
scanf_s("%hhu", &index);
printf("Anzahl der 1sen eingeben\n");
scanf_s("%hhu", &length);

if (index < length || index > 8)

   {
        printf("Fehler");
        system("pause");
        return(0);
    }
    else {
        index = index - 1; // Weil Array von 0-7 platz hat
        while (index != 0) {
            if (length > 0) {
                mask[length] = 1;
                length = length - 1;
            }
            else {}
            index = index - 1;
        }
    }
    for (int i = 0; i < 8;) {
        printf("%hhu", mask[i]);
        i++;
    }
}
```

Meine Frage wäre jetzt ob ich das so umsetzen kann, ich erhalte jetzt ja jetzt meine Zahl für die "Bitmaske" aus meinen zwei eingegebenen Werten als Binärzahl. Hätte jemand noch eine andere Umsetzung für mein Programm?
Oder Ratschläge wie ich es noch verbessern/ verändern könnte.

Lg Karplan


----------



## cwriter (25. Januar 2018)

Karplan hat gesagt.:


> Oder Ratschläge wie ich es noch verbessern/ verändern könnte.




```
uint8_t index;
uint8_t length;

//index und length mit Werten füllen. (index 0 ist hier MSB, die Umkehrung ist aber nicht schwer)

assert(index + length < 8);
assert(index < 8);
assert(length > 0);

uint8_t mask = 0;
const int8_t shifter = (1 << 7); //0b10000000
uint8_t mask1 = (uint8_t)(shifter >> (index + length - 1));
uint8_t mask2 = (uint8_t)((shifter >> index) << 1);

mask = mask1 ^ mask2;
```
Einschränkungen:
1) two's-complement-system
2) Compiler mit arithmetischem shift

(Praktisch alle x86-CPUs und fast alle Chips sind so, einzige Ausnahme sind einige wenige Modems aus alten Zeiten und uralt-Maschinen)

Eine Erklärung dazu:
Wir nehmen shifter als ein signed-byte. D.h. der Wert, der zugewiesen wird (1 << 7), ist -128. Da das logische Shiften eine /2-Operation sein will, muss das auch auf negative Zahlen funktionieren (bzw. wurde einfach so definiert). Daher ist ein Shift von negativen Zahlen im two's-complement ein Shift, der das MSB kopiert:

```
int8_t  a = (1 << 7); //-128, 0b10000000
uint8_t b = (1 << 7); //128, 0b10000000
int8_t c = (1 << 6); //64, 0b01000000

// a >> 1 == -64 (0b11000000)
//b >> 1 == 64 (0b01000000)
//c >> 1 == 32 (0b00100000)
```


```
Am Beispiel von Index = 2, Length = 4: Wir erwarten 0b00111100
Nun macht der Code folgendes:
(shifter >> (index + length-1):
((1 << 7) >> (6-1)) == 0b11111100
Das ist nun mask1,

Dann müssen nur noch die ersten paar Bits aufgeräumt werden:
(shifter >> index) << 1:
((1 << 7) >> 2) << 1 == 0b11100000 << 1 == 0b11000000
Das ist mask2.

Als letztes noch XOR (gleiche Bits werden 0, ungleiche werden 1):
mask1 ^ mask2 ==
0b11111100 ^
0b11000000 ==
0b00111100
```



Karplan hat gesagt.:


> Meine Frage wäre jetzt ob ich das so umsetzen kann, ich erhalte jetzt ja jetzt meine Zahl für die "Bitmaske" aus meinen zwei eingegebenen Werten als Binärzahl.


Du bekommst zumindest keine Bitmaske, da du damit ja eigentlich nichts maskieren kannst (kein &).
Um aus deinem Array wieder eine Bitmaske zu basteln, ginge so etwas:

```
uint8_t bitmask = 0;
for(size_t i = 0; i < 8; ++i)
    bitmask |= (mask[i] & 1) << i)
```
Das ist eine andere Reihenfolge als in meinem Codevorschlag. Wenn du es umgekehrt haben willst:
uint8_t bitmask = 0;
for(size_t i = 0; i < 8; ++i)
    bitmask |= (mask[7 - i] & 1) << i)
[/code]
Aber wie du ja selbst sehen kannst, ist mein Codevorschlag wesentlich kürzer (und das unoptimiert).
Es bietet sich gerade für C-Programmierer sehr an, die Bitoperationen im Schlaf zu können.

Hier noch eine bessere/direktere Version:

```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
int main(int argc, char* argv[])
{
        uint8_t index = 2;
        uint8_t length = 0;
        assert(index + length < 8);
        assert(index < 8);


        uint8_t mask = 0;
        const int8_t shifter = (1 << 7); //0b10000000
        uint8_t tmp = (shifter << (length == 0)) >> (length - (length != 0));
        mask = tmp >> index;


        printf("0b");
        for(size_t i = 0; i < 8; ++i)
                printf("%d", mask & (1 << (7-i)) ? 1 : 0);
        return 0;
}
```
# Ops: 1 cmp, 1 shl, 1 sar, 1 shr, 1 sub, 2 sete (idealerweise, der Compiler hat natürlich anderes im Sinn...)
Wenn length als > 0 definiert ist, wird es sehr viel einfacher:

```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
int main(int argc, char* argv[])
{
        uint8_t index = 2;
        uint8_t length = 0;
        assert(index + length < 8);
        assert(index < 8);
        assert(length > 0);


        uint8_t mask = 0;
        const int8_t shifter = (1 << 7); //0b10000000
        uint8_t tmp = shifter >> (length - 1);
        mask = tmp >> index;


        printf("0b");
        for(size_t i = 0; i < 8; ++i)
                printf("%d", mask & (1 << (7-i)) ? 1 : 0);
        return 0;
}
```

//Als kleines Zückerchen, nur für mich: (ARMv6 assembly)

```
//r0: index
//r1: length
subs r1, #1
eorlt r0, r0 //Falls r1 - 1 negativ war (r1 war 0), setze r0 auf 0
blt lr //Beende, falls r1 0 war.
mvn r2, 0x7f, asr r1 //r2 = -128 >> r1
mov r0, r2, lsr r0
and r0, #0xFF
//resultat in r0, nun bx lr, falls in Funktion
```
(Ungetestet, sollte aber funktionieren. Man beachte die Schönheit von 6 Instruktionen (24 Bytes, 28 Bytes als Funktion)). Irgendetwas habe ich sicher übersehen; 1-3 Instruktionen könnten wohl gespart werden.

Diese Kürze bekommt man nur durch Bitoperationen selbst. Die char-Array-Variante dürfte ein Vielfaches davon kosten.


Gruss
cwriter

//Edit: Auch ein schöner Hack:

```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
int main(int argc, char* argv[])
{
        uint8_t index = 2;
        uint8_t length = 0;
        assert(index + length < 8);
        assert(index < 8);


        uint8_t mask = 0;
        const uint16_t shifter = 0xFF00;
        uint8_t tmp = shifter >> length; //Shifte nach rechts und kürze (truncate) auf 8 bits
        mask = tmp >> index; //Shifte den Index


        printf("0b");
        for(size_t i = 0; i < 8; ++i)
                printf("%d", mask & (1 << (7-i)) ? 1 : 0);
        return 0;
}
```
Damit fallen alle Überprüfungen auf 0 und alle Arithmetischen Shifts weg und es ist noch ein bisschen übersichtlicher.


----------

