From ac2d9ad3f2c88bc12420fc439e8d0b4775a11169 Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Fri, 30 Aug 2024 15:04:20 +0200
Subject: various small improvements

---
 content/other/bitOps.cpp    |  7 -------
 content/other/josephus2.cpp |  9 +++------
 content/other/other.tex     | 34 +++++++++++++++++++++-------------
 content/other/pbs.cpp       |  3 +--
 content/other/recover.cpp   | 12 ++++++++++++
 content/other/stuff.cpp     |  6 ------
 6 files changed, 37 insertions(+), 34 deletions(-)
 create mode 100644 content/other/recover.cpp

(limited to 'content/other')

diff --git a/content/other/bitOps.cpp b/content/other/bitOps.cpp
index 8079305..6230c86 100644
--- a/content/other/bitOps.cpp
+++ b/content/other/bitOps.cpp
@@ -3,13 +3,6 @@
 for (int subset = bitmask; subset > 0;
      subset = (subset - 1) & bitmask)
 
-// Zählt Anzahl der gesetzten Bits.
-int numberOfSetBits(int i) {
-	i = i - ((i >> 1) & 0x5555'5555);
-	i = (i & 0x3333'3333) + ((i >> 2) & 0x3333'3333);
-	return (((i + (i >> 4)) & 0x0F0F'0F0F) * 0x0101'0101) >> 24;
-}
-
 // Nächste Permutation in Bitmaske
 // (z.B. 00111 => 01011 => 01101 => ...)
 ll nextPerm(ll v) {
diff --git a/content/other/josephus2.cpp b/content/other/josephus2.cpp
index 5086e13..33544ea 100644
--- a/content/other/josephus2.cpp
+++ b/content/other/josephus2.cpp
@@ -1,8 +1,5 @@
 int rotateLeft(int n) { // Der letzte Überlebende, 1-basiert.
-	for (int i = 31; i >= 0; i--) {
-		if (n & (1 << i)) {
-			n &= ~(1 << i);
-			break;
-	}}
-	n <<= 1; n++; return n;
+	int bits = __lg(n);
+	n ^= 1 << bits;
+	return 2 * n + 1;
 }
diff --git a/content/other/other.tex b/content/other/other.tex
index b47893f..e8d8041 100644
--- a/content/other/other.tex
+++ b/content/other/other.tex
@@ -13,6 +13,19 @@
 	\sourcecode{other/timed.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Overflow-sichere arithmetische Operationen}
+	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
+	\begin{expandtable}
+		\begin{tabularx}{\linewidth}{|lR|}
+			\hline
+			Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
+			Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
+			Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
+			\hline
+		\end{tabularx}
+	\end{expandtable}
+\end{algorithm}
+
 \begin{algorithm}{Bit Operations}
 	\begin{expandtable}
 	\begin{tabularx}{\linewidth}{|Ll|}
@@ -31,19 +44,6 @@
 	\sourcecode{other/bitOps.cpp}
 \end{algorithm}
 
-\begin{algorithm}{Overflow-sichere arithmetische Operationen}
-	Gibt zurück, ob es einen Overflow gab. Wenn nicht, enthält \code{c} das Ergebnis.
-	\begin{expandtable}
-		\begin{tabularx}{\linewidth}{|lR|}
-			\hline
-			Addition & \code{__builtin_saddll_overflow(a, b, &c)} \\
-			Subtraktion & \code{__builtin_ssubll_overflow(a, b, &c)} \\
-			Multiplikation & \code{__builtin_smulll_overflow(a, b, &c)} \\
-			\hline
-		\end{tabularx}
-	\end{expandtable}
-\end{algorithm}
-
 \begin{algorithm}{Pragmas}
 	\sourcecode{other/pragmas.cpp}
 \end{algorithm}
@@ -95,6 +95,14 @@
 	\textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $\boldsymbol{1, \ldots, n}$ nummeriert sind, im zweiten Fall von $\boldsymbol{0, \ldots, n-1}$!}
 \end{algorithm}
 
+\vfill\null\columnbreak
+
+\subsection{Recover $\boldsymbol{x}$ and $\boldsymbol{y}$ from $\boldsymbol{y}$ from $\boldsymbol{x\*y^{-1}}$ }
+\method{recover}{findet $x$ und $y$ für $x=x\*y^{-1}\bmod m$}{\log(m)}
+\textbf{WICHTIG:} $x$ und $y$ müssen kleiner als $\sqrt{\nicefrac{m}{2}}$ sein!
+\sourcecode{other/recover.cpp}
+
+
 \begin{algorithm}[optional]{Zeileneingabe}
 	\sourcecode{other/split.cpp}
 \end{algorithm}
diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp
index 7cb60e5..5508d6c 100644
--- a/content/other/pbs.cpp
+++ b/content/other/pbs.cpp
@@ -10,9 +10,8 @@ while (true) {
 
 	// reset simulation
 	for (int step = 0; auto [mid, i] : focus) {
-		while (step <= mid) {
+		for (; step <= mid; step++) {
 			// simulation step
-			step++;
 		}
 		if (/* requirement already fulfilled */) high[i] = mid;
 		else low[i] = mid + 1;
diff --git a/content/other/recover.cpp b/content/other/recover.cpp
new file mode 100644
index 0000000..0d3c3ea
--- /dev/null
+++ b/content/other/recover.cpp
@@ -0,0 +1,12 @@
+ll sq(ll x) {return x*x;}
+
+pair<ll, ll> recover(ll c, ll m) {
+	array<ll, 3> u = {1, 0, m}, v = {0, 1, c};
+	while (m <= 2 * sq(v[2])) {
+		ll q = u[2] / v[2];
+		for (int i : {0, 1, 2}) u[i] -= q * v[i];
+		swap(u, v);
+	}
+	if (v[1] < 0 || 2 * sq(v[1]) >= m) return {-1, -1};
+	return {v[2], v[1]};
+}
diff --git a/content/other/stuff.cpp b/content/other/stuff.cpp
index 41543ad..e4e37e2 100644
--- a/content/other/stuff.cpp
+++ b/content/other/stuff.cpp
@@ -1,13 +1,7 @@
-// Alles-Header.
-#include <bits/stdc++.h>
-
 // Setzt deutsche Tastaturlayout / toggle mit alt + space
 setxkbmap de
 setxkbmap de,us -option grp:alt_space_toggle
 
-// Schnelle Ein-/Ausgabe mit cin/cout.
-cin.tie(nullptr)->ios::sync_with_stdio(false);
-
 // Set mit eigener Sortierfunktion.
 set<point2, decltype(comp)> set1(comp);
 
-- 
cgit v1.2.3