#include <iostream>
#include <bitset>
#include <string>

using namespace std;

/*
Bit operators
 ^  xor
 |  or
 &  and
 ~  not
 << mult by 2.
 >> divide by 2.

unsigned short int  - 16 bits.
signed = sign bit(uppermost bit) + value
Generally work on unsigned.

*/

void test01()
{
  unsigned short int cr = 0x00;
  unsigned short int s = 0x83;  // 1000 0011

  cout << "Looking at bit operations" << endl;
  cout << "Better to use hex or oct to display the binary representation. " 
    << endl;
  cout << "hex" << hex << cr << endl;
  cout << "hex:" << hex << s << endl;
  cout << "oct:" << oct << s << endl;

}

/* Print out the number in binary. */
void print( unsigned short int k )
{
  cout << endl;
  cout << bool( k & ( 1 << 15) );
  cout << bool( k & ( 1 << 14) );
  cout << bool( k & ( 1 << 13) );
  cout << bool( k & ( 1 << 12) );
cout << ",";
  cout << bool( k & ( 1 << 11) );
  cout << bool( k & ( 1 << 10) );
  cout << bool( k & ( 1 <<  9) );
  cout << bool( k & ( 1 <<  8) );
cout << ",";
  cout << bool( k & ( 1 <<  7) );
  cout << bool( k & ( 1 <<  6) );
  cout << bool( k & ( 1 <<  5) );
  cout << bool( k & ( 1 <<  4) );
cout << ",";
  cout << bool( k & ( 1 <<  3) );
  cout << bool( k & ( 1 <<  2) );
  cout << bool( k & ( 1 <<  1) );
  cout << bool( k & ( 1 <<  0) );
  cout << endl;
}

void test02()
{
  unsigned short int w(23);
  print(w);

}


/*
reset()  - clears all bits
reset(i) - clears i
set()    - sets all bits
test(i)  - tests bit i

any()    - nonzero
count()  - summs bits

flip()   - not
flip(i)  - flip bit i


*/

/*
Problem: cann't get flags.set(i) working in runtime.
  eg flags.set(3) is fine - a compile time bind, but flag.set(i) is failing.

Solution: use the right type. Indexes need size_t, I was using int
 and for some obvious reasons it failed (int is signed to begin with).


*/
void test03()
{
  bitset<16> flags;

  flags.reset();
  size_t a;
  int input;

  cout << endl;
  cout << flags << endl;

  cout << "Enter   {-1,0,1}  bit " << endl;
  cout << "  0 is exit, -1 to unset and 1 to set." << endl;

  for (;;)
  {
    cin >> input;
    if (input==0)
      return;

    cin >> a;

    if (input>0)
      flags[a] = true;
   
    if (input<0)
      flags[a] = false;

    cout << flags << endl;
  }
}


/* Note: erronous use of type, do not follow this code! 
   Instead look at where it went wrong. */
class bitset5
{
  bitset<5> bt;
public:

  void set(int i);
  void reset(int i);

  int const count() const;
  bool const any() const;

  ostream& print(ostream& os) const;
};



ostream& operator << (ostream& os, bitset5 const & b)
{ 
  return b.print(os); 
}


int const bitset5::count() const 
{
  return bt.count();
}

bool const bitset5::any() const
{
  return bt.any();
}

ostream& bitset5::print(ostream& os) const
{
  return os << bt;
}

void bitset5::set(int i)
{
  switch(i)
  {
    case 0:
      bt.set(0);
      break;

    case 1:
      bt.set(1);
      break;

    case 2:
      bt.set(2);
      break;

    case 3:
      bt.set(3);
      break;

    case 4:
      bt.set(4);
      break;
  }
}

void bitset5::reset(int i)
{
  switch(i)
  {
    case 0:
      bt.reset(0);
      break;
                                                                                
    case 1:
      bt.reset(1);
      break;
                                                                                
    case 2:
      bt.reset(2);
      break;
                                                                                
    case 3:
      bt.reset(3);
      break;
                                                                                
    case 4:
      bt.reset(4);
      break;
  }
}


void test04()
{
  cout << "5 switch state machine." << endl << endl;
  cout << "Enter   set-bit reset-bit" << endl;
  cout << "  A bit outside the range [0,4] is ignored." << endl;
  cout << "  Ctrl+C to exit infinite loop." << endl;

  bitset5 flags;
  cout << "flags=" << flags << endl;

  for (int a;;)
  {
    cin >> a;
    flags.set(a);

    cin >> a;
    flags.reset(a);

    cout << "flags=" << flags << endl;
    cout << "count=" << flags.count() << endl;
    cout << "any=" << flags.any() << endl;
  }
}

/* Reference "The C++ Standard Library" by Nicolai M. Josuttis", pages463+.

 My appologies, I did not realize bitset had been around for so long.
 There are better ways to use it than above which is very limited.
 Sorry.

*/


/* Implementing + because STL did not supply the operation. */

