将棋のための128ビット整数クラス  [更新日: 2008年03月11日 ]

C++ のクラスを使い 128 ビットリニアな Shift-L, Shift-R, ADD, SUB と AND, OR, XOR, NOT などを実装してみた。 利用目的は将棋盤 (9x9) のビット演算用なので、 積/除算は実装するつもりがありません。

履歴

• 2008/03/09: 1.0.3 — getbit(), getofs() 追加, getlsb() 更新
• 2007/11/15: 1.0.2 — operator bool() メソッドを追加
• 2007/11/11: 1.0.1 — getlsb(), getmsb() メソッドを追加
• 2007/11/10: 1.0.0 — 新規作成

ヘッダ部

// vim: set ts=4 sw=4 sts=0 :
// Copyright (C) 2007,2008, Shu KONNO . All rights reserved.
// This program is free software licensed under the GPL 2 or above.
//
// 1.0.3 - 2008/03/09 added getbit(), getofs(), updated getlsb()
// 1.0.2 - 2007/11/15 added operator bool()
// 1.0.1 - 2007/11/11 added getlsb(), getmsb()
// 1.0.0 - 2007/11/10 created new
#ifndef _C128_H_
#define _C128_H_
typedef unsigned long long ULong;

class C128 {
protected:
	ULong lo;
	ULong hi;
public:
	C128() : lo(0), hi(0) {}
	C128(ULong m, ULong n=0) : lo(m), hi(n) {}
	~C128() {}
	void clear() { lo = 0; hi = 0; }
	ULong getl() const { return lo; }
	ULong geth() const { return hi; }
	int getbit();
	int getofs() const;
	bool getbit(unsigned int) const;
	void setbit(unsigned int);
	void unsetbit(unsigned int);
	C128 getlsb() const;
	C128 getmsb() const;
	operator bool() const { return lo || hi; }
	C128& operator<<=(unsigned int);
	C128 operator<<(int n) const { return C128(*this) <<= n; }
	C128& operator>>=(unsigned int);
	C128 operator>>(int n) const { return C128(*this) >>= n; }
	C128& operator+=(ULong);
	C128& operator+=(C128);
	C128 operator+(int i) const { return C128(*this) += i; }
	C128 operator+(ULong u) const { return C128(*this) += u; }
	C128 operator+(C128 c) const { return C128(*this) += c; }
	C128 operator+() const { return *this; }
	C128& operator-=(ULong);
	C128& operator-=(C128);
	C128 operator-(int i) const { return C128(*this) -= i; }
	C128 operator-(ULong u) const { return C128(*this) -= u; }
	C128 operator-(C128 c) const { return C128(*this) -= c; }
	C128 operator-() const { return C128() -= *this; }
	C128& operator&=(C128);
	C128 operator&(C128 c) const { return C128(*this) &= c; }
	C128& operator|=(C128);
	C128 operator|(C128 c) const { return C128(*this) |= c; }
	C128& operator^=(C128);
	C128 operator^(C128 c) const { return C128(*this) ^= c; }
	C128 operator~() const { return C128(~lo, ~hi); };
private:
	int getofs(ULong) const;
};
#endif // _C128_H_

処理コード

// vim: set ts=4 sw=4 sts=0 :
// Copyright (C) 2007,2008, Shu KONNO . All rights reserved.
// This program is free software licensed under the GPL 2 or above.
//
#include "C128.h"

int C128::getbit()
{
	if (lo) {
		ULong x = lo & -lo;
		lo &= ~x;
		return getofs(x);
	}
	ULong x = hi & -hi;
	hi &= ~x;
	return 64 + getofs(x);
}

int C128::getofs() const
{
	return lo? getofs(lo): 64 + getofs(hi);
}

// only one bit condition
int C128::getofs(ULong x) const
{
	int n = 0;
	if (x & 0xffffffff00000000) n += 32;
	if (x & 0xffff0000ffff0000) n += 16;
	if (x & 0xff00ff00ff00ff00) n += 8;
	if (x & 0xf0f0f0f0f0f0f0f0) n += 4;
	if (x & 0xcccccccccccccccc) n += 2;
	if (x & 0xaaaaaaaaaaaaaaaa) n += 1;
	return n;
}

bool C128::getbit(unsigned int n) const
{
	if (n < 64)
		return lo & ((ULong)0x01 << n);
	else
		return hi & ((ULong)0x01 << (n - 64));
	return false;
}

void C128::setbit(unsigned int n)
{
	if (n < 64)
		lo |= ((ULong)0x01 << n);
	else
		hi |= ((ULong)0x01 << (n - 64));
}

void C128::unsetbit(unsigned int n)
{
	if (n < 64)
		lo &= ~((ULong)0x01 << n);
	else
		hi &= ~((ULong)0x01 << (n - 64));
}

// get least significant bit
#if 0
// 0.452s/100,000,000
C128 C128::getlsb() const
{
	ULong x = -hi;
	if (lo)
		--x;
	return C128(lo & (-lo), hi & x);
}
#else
// 0.400s/100,000,000
C128 C128::getlsb() const
{
	return lo? C128(lo & (-lo)): C128(0, hi & (-hi));
}
#endif

// get most significant bit
// 1.000s/100,000,000
C128 C128::getmsb() const
{
	ULong x = (hi)? hi: lo;
	x |= (x >> 1);
	x |= (x >> 2);
	x |= (x >> 4);
	x |= (x >> 8);
	x |= (x >> 16);
	x |= (x >> 32);
	x &= ~(x >> 1);
	return (hi)? C128(0, x): C128(x);
}

// 0.584s/100,000,000
C128& C128::operator<<=(unsigned int n)
{
	n &= 0x07f;
	if (n >= 64) {
		hi = lo << (n - 64);
		lo = 0;
	}
	else if (n) {
		hi <<= n;
		hi |= lo >> (64 - n);
		lo <<= n;
	}
	return *this;
}

C128& C128::operator>>=(unsigned int n)
{
	n &= 0x07f;
	if (n >= 64) {
		lo = hi >> (n - 64);
		hi = 0;
	}
	else if (n) {
		lo >>= n;
		lo |= hi << (64 - n);
		hi >>= n;
	}
	return *this;
}

C128& C128::operator+=(ULong u)
{
	ULong t = lo;
	if ((lo += u) < t)
		++hi;
	return *this;
}

C128& C128::operator+=(C128 c)
{
	ULong t = lo;
	if ((lo += c.lo) < t)
		++hi;
	hi += c.hi;
	return *this;
}

C128& C128::operator-=(ULong u)
{
	ULong t = lo;
	if ((lo -= u) > t)
		--hi;
	return *this;
}

C128& C128::operator-=(C128 c)
{
	ULong t = lo;
	if ((lo -= c.lo) > t)
		--hi;
	hi -= c.hi;
	return *this;
}

C128& C128::operator&=(C128 c)
{
	lo &= c.lo;
	hi &= c.hi;
	return *this;
}

C128& C128::operator|=(C128 c)
{
	lo |= c.lo;
	hi |= c.hi;
	return *this;
}

C128& C128::operator^=(C128 c)
{
	lo ^= c.lo;
	hi ^= c.hi;
	return *this;
}