Merge branch 'master' of /users/13/info/oulamara/Work/../../auvolat/boulot/AlgoProg-Projet

3 files changed, 19 insertions, 6 deletions

diff --git a/algos.c b/algos.c
index 630a719..3d24558 100644
--- a/algos.c
+++ b/algos.c
@@ -53,8 +53,10 @@ void max_clique_b(const graph g, set k, set c, set a, set *mc) {
 // Il est donc de la responsabilité de l'appellant de vérifier qu'à
 // chaque appel les sets sont utilisables et cohérents
 void max_clique_c(const graph g, set k, set c, set a, set *mc) {
+	if (set_size(k) + set_size(c) <= set_size(*mc)) return;
+
 	if (is_set_empty(c)) {
-		if (set_size(k) > set_size(*mc)) {
+		if (set_size(k) > set_size(*mc)) { // useless condition
 			delete_set(*mc);
 			*mc = copy_set(k);
 			printf("Found new max clique: "); dump_set(*mc); fflush(stdout);
diff --git a/graph.c b/graph.c
index a957136..4d3ba2a 100644
--- a/graph.c
+++ b/graph.c
@@ -65,7 +65,6 @@ graph load_graph_dimacs(FILE *stream) {
 		}
 
 		fscanf(stream, " %d %d\n", &a, &b);
-		fprintf(stderr, "Edge: (%d, %d)\n", a, b);
 		a--; b--;
 		set_add_ip(b, k->neighbour[a]);
 		set_add_ip(a, k->neighbour[b]);
diff --git a/set_bitsets.c b/set_bitsets.c
index 7eddcfd..4ac8462 100644
--- a/set_bitsets.c
+++ b/set_bitsets.c
@@ -21,10 +21,22 @@ int nbCells(int n){		//the mathematical ceil function
 }
 
 int nb_one(unsigned long long x) {	//the hamming weight of x
-    int cnt = 0, i;
-    for(i = 0; i < SCOD; i++)
-	cnt+= ((x>>i)&1);
-    return cnt;
+	assert(SCOD==64);
+	
+	//1
+	x = (x & 0x5555555555555555) + ((x >> 1) & 0x5555555555555555);		// mask : 0101010101...
+	//2
+	x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);		// mask : 001100110011...
+	//4
+	x = (x & 0x0F0F0F0F0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F0F0F0F0F);		// mask : 000011110000....
+	//8
+	x = (x & 0x00FF00FF00FF00FF) + ((x >> 8) & 0x00FF00FF00FF00FF);		// etc.
+	//16
+	x = (x & 0x0000FFFF0000FFFF) + ((x >> 16) & 0x0000FFFF0000FFFF);
+	//32
+	x = (x & 0x00000000FFFFFFFF) + ((x >> 32) & 0x00000000FFFFFFFF);
+
+    return x;
 }
 
 int set_size(const set s){