Merge branch 'master' of https://github.com/pjungeblut/ChaosKITs

merge# Bitte geben Sie eine Commit-Beschreibung ein um zu erklären, warum dieser

4 files changed, 69 insertions, 3 deletions

diff --git a/sonstiges/Roman.cpp b/sonstiges/Roman.cpp
new file mode 100644
index 0000000..195f833
--- /dev/null
+++ b/sonstiges/Roman.cpp
@@ -0,0 +1,40 @@
+map<char,int> m; map<int,char> o; 
+int num[7] = {1000,500,100,50,10,5,1};
+
+void buildMap() {
+	m['M'] = 1000; m['D'] = 500; m['C'] = 100; m['L'] = 50; m['X'] = 10; m['V'] = 5; m['I'] = 1; m[' '] = 0;
+	o[1000] = 'M'; o[500] = 'D'; o[100] = 'C'; o[50] = 'L'; o[10] = 'X'; o[5] = 'V'; o[1] = 'I';
+} 
+
+int convertToInt(string &s) {
+	int res = m[s[0]];
+	for(int i = 1; i < s.size(); i++) {
+		if(m[s[i-1]] < m[s[i]])
+			res -= 2*m[s[i-1]];
+		res += m[s[i]];	
+	}
+	return res;
+}
+
+string convertToRoman(int n) {
+	string roman = "";
+	for(int i = 0; i < 7; i++) {
+		while(n >= num[i]) {
+			roman += o[num[i]];
+			n -= num[i];
+		}
+	}
+	int pos = roman.find("CCCC");
+	if(pos != string::npos) roman.replace(pos,4,"CD");
+	pos = roman.find("XXXX");
+	if(pos != string::npos) roman.replace(pos,4,"XL");
+	pos = roman.find("IIII");
+	if(pos != string::npos) roman.replace(pos,4,"IV");
+	pos = roman.find("DCD");
+	if(pos != string::npos) roman.replace(pos,3,"CM");
+	pos = roman.find("LXL");
+	if(pos != string::npos) roman.replace(pos,3,"XC");
+	pos = roman.find("VIV");
+	if(pos != string::npos) roman.replace(pos,3,"IX");
+	return roman;
+}
diff --git a/sonstiges/bitOps.cpp b/sonstiges/bitOps.cpp
new file mode 100644
index 0000000..df8cd8f
--- /dev/null
+++ b/sonstiges/bitOps.cpp
@@ -0,0 +1,22 @@
+[lsb: 0-th bit, msb: n-th bit,]
+
+Get j-th bit:
+(a & (1 << j)) != 0
+
+Set j-th bit:
+a |= (1 << j)
+
+Clear j-th bit:
+a &= ~(1 << j)
+
+Toggle j-th bit:
+a ^= (1 << j)
+
+Get value of first set bit:
+(a & -a)
+
+Turn on all bits:
+a = -1
+
+Turn on first n bits:
+a = (1 << n) - 1
diff --git a/sonstiges/sonstiges.tex b/sonstiges/sonstiges.tex
index 375dc6b..8960a8a 100644
--- a/sonstiges/sonstiges.tex
+++ b/sonstiges/sonstiges.tex
@@ -16,3 +16,9 @@ Wenn die Eingabe aus einem kleinen Intervall $\left[0, n\right)$ stammt ist Buck
 
 \subsubsection{LSD-Radixsort}
 \lstinputlisting{sonstiges/radixsort.cpp}
+
+\subsubsection{Bit Operations}
+\lstinputlisting{sonstiges/bitOps.cpp}
+
+\subsubsection{Roman-Literal-Converting}
+\lstinputlisting{sonstiges/Roman.cpp}
diff --git a/toDo.txt b/toDo.txt
index 3395f15..43482da 100644
--- a/toDo.txt
+++ b/toDo.txt
@@ -1,6 +1,4 @@
 - bitonic tsp
 - josephus problem
 - min cost max flow
-- roman numerals
-- NIM GAMES (WICHTIG)
-- bit operationen (WICHTIG)
\ No newline at end of file
+- bit operationen (WICHTIG)