template<unsigned int N>
bitset<N>& operator += (bitset<N>& a, bitset<N> const & b)
{
  bool carry=false;
  for(size_t i=0, imax=N; i<imax; ++i)
  {
    if( a[i] )
    {
      if (b[i])
      {
        if (carry) // 1+1+1
          continue;
        else // 1+1+0
        {
          a[i]=false;
          carry=true;
          continue;
        }
      }
      else
      { 
        if (carry) // 1+0+1
        {
          a[i]=false;
          continue;
        }
        else
        { // 1+0+0
          a[i] = true;
          continue;
        }
      }
    }
    else
    {
      if (b[i])
      {
        if (carry) // 0+1+1
          continue;
        else // 0+1+0
        {
          a[i]=true;
          continue;
        }
      }
      else
      {
        if (carry) // 0+0+1
        {
          a[i]=true;
          carry=false;
          continue;
        }
        else
          continue;
      }
    }
  }
}


void test05()
{
  bitset<16> f1(25),f2(string("11")),f3;

  cout << "f1=" << f1 << endl;
  cout << "f2=" << f2 << endl;
                                                                                
  cout << "f1 shifted 2 left." << endl;
  f1 <<= 2;
  cout << "f1=" << f1 << endl;

  cout << "f1 += f2" << endl;
  f1 += f2;
  cout << "f1=" << f1 << endl;

  cout << endl << endl;

  cout << "Testing the add function" << endl;
  cout << "Enter  bool a b" << endl;

  unsigned int a0;
  unsigned int b0;

  bool flag;
  for (;;)
  {
    cin >> flag;
    if (!flag)
      return;

    cin >> a0;
    cin >> b0;

    bitset<32> a(a0);
    bitset<32> b(b0);
    cout << "a=" << a << endl;
    cout << "b=" << b << endl;
    a += b;
    cout << "a+b=" << a << "=" << a.to_ulong() << endl;
                      
  }

  
}


/* Thomas Wang's 32 bit Mix Function */
void hash(bitset<32>& h, bitset<32> const & key ) 
{
  h = key;

  h += ~(h << 15);
  h ^=  (h >> 10);
  h +=  (h << 3);
  h ^=  (h >> 6);
  h += ~(h << 11);
  h ^=  (h >> 10);
}
  
void test06()
{
  unsigned int key;

  cout << "Thomas Wang's 32 bit Mix Function" << endl;
  cout << endl;

  cout << "Enter a non-zero number and view the hash." << endl;
  cout << "Enter 0 to quit." << endl;

  for(;;)
  {
    cin >> key;
    if (key==0)
      return;

    bitset<32> x(key);
    bitset<32> y;
    hash(y,x);

    cout << "key=" << x << endl;
    cout << "hash=" << y << endl;
  }
}


void hash2(unsigned int & h, int const & key )
{
  h = key;
                                                                                
  h += ~(h << 15);
  h ^=  (h >> 10);
  h +=  (h << 3);
  h ^=  (h >> 6);
  h += ~(h << 11);
  h ^=  (h >> 10);
}


void test07()
{

  cout << "Testing that both has functions return the same output" << endl;
  cout << endl;


  unsigned int key;
  cin >> key;

  bitset<32> x(key);
  bitset<32> y;
  hash(y,x);

  cout << "key=" << x << endl;
  cout << "hash=" << y.to_ulong() << endl;

  unsigned int y2;
  hash2(y2,(int)key);
  cout << "hash2=" << y2 << endl; 

}


#include <ctime>
using namespace std;

/*
 * Measuring event times 
 *
 * Usage: 
 *   Call measure() before and after the event being timed.
 *   Call difference functions diff_s() or diff(). 
*/
class aclock
{
  clock_t tv;   // previous time measurement
  clock_t tv2;  // most recent time measurement
public:

  // Call measure() before and after the event.
  void measure()
    { tv = tv2; tv2 = clock(); }

  // Difference in clock cycles. 
  long int const diff()
    { return tv2-tv; }

  /* Difference in milliseconds. */
  double const diff_ms() 
    { return (double const) diff()*( (double const)1000. / (double const) CLOCKS_PER_SEC ); }

  // Difference in seconds
  double const diff_s() 
    { return (double const) diff()/ (double const) CLOCKS_PER_SEC; }

};


void test08()
{
  cout << "Comparing timings of the standard shift operators ";
  cout << "and STL's bitset class." << endl << endl;

  unsigned int long imax=200000;

  aclock c;

  c.measure();
  bitset<32> y;
  for (unsigned int long i=0; i<imax; ++i)
  {
    bitset<32> x(i);
    hash(y,x);
  }
  c.measure();
  cout << c.diff_ms() << "ms" << endl;

  c.measure();
  unsigned int y2;
  for (unsigned int long i=0; i<imax; ++i)
  {
    hash2(y2,(int)i);
  }
  c.measure();
  cout << c.diff_ms() << "ms" << endl;

}

/*
Results on my box for imax=200000
6760
20

Here the standard bit shifting is over 300 times
 faster than using the bitset class. 

 No wonder I have not seen much about bitset on the net.

*/


int main()
{
  test08();


  return 0;
}