Groebner_HFE80/bitset.h

#ifndef BITSET_H
#define BITSET_H

#include "conf.h"
struct bitset_N {
	unsigned long long data[(N + 63) / 64];    //data[i]<5D><>ʾ<EFBFBD><CABE>64i~64i+63λ
	inline bool get(int n)     //<2F><>ȡ<EFBFBD><C8A1>nλ
	{
		int index = n >> 6;
		int bit = n & 63;
		return data[index] & (1ull << n);
	}
	inline void set(int n)     //<2F><><EFBFBD><EFBFBD>nλ<6E><CEBB>Ϊ1
	{
		int index = n >> 6;
		int bit = n & 63;
		data[index] |= (1ull << n);
	}
	inline void add(int n)      //<2F><><EFBFBD><EFBFBD>nλ<6E><CEBB>1<EFBFBD><31><EFBFBD><EFBFBD>ת<EFBFBD><D7AA>
	{
		int index = n >> 6;
		int bit = n & 63;
		data[index] ^= (1ull << n);
	}
	inline bitset_N& operator ^= (bitset_N b)
	{
		for (int i = 0; i < (N + 63) / 64; i++)
		{
			data[i] ^= b.data[i];
		}
		return *this;
	}
	inline bitset_N& operator |= (bitset_N b)
	{
		for (int i = 0; i < (N + 63) / 64; i++)
		{
			data[i] |= b.data[i];
		}
		return *this;
	}
	inline bitset_N operator ~ ()
	{
		bitset_N ret;
		for (int i = 0; i < (N + 63) / 64; i++)
		{
			ret.data[i] = ~data[i];
		}
		return ret;
	}
	inline bitset_N operator & (bitset_N b)
	{
		bitset_N ret;
		for (int i = 0; i < (N + 63) / 64; i++)
		{
			ret.data[i] = data[i] & b.data[i];
		}
		return ret;
	}
	inline bitset_N operator | (bitset_N b)
	{
		bitset_N ret;
		for (int i = 0; i < (N + 63) / 64; i++)
		{
			ret.data[i] = data[i] | b.data[i];
		}
		return ret;
	}
	inline void clear()
	{
		memset(data, 0, sizeof(data));
	}
	inline bool none()
	{
		unsigned long long ret = 0;
		for (int i = 0; i < (N + 63) / 64; i++)
			ret |= data[i];
		return !ret;
	}
};

struct bitset_M {
	unsigned long long data[(M - 1) / 64 + 1];    //data[i]<5D><>ʾ<EFBFBD><CABE>64i~64i+63λ
	int data_len;              //<2F><><EFBFBD><EFBFBD>data<74><61><EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>ݵij<DDB5><C4B3><EFBFBD>
	//int leader;
	//int had_set_leader;        //<2F>Ѿ<EFBFBD><D1BE><EFBFBD>ȡ<EFBFBD><C8A1><EFBFBD><EFBFBD><EFBFBD><EFBFBD>
	inline bool get(int n)     //<2F><>ȡ<EFBFBD><C8A1>nλ
	{
		int index = n >> 6;
		int bit = n & 63;
		return data[index] & (1ull << n);    //1ull<6C><6C>ʾ<EFBFBD>޷<EFBFBD><DEB7><EFBFBD>64λ<34><CEBB>1
	}
	inline void set(int n)     //<2F><><EFBFBD><EFBFBD>nλ<6E><CEBB>Ϊ1
	{
		int index = n >> 6;
		int bit = n & 63;
		data[index] |= (1ull << n);
	}
	inline void add(int n)      //<2F><><EFBFBD><EFBFBD>nΪ<6E><CEAA>1<EFBFBD><31><EFBFBD><EFBFBD>ת<EFBFBD><D7AA>
	{
		int index = n >> 6;
		int bit = n & 63;
		data[index] ^= (1ull << n);
	}
	inline int getleader(int max_leader = M - 1)
	{
		int max_int_index = max_leader / 64;
		int leader = 0;
		for (int i = max_int_index; i >= 0; i--)
		{
			if (data[i] != 0)
			{
				for (int j = 63; j >= 0; j--)
				{
					if (data[i] & (1ull << j))
					{
						leader = i * 64 + j;
						data_len = i + 1;
						return leader;
					}
				}
			}
		}
		leader = -1;
		data_len = 0;
		return leader;
	}
	inline void xor_part(bitset_M& b, int begin_block, int end_block)
	{
		int temp = (end_block - begin_block) % 8;
		for (int i = begin_block; i < begin_block+temp; i++)
		{
			data[i] ^= b.data[i];
		}
		for (int i = begin_block + temp; i < end_block; i+=8)
		{
			data[i] ^= b.data[i];
			data[i+1] ^= b.data[i+1];
			data[i+2] ^= b.data[i+2];
			data[i+3] ^= b.data[i+3]; 
			data[i+4] ^= b.data[i+4];
			data[i+5] ^= b.data[i+5];
			data[i+6] ^= b.data[i+6];
			data[i+7] ^= b.data[i+7];
		}
	}
	inline void xor_part(bitset_M& b, int block)
	{
		data[block] ^= b.data[block];
	}
	inline void clear()
	{
		memset(data, 0, sizeof(data));
		data_len = 0;
	}
};

inline bool operator > (bitset_M& a, bitset_M& b)
{
	if (a.data_len > b.data_len)
		return true;
	if (a.data_len < b.data_len)
		return false;
	for (int i = a.data_len - 1; i >= 0; i--)
	{
		if (a.data[i] > b.data[i])
			return true;
		if (a.data[i] < b.data[i])
			return false;
	}
	return false;
}

inline bool operator < (bitset_M& a, bitset_M& b)
{
	if (a.data_len < b.data_len)
		return true;
	if (a.data_len > b.data_len)
		return false;
	for (int i = a.data_len - 1; i >= 0; i--)
	{
		if (a.data[i] < b.data[i])
			return true;
		if (a.data[i] > b.data[i])
			return false;
	}
	return false;
}

#endif