From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- other/bitOps.cpp | 40 ++++++++++++++++++---------------------- 1 file changed, 18 insertions(+), 22 deletions(-) (limited to 'other/bitOps.cpp') diff --git a/other/bitOps.cpp b/other/bitOps.cpp index ecb94fa..9666187 100644 --- a/other/bitOps.cpp +++ b/other/bitOps.cpp @@ -1,22 +1,18 @@ -// Bit an Position j auslesen. -(a & (1 << j)) != 0 -// Bit an Position j setzen. -a |= (1 << j) -// Bit an Position j löschen. -a &= ~(1 << j) -// Bit an Position j umkehren. -a ^= (1 << j) -// Wert des niedrigsten gesetzten Bits. -(a & -a) -// Setzt alle Bits auf 1. -a = -1 -// Setzt die ersten n Bits auf 1. Achtung: Overflows. -a = (1 << n) - 1 -// Iteriert über alle Teilmengen einer Bitmaske (außer der leeren Menge). -for (int subset = bitmask; subset > 0; subset = (subset - 1) & bitmask) -// Anzahl der gesetzten Bits. -int __builtin_popcount(unsigned int x); -int __builtin_popcountll(unsigned long long x); -// Anzahl der führenden 0-Bits. -int __builtin_clz(unsigned int x); -int __builtin_clzll(unsigned long long x); +// Iteriert über alle Teilmengen einer Bitmaske +// (außer der leeren Menge). +for (int subset = bitmask; subset > 0; + subset = (subset - 1) & bitmask) + +// Zählt Anzahl der gesetzten Bits. +int numberOfSetBits(int i) { + i = i - ((i >> 1) & 0x55555555); + i = (i & 0x33333333) + ((i >> 2) & 0x33333333); + return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; +} + +// Nächste Permutation in Bitmaske +// (z.B. 00111 => 01011 => 01101 => ...) +ll nextPerm(ll v) { + ll t = v | (v - 1); + return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctzll(v) + 1)); +} -- cgit v1.2.3