naoya_t@topcoder

Bits

11:59 |

ビット列の論理演算クラスを試作。

AND,OR,XOR,NOTとか。今日の問題が通る程度の実装。

• 内部でメモリを確保して、8ビット最密充填
• 演算子オーバーロードを使えば配列的記法で（a=bits[201];みたいに）特定ビットの内容を取って来ることはできるが、代入（bits[201]=1; みたいな）ができないのが残念。で、代入やられると危険なのでオーバーロードしてない。

//
// Bits.h - (c)2009 by naoya_t
//
// ライセンスは NYSL 0.9982に従います http://www.kmonos.net/nysl/
//
#include <string>
#include <iostream>
#include <sstream>
using namespace std;

class Bits {
  unsigned char *data;
  int data_bytesize;
  int data_size;

public:
  Bits() { data = NULL; data_size = 0; }
  Bits( int size, int initial_value=0 ) { data = NULL; init(size,initial_value); }
  Bits( const Bits& bits ) { data = NULL; init(bits); }
  virtual ~Bits() { dealloc_data(); }

  const int size() { return data_size; }
  const int popcount();

  void dealloc_data() { if (data) { free((void*)data); data = NULL; } }

  Bits &init( int size, int initial_value=0 );
  Bits &init( const Bits& bits );
  Bits &operator=( const Bits& bits ) { dealloc_data(); return init( bits ); }

  void set( int offset, int value=1 );
  void unset( int offset );
  int get( int offset );

  Bits &operator&=(const Bits& other);
  Bits &operator|=(const Bits& other);
  Bits &operator^=(const Bits& other);

  Bits &operator+=(const Bits& other); //concat

  Bits operator&(const Bits& other) { Bits result(*this); result &= other; return result; }
  Bits operator|(const Bits& other) { Bits result(*this); result |= other; return result; }
  Bits operator^(const Bits& other) { Bits result(*this); result ^= other; return result; }
  Bits operator‾();

  Bits operator+(const Bits& other) { Bits result(*this); result += other; return result; }

  string desc();
};

const int
Bits::popcount()
{
  int cnt = 0;
  int fullsize = data_size >> 3;
  for (int i=0; i<fullsize; i++)
    cnt += __builtin_popcount(data[i]);
  if (fullsize < data_bytesize) {
    int rest_bitsize = data_size % 8; // 1..7
    int mask = 127 >> (7 - rest_bitsize); // 1...127
    cnt += __builtin_popcount((int)data[fullsize] & mask);
  }
  return cnt;
}

Bits &
Bits::init( int size, int initial_value )
{
  dealloc_data();
  data_size = size; data_bytesize = (size + 7) >> 3;
  data = (unsigned char *)malloc( data_bytesize );
  memset( data, initial_value ? 255 : 0, data_bytesize );
  return *this;
}
Bits &
Bits::init( const Bits& bits )
{
  dealloc_data();
  data_size = bits.data_size; data_bytesize = bits.data_bytesize;
  data = (unsigned char *)malloc( data_bytesize );
  memcpy( data, bits.data, data_bytesize );
  return *this;
}

void
Bits::set( int offset, int value )
{
  if (offset < 0 || data_size <= offset) return; // invalid.
  if (!data) return;

  int byteofs = offset >> 3, bitofs = offset % 8;
  if (value)
    data[byteofs] |= (1 << bitofs);
  else
    data[byteofs] &= (~(1 << bitofs));
}
void
Bits::unset( int offset )
{
  if (offset < 0 || data_size <= offset) return; // invalid.
  if (!data) return;

  int byteofs = offset >> 3, bitofs = offset % 8;
  data[byteofs] &= (~(1 << bitofs));
}
int
Bits::get( int offset )
{
  if (offset < 0 || data_size <= offset) return -1; // invalid.
  if (!data) return -1;

  int byteofs = offset >> 3, bitofs = offset % 8;
  return (data[byteofs] & (1 << bitofs)) ? 1 : 0;
}

