#include <iostream>
#include <fstream>
#include <stdio.h>
#define N 1270
#define K 1200
#define G 70
//#define HAIMING
using namespace std;
int len[N];
int i_2_r(int a)             //求一個2^n次方的數的冪
{
 int count=0;
 if(a==1) 
 return 0;
 while(a>1)
 {
  a=a/2;
  count++;
 }
 return count;
}
void in_to_Group(int a[],int b,int n)  //添加到各組中
{
 int i;
 for(i=1;i<=n;i++)
   if(a[i]==-1)
  a[i]=b; 
}
int _2_r_gt_k_r(int k,int r)  //判斷 2^r >= k+r+1
{
 int i,s = 1;
 for(i = 1;i <= r;i++)
  s = 2*s;
 if(s >= k+r+1)
  return 1;
 else 
  return 0;
}
int is_i_2_r(int i)         //判斷 i 是否為 2^n 位
{
 if(i == 1) 
  return 1;
 if(i%2 != 0)
  return 0;
 while(i%2 == 0 && i != 1)
  i=i/2;
 if(i==1)
  return 1;
 return 0;
}
/*int int_to_invdec(int n)       //求一個整數的逆序的二進制碼
{
 int i=1,j,b[N];               //以計算校驗位號
 while(n)
 {
  b[i++]=n%2;
  n/=2;
 }
 for(j = 1;j<=(i-1);j++)
	 a[j]=b[j];
 for(j = 1;j<=(i-1);j++)//測試
	 cout<<a[j];
 cout<<endl;
 return i-1;                    //返回位數
}*/
int count1(int a[],int n)  //計算 1 的個數,為偶數是返回0
{
 int i,count = 0;
 for(i = 0;i<n;i++)
  if(a[i] == 1)
   count++;
 if(count%2 == 0)
  return 0;
 return 1;
}
int  *decodehaiming(int decode[],int k,int r)
{
	int group[G][K],i,g,j,err=0,encode[N];
	int count[G],infor[K];
	int a_l,h=1, u=1,a[N],p=1;
	for(i=0;i<(k+r);i++)
		encode[i]=decode[i];
	for(i=0;i<(k+r);i++)     //測試輸入
		cout<<encode[i];
	cout<<endl;
	//for(i=0;i<N;i++)   //測試
	//	a[i]=-1;
	for(i=0;i<=r;i++)
	{
		len[i]=0;
	    for(g=0;g<=k;g++)	
		   group[i][g]=-1;
	}
	for(i=0;i<r;i++)     //測試分組數組的初始化
	for(g=0;g<k;g++)
		cout<<group[r][g];
	//cout<<len[i];
	cout<<endl;

	 for(i=1;i<=k+r;i++)           //!!!*從添加檢測位后的第 1 位開始進行分組 ( 關鍵 )
	 {
		 h=1;
		if(is_i_2_r(i))
		{
			group[i_2_r(i)][0]=encode[i-1];
		    len[i_2_r(i)]++;
		}
		else
		{
		//	a_l=int_to_invdec(i);
			u=i;
			 while(u)
			 {
                 a[h]=u%2;
				 h++;
                     u/=2;
			 }
			 a_l=h-1;
			for(g=1;g<=r;g++)           //共分為 r 組
			{
                for(j=1;j<=a_l;j++)   
                if(a[j]==1)             //**查轉化后 a[] 中為 1 的下標位(如為1則分給第1組,為2則分給第二組等等)
                if(g==j)                //若分組號與下標位相同,
				{           
                    //in_to_Group(group[g-1],encode[i-1],len[g-1]);//**將該信息碼添加到第 g 小組中
					for(p=0;p<=len[g-1];p++)
					{
						if(group[g-1][p]==-1)
							group[g-1][p]=encode[i-1];
					}

                     len[g-1]++;               //*第 g 小組長度增 1 
                     break; 
				}
			}
		}
	}
    // for(i=0;i<len[2];i++)
	// cout<<group[2][i]<<"zhi"<<endl;
	// cout<<endl;
    for(i=0;i<r;i++)
			count[i]=count1(group[i],len[i]);
		i=1;
		for(g=0;g<r;g++)
		{
		    err=err+count[g]*(i);
			i=i*2;
		}
	//cout<<group[i][g];
//	cout<<endl;
//	for(i=0;i<r;i++)//測試
		cout<<"err="<<err<<endl;
    if(err==0)
	{
			g=0;
		for(i=0;i<k+r;i++)
		{
			if(!is_i_2_r(i+1) )
			infor[g++]=encode[i];
		}
	}
	else
	{
		if(encode[err-1]>0)
		encode[err-1]= encode[err-1]-1;
		else
		
			encode[err-1]= encode[err-1]+1;
		g=0;
		for(i=0;i<k+r;i++)
		{
			if(!is_i_2_r(i+1) )
			infor[g++]=encode[i];
		}
	}
	cout<<"信息碼為："<<endl;
	for(i=0;i<k;i++)
		cout<<infor[i];
	cout<<endl;
	return infor;
}
void main(int argc, char* argv[])
{
	int decode[]={0,0,1,0,1,0,0,1,1,1,0,0,1,1,1,1,1},*infor;
	decodehaiming(decode,12,5);
}