Bitmanipulation - Standard C - DeMorgan Umformung

Das Theorem von De Morgan besagt, dass sich die Aussage einer binären, logischen Verknüpfung umkehrt (invertiert), wenn man die Eingangsgrößen invertiert und die Verknüpfung von UND nach ODER bzw. ODER nach UND ändert. Dieses Gesetz nutzt man oft bei der logischen Minimierung von Schaltgleichungen oder zur Umwandlung in einheitliche Verknüpfungen (z.B. alle Gatter in einer Schaltung in NAND-Gatter umwandeln). Im Softwarebereich wird sie eher selten verwendet.

   a  &  b  ==  c;    // Original mit AND-Logik
!( a  &  b) == !c;    // invertiert, NAND-Logik
  !a  | !b  == !c;    // Invertierung aufgelöst (De Morgan)  
!(!a  | !b) ==  c;    // invertierte Eingangssignale, NOR-Logik

   a  |  b  ==  c;    // Original mit OR-Logik
 !(a  |  b) == !c;    // invertiert, NOR-Logik    
  !a  & !b  == !c     // Invertierung aufgelöst (De Morgan)
!(!a  & !b) ==  c;    // invertierte Eingangssignale, NAND-Logik

Bei folgendem Code mit binären Präfixen handelt es sich nicht um Standard-C, sondern um eine häufig implementierte Erweiterung. Der GNU C/C++ Compiler unterstützt sie seit Version 4.3, genauso wie etwa CLANG und SDCC. Alle aktuellen, auf GCC basierenden Toolchains (AVRGCC,Arduino,MSP430-GCC usw.) sollten diese Erweiterung inzwischen unterstützen.

Wichtiger Hinweis: Die ODER/UND-Verknüpfung und die anschliessende Invertierung kann man nicht vertauschen, darum sind auch die Klammern wichtig! Bei der Verknüpfung von Bitmustern ist zu beachten, dass die Verknüpfung bitweise erfolgt, im Gegensatz zur logischen Verknüpung im 1. Beispiel, wo sie für den logischen Wert insgesamt erfolgt.

 ~(0b0001 |  0b0010) == 0b1100
  ~0b0001 & ~0b0010  == 0b1100