Bits &
Bits::operator&=(const Bits& other)
{
  if (data_size < other.data_size) {
    // 自分.size < 相手.size
    for (int i=0; i<data_bytesize; i++) data[i] &= other.data[i];
    // 残りは捨てられる
  } else {
    // 自分.size >= 相手.size
    int fullsize = other.data_size >> 3;
    for (int i=0; i<fullsize; i++)
      data[i] &= other.data[i];
    if (fullsize < other.data_bytesize) {
      int rest_bitsize = other.data_size & 7;
      int mask = 127 >> (7 - rest_bitsize);
      int rest = other.data[fullsize] & mask;
      data[fullsize++] &= rest;
    }
    // 足りない分はzero
    for (int i=fullsize; i<data_bytesize; i++) data[i] = 0; // data[i] &= 0;
  }
  return *this;
}

Bits &
Bits::operator|=(const Bits& other)
{
  if (data_size < other.data_size) {
    // 自分.size < 相手.size
    for (int i=0; i<data_bytesize; i++) data[i] |= other.data[i];
    // 残りは捨てられる
  } else {
    // 自分.size >= 相手.size
    int fullsize = other.data_size >> 3;
    for (int i=0; i<fullsize; i++)
      data[i] |= other.data[i];
    if (fullsize < other.data_bytesize) {
      int rest_bitsize = other.data_size % 8;
      int mask = 127 >> (7 - rest_bitsize);
      int rest = other.data[fullsize] & mask;
      data[fullsize++] |= rest;
    }
    // 足りない分は放置
    // for (int i=fullsize; i<data_bytesize; i++) data[i] |= 0;
  }
  return *this;
}

Bits &
Bits::operator^=(const Bits& other)
{
  if (data_size < other.data_size) {
    // 自分.size < 相手.size
    for (int i=0; i<data_bytesize; i++) data[i] ^= other.data[i];
    // 残りは捨てられる
  } else {
    // 自分.size >= 相手.size
    int fullsize = other.data_size >> 3;
    for (int i=0; i<fullsize; i++)
      data[i] ^= other.data[i];
    if (fullsize < other.data_bytesize) {
      int rest_bitsize = other.data_size % 8;
      int mask = 127 >> (7 - rest_bitsize);
      int rest = other.data[fullsize] & mask;
      data[fullsize++] ^= rest;
    }
    // 足りない分は放置
    // for (int i=fullsize; i<data_bytesize; i++) data[i] ^= 0;
  }
  return *this;
}

Bits
Bits::operator~()
{
  Bits not_this(*this);
  for (int i=0; i<data_bytesize; i++) not_this.data[i] = ‾not_this.data[i];
  return not_this;
}

Bits &
Bits::operator+=(const Bits& other)
{
  unsigned char *old_data = data; data = NULL;
  int old_data_size = data_size, old_data_bytesize = data_bytesize;
  init( old_data_size + other.data_size );
  memcpy( data, old_data, old_data_bytesize );
  for (int i=0; i<other.data_size; i++)
    set( old_data_size + i, ((Bits)other).get(i) );
  free( (void*)old_data );
  return *this;
}

string
Bits::desc()
{
  stringstream s;
  for (int i=0; i<data_size; i++) s << get(i);
  return s.str();
}

ostream& operator<<(ostream &s, Bits bits)
{
  s << bits.desc();
  return s;
}

テスト

googletestで

% g++ Bits-test.cc -lgtest

% ./a.out

#include <gtest/gtest.h>
#include "Bits.h"
//#include <string>
//using namespace std;

TEST(Bits,ctor)
{
  Bits z(1), a(3,1), b(5,1), c(7,0), d(9), e(11,1);

  EXPECT_EQ("0", z.desc() );
  EXPECT_EQ("111", a.desc() );
  EXPECT_EQ("11111", b.desc() );
  EXPECT_EQ("0000000", c.desc() );
  EXPECT_EQ("000000000", d.desc() );
  EXPECT_EQ("11111111111", e.desc() );
}

