#include "float.h"
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <stdlib.h>
#define add(bitset, i) (bitset | (1<<i)) // add element in bit set
#define in(bitset, i) ( (bitset) & (1<< (i) )) // check if the element is in
#define rem(bitset, i) (bitset & ~(1<<i)) // rem element
void print_bitset(int32_t, int32_t);
void print_tab(int*, int32_t);
int32_t next(int32_t, int32_t, int32_t);
void incr(int*, int32_t, int32_t, int*);
void print_binary(int32_t);
int32_t nlz(int32_t);
int32_t find_next_zero_bit(int32_t, int32_t);
/**
* Utility function to display the bitset content
*/
inline void print_bitset(int32_t bs, int32_t n)
{
for(int32_t i=0; i<n; i++) printf("%d:%d ",i ,(in(bs,i)>0 ? 1 : 0));
printf("\n");
}
/**
* Utility function to display the solution
*/
inline void print_tab(int* t, int32_t n)
{
int32_t i;
for(i=0; i -1)
{
ret[0] = 1;
ret[1] = rem(ret[1], sol[i]);
sol[i] = inc;
ret[1] = add(ret[1], inc);
}
}
inline void print_binary(int32_t a)
{
for(int32_t i=0; i< 32; i++)
{
int32_t n = in(a,i);
printf("%d ", (n>0 ? 1 : 0));
}
printf("\n");
}
inline int32_t nlz(int32_t x)
{
int32_t y, m, n;
y = -(x >> 16); // If left half of x is 0,
m = (y >> 16) & 16; // set n = 16. If left half
n = 16 - m; // is nonzero, set n = 0 and
x = x >> m; // shift x right 16.
// Now x is of the form 0000xxxx.
y = x - 0x100; // If positions 8-15 are 0,
m = (y >> 16) & 8; // add 8 to n and shift x left 8.
n = n + m;
x = x << m;
y = x - 0x1000; // If positions 12-15 are 0,
m = (y >> 16) & 4; // add 4 to n and shift x left 4.
n = n + m;
x = x << m;
y = x - 0x4000; // If positions 14-15 are 0,
m = (y >> 16) & 2; // add 2 to n and shift x left 2.
n = n + m;
x = x << m;
y = x >> 14; // Set y = 0, 1, 2, or 3.
m = y & ~(y >> 1); // Set m = 0, 1, 2, or 2 resp.
return n + 2 - m;
}
inline int32_t find_next_zero_bit(int32_t o, int32_t offset)
{
o = o >> offset;
o = ~o;
int32_t mask = o & -o;
return 31 - nlz(((mask) << offset));
}
int32_t main(int32_t argc, char *argv[])
{
clock_t start = clock();
int32_t* solution;
int32_t n = 10; // number of meetings
int32_t i = n-1; // last item index
int32_t bs = 0; // bitset which contains the already tuned meetings
double bound = DBL_MAX;
double currentValue = 0;
int32_t options[2];
solution = (int32_t *) malloc(n * sizeof(int32_t));
for(int32_t j=0; j<n; j++)
{
solution[j] = j;
bs = add(bs, j);
}
//print_bitset(bs, n);
while(i > 0)
{
if(i == n-1 && solution[n-1] > -1)
{
// currentValue = eval(i)
//print_tab(solution, n);
}
if(currentValue < bound)
{
options[1] = bs;
incr(solution, i, n, options);
bs = options[1];
if(options[0]>0)
{
i++;// = (i<n-1 ? i+1 : i-1);
}
else
{
// Set the end of the solution to -1
// (because the first index is 0)
for(int32_t j=i; j<n; j++)
{
bs = rem(bs, solution[j]);
solution[j] = -1;
}
i--;
}
}
else
{
i--;
}
}
printf("%d %f\n", n, ((double)clock() - start) / CLOCKS_PER_SEC);
}
Lambdacrash
#define rem(bitset, i) (bitset & ~(1<<i))
