merge

4 files changed, 23 insertions, 16 deletions

diff --git a/sonstiges/bitOps.cpp b/sonstiges/bitOps.cpp
index 20ca532..b882965 100644
--- a/sonstiges/bitOps.cpp
+++ b/sonstiges/bitOps.cpp
@@ -1,22 +1,15 @@
-// [lsb: 0-th bit, msb: n-th bit,]
-
-//Get j-th bit:
+//lsb: 0-th bit, msb: n-th bit
+//get j-th bit
 (a & (1 << j)) != 0
-
-//Set j-th bit:
+//set j-th bit
 a |= (1 << j)
-
-//Clear j-th bit:
+//clear j-th bit
 a &= ~(1 << j)
-
-//Toggle j-th bit:
+//toggle j-th bit
 a ^= (1 << j)
-
-//Get value of first set bit:
+//get value of least significant bit set
 (a & -a)
-
-//Turn on all bits:
+//turn on all bits
 a = -1
-
-//Turn on first n bits:
+//turn on first n bits (be aware of overflows)
 a = (1 << n) - 1
diff --git a/sonstiges/josephus2.cpp b/sonstiges/josephus2.cpp
new file mode 100644
index 0000000..7676e3c
--- /dev/null
+++ b/sonstiges/josephus2.cpp
@@ -0,0 +1,8 @@
+int rotateLeft(int n) { //returns the number of the last survivor (1 based)
+	for (int i = 31; i >= 0; i--)
+		if (n & (1 << i)) {
+			n &= ~(1 << i);
+			break;
+		}
+	n <<= 1; n++; return n;
+}
\ No newline at end of file
diff --git a/sonstiges/josephusK.cpp b/sonstiges/josephusK.cpp
new file mode 100644
index 0000000..e3fcac2
--- /dev/null
+++ b/sonstiges/josephusK.cpp
@@ -0,0 +1,4 @@
+int josephus(int n, int k) { //returns the number of the last survivor (0 based)
+	if (n == 1) return 0;
+	return (josephus(n - 1, k) + k) % n;
+}
\ No newline at end of file
diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex
index a0e2fb5..255af6a 100644
--- a/sonstiges/sonstiges.tex
+++ b/sonstiges/sonstiges.tex
@@ -15,7 +15,7 @@ Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Buck
 \lstinputlisting{sonstiges/bucketSort.cpp}
 
 \subsubsection{LSD-Radixsort}
-\lstinputlisting{sonstiges/radixsort.cpp}
+\lstinputlisting{sonstiges/radixSort.cpp}
 
 \subsection{Bit Operations}
 \lstinputlisting{sonstiges/bitOps.cpp}
@@ -27,6 +27,8 @@ Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Buck
 $n$ Personen im Kreis, jeder $k$-te wird erschossen.
 \begin{description}
 	\item[Spezialfall $k=2$:] Betrachte Binärdarstellung von $n$. Für $n = 1b_1b_2b_3..b_n$ ist $b_1b_2b_3..b_n1$ die Position des letzten Überlebenden. (Rotiere $n$ um eine Stelle nach links)
+	\lstinputlisting{sonstiges/josephus2.cpp}
 	\item[Allgemein:] Sei $F(n,k)$ die Position des letzten Überlebenden. Nummeriere die Personen mit $0, 1, \ldots, n-1$. Nach Erschießen der $k$-ten Person, hat der Kreis noch Größe $n-1$ und die Position des Überlebenden ist jetzt $F(n-1,k)$. Also: $F(n,k) = (F(n-1,k)+k)\%n$. Basisfall: $F(1,k) = 0$. 
+	\lstinputlisting{sonstiges/josephusK.cpp}
 \end{description}
 \textbf{Beachte bei der Ausgabe, dass die Personen im ersten Fall von $1, \ldots, n$ nummeriert sind, im zweiten Fall von $0, \ldots, n-1$!}