TEST(Bits,set)
{
  Bits a(10);
  EXPECT_EQ("0000000000", a.desc() );
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) a.unset(i);
  EXPECT_EQ("0010100010", a.desc() );
  for (int i=0; i<10; i+=5) a.set(i,1);
  EXPECT_EQ("1010110010", a.desc() );
  for (int i=0; i<10; i+=2) a.set(i,0);
  EXPECT_EQ("0000010000", a.desc() );
}

TEST(Bits,and)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_and_b = a & b;
  EXPECT_EQ("1000001000", a_and_b.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a &= b;
  EXPECT_EQ("1000001000", a.desc() );
}

TEST(Bits,or)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_or_b = a | b;
  EXPECT_EQ("1011101011", a_or_b.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a |= b;
  EXPECT_EQ("1011101011", a.desc() );
}

TEST(Bits,xor)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_xor_b = a ^ b;
  EXPECT_EQ("0011100011", a_xor_b.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a ^= b;
  EXPECT_EQ("0011100011", a.desc() );
}

TEST(Bits,not)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits not_a = ~a, not_b = ~b;
  EXPECT_EQ("0101010101", not_a.desc() );
  EXPECT_EQ("0110110110", not_b.desc() );
}

TEST(Bits,concat)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  EXPECT_EQ("1001001001", b.desc() );

  Bits a_b = a + b, b_a = b + a;
  EXPECT_EQ("10101010101001001001", a_b.desc() );
  EXPECT_EQ("10010010011010101010", b_a.desc() );
  // a, b が不変であること
  EXPECT_EQ("1010101010", a.desc() );
  EXPECT_EQ("1001001001", b.desc() );

  a += b;
  EXPECT_EQ("10101010101001001001", a.desc() );
}

TEST(Bits,count)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  // EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  // EXPECT_EQ("1001001001", b.desc() );

  EXPECT_EQ(10, a.size());
  EXPECT_EQ(10, b.size());

  Bits c1(1,1), c2(2,1), c3(3,1), c4(4,1), c5(5,1), c6(6,1), c7(7,1), c8(8,1), c9(9,1), d(2401,1);
  EXPECT_EQ(1, c1.size());
  EXPECT_EQ(2, c2.size());
  EXPECT_EQ(3, c3.size());
  EXPECT_EQ(4, c4.size());
  EXPECT_EQ(5, c5.size());
  EXPECT_EQ(6, c6.size());
  EXPECT_EQ(7, c7.size());
  EXPECT_EQ(8, c8.size());
  EXPECT_EQ(9, c9.size());
  EXPECT_EQ(2401, d.size());
}

TEST(Bits,popcount)
{
  Bits a(10), b(10);
  for (int i=0; i<10; i+=2) a.set(i);
  //EXPECT_EQ("1010101010", a.desc() );
  for (int i=0; i<10; i+=3) b.set(i);
  //EXPECT_EQ("1001001001", b.desc() );

  EXPECT_EQ(5, a.popcount());
  EXPECT_EQ(4, b.popcount());

  Bits c1(1,1), c2(2,1), c3(3,1), c4(4,1), c5(5,1), c6(6,1), c7(7,1), c8(8,1), c9(9,1), d(2401,1);
  EXPECT_EQ(1, c1.popcount());
  EXPECT_EQ(2, c2.popcount());
  EXPECT_EQ(3, c3.popcount());
  EXPECT_EQ(4, c4.popcount());
  EXPECT_EQ(5, c5.popcount());
  EXPECT_EQ(6, c6.popcount());
  EXPECT_EQ(7, c7.popcount());
  EXPECT_EQ(8, c8.popcount());
  EXPECT_EQ(9, c9.popcount());
  EXPECT_EQ(2401, d.popcount());
}

int main(int argc, char** argv)
{
  testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}