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]表示第64i~64i+63位
	inline bool get(int n)     //获取第n位
	{
		int index = n >> 6;
		int bit = n & 63;
		return data[index] & (1ull << n);
	}
	inline void set(int n)     //将第n位置为1
	{
		int index = n >> 6;
		int bit = n & 63;
		data[index] |= (1ull << n);
	}
	inline void add(int n)      //将第n位加1（反转）
	{
		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]表示第64i~64i+63位
	int data_len;              //数组data存入数据的长度
	//int leader;
	//int had_set_leader;        //已经获取过首项
	inline bool get(int n)     //获取第n位
	{
		int index = n >> 6;
		int bit = n & 63;
		return data[index] & (1ull << n);    //1ull表示无符号64位的1
	}
	inline void set(int n)     //将第n位置为1
	{
		int index = n >> 6;
		int bit = n & 63;
		data[index] |= (1ull << n);
	}
	inline void add(int n)      //将第n为加1（反转）
	{
		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