8 files changed, 54 insertions, 43 deletions
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/divideAndConquer.cpp b/content/other/divideAndConquer.cpp
index 830dc7f..9bd5f0c 100644
--- a/content/other/divideAndConquer.cpp
+++ b/content/other/divideAndConquer.cpp
@@ -5,7 +5,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 	if (j1 < j0) return;
 	int jmid = (j0 + j1) / 2;
 
-	dp[i][jmid] = inf;
+	dp[i][jmid] = INF;
 	int bestk = m0;
 	for (int k = m0; k < min(jmid, m1 + 1); ++k) {
 		if (dp[i - 1][k] + C[k + 1][jmid] < dp[i][jmid]) {
@@ -18,7 +18,7 @@ void rec(int i, int j0, int j1, int m0, int m1) {
 }
 
 ll calc(int n, int m) {
-	dp = vector<vector<ll>>(m, vector<ll>(n, inf));
+	dp = vector<vector<ll>>(m, vector<ll>(n, INF));
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
 	for (int i = 1; i < m; i++) {
 		rec(i, 0, n - 1, 0, n - 1);
diff --git a/content/other/fastSubsetSum.cpp b/content/other/fastSubsetSum.cpp
new file mode 100644
index 0000000..84396f6
--- /dev/null
+++ b/content/other/fastSubsetSum.cpp
@@ -0,0 +1,21 @@
+int fastSubsetSum(vector<int> w, int t){
+	int a = 0, b = 0;
+	while(b < sz(w) && a + w[b] <= t) a += w[b++];
+	if(b == sz(w)) return a;
+	int m = *max_element(all(w));
+	vector<int> dp(2*m, -1), old;
+	dp[m+a-t] = b;
+	for(int i = b; i < sz(w); i++){
+		old = dp;
+		for(int j = 0; j < m; j++){
+			dp[j+w[i]] = max(dp[j+w[i]], old[j]);
+		}
+		for(int j = 2*m-1; j > m; j--){
+			for(int k = max(old[j], 0); k < dp[j]; k++){
+				dp[j-w[k]] = max(dp[j-w[k]], k);
+			}
+		}
+	}
+	for(a = t; dp[m+a-t] < 0; a--);
+	return a;
+}
+\ No newline at end of file
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/knuth.cpp b/content/other/knuth.cpp
index 1d513c8..aa54924 100644
--- a/content/other/knuth.cpp
+++ b/content/other/knuth.cpp
@@ -1,5 +1,5 @@
 ll calc(int n, int m, const vector<vector<ll>>& C) {
-	vector<vector<ll>> dp(m, vector<ll>(n, inf));
+	vector<vector<ll>> dp(m, vector<ll>(n, INF));
 	vector<vector<int>> opt(m, vector<int>(n + 1, n - 1));
 
 	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
diff --git a/content/other/other.tex b/content/other/other.tex
index 7a3c52b..59b5790 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}
@@ -72,6 +72,12 @@
 	\sourcecode{other/sos.cpp}
 \end{algorithm}
 
+\begin{algorithm}{Fast Subset Sum}
+	\method{fastSubsetSum}{findet maximale subset $\mathit{sum}\leq t$}{n \cdot A}
+	Die Laufzeit hängt vom maximalen Wert $A$ in der Menge ab.
+	\sourcecode{other/fastSubsetSum.cpp}
+\end{algorithm}
+
 \begin{algorithm}{Parallel Binary Search}
 	\sourcecode{other/pbs.cpp}
 \end{algorithm}
diff --git a/content/other/pbs.cpp b/content/other/pbs.cpp
index 7cb60e5..f4db2fd 100644
--- a/content/other/pbs.cpp
+++ b/content/other/pbs.cpp
@@ -1,19 +1,19 @@
 // Q = # of queries, bucket sort is sometimes faster
-vector<int> low(Q, 0), high(Q, MAX_OPERATIONS);
+vector<int> low(Q, -1), high(Q, MAX_OPERATIONS);
 while (true) {
 	vector<pair<int, int>> focus;
-	for (int i = 0; i < Q; i++) if (low[i] < high[i]) {
-		focus.emplace_back((low[i] + high[i]) / 2, i);
-	}
+	for (int i = 0; i < Q; i++) {
+		if (low[i] + 1 < high[i]) {
+			focus.emplace_back((low[i] + high[i]) / 2, i);
+	}}
 	if (focus.empty()) break;
 	sort(all(focus));
 
 	// 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;
-}} // answer in low (and high)
+		else low[i] = mid;
+}} // answer in low (MAX_OPERATIONS if never ok)
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);