読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

マイナス2進数を求めるプログラムを書いてみた。

まず、2進数についてはこちらをどうぞ。
2進数、16進数と10進数 - CyberLibrarian


マイナス2進数というのは、基本的には同じです。
例えば、マイナス2進数の 1101 を10進数に直すと、
1*(-2)^3 + 1*(-2)^2 + 0*(-2)^1 + 1*(-2)^0
= -8 +4 +1 = -3


あれ、マイナスになってしまった。
んじゃ、次の例です。
マイナス2進数 11010 のときは、
1*(-2)^4 + 1*(-2)^3 + 0*(-2)^2 + 1*(-2)^1 + 0*(-2)^0
= 16 -8 -2 = 6


はい、11010が6です。
当然、11011は7になりますね。


0から30までのマイナス2進数を列挙すると、


0 : 0
1 : 1
2 : 110
3 : 111
4 : 100
5 : 101
6 : 11010
7 : 11011
8 : 11000
9 : 11001
10 : 11110
11 : 11111
12 : 11100
13 : 11101
14 : 10010
15 : 10011
16 : 10000
17 : 10001
18 : 10110
19 : 10111
20 : 10100
21 : 10101
22 : 1101010
23 : 1101011
24 : 1101000
25 : 1101001
26 : 1101110
27 : 1101111
28 : 1101100
29 : 1101101
30 : 1100010

このような数字になります。
マイナス2進数から10進数にするのは簡単です。
10進数からマイナス2進数にするのが少々厄介です。
通常の2進数のような計算方法では10進からマイナス2進数を求めることは出来ない?
出来るなら誰か教えてくだしあ。

/*************************************
 正の10進数からマイナス2進数を求めるプログラム
 ************************************/

#include <stdio.h>

long long POW(int a, int b)
{
	int i;
	long long ret = 1;
	for( i=0; i<b; i++)ret *= a;
	return ret;
}

char* decMinus2bin(char* str, int N)
{
	int u,k;
	long long i,j,sum;
	static const long long oddsum[]={
		2LL, 10LL, 42LL,
		170LL, 682LL, 2730LL,
		10922LL, 43690LL, 174762LL,
		699050LL, 2796202LL, 11184810LL,
		44739242LL, 178956970LL, 715827882LL,
		2863311530LL
	};
	static const long long evensum[]={
		1LL, 5LL, 21LL,
		85LL, 341LL, 1365LL,
		5461LL, 21845LL, 87381LL,
		349525LL, 1398101LL, 5592405LL,
		22369621LL, 89478485LL, 357913941LL,
		1431655765LL
	};
	
	if( N<0 )return NULL;
	if( N==0 ){
		str[0] = '0', str[1] = 0;
		return str;
	}
	
	for(u=0; evensum[u] < N; u++);
	j = (1LL<<(2*u));

	sum = j;
	
	do{
		if( sum<N ){
			for(u=0; sum+evensum[u] < N ; u++);
			j = j + (1LL<<(2*u));
		}else if( sum>N ){
			for(u=0; sum-oddsum[u] > N; u++);
			j = j + (1LL<<(2*u+1));
		}
		sum = 0;
		for(i=1,k=0; i<=j; i<<=1,k++){
			if( j&i )
				sum += POW(-2,k);
		}
	}while( sum!=N );
	
	str[k] = 0;
	for(i=1; i<=j; i<<=1){
		str[--k] = j&i ? '1' : '0';
	}
	
	return str;
}

int main()
{
	char str[34];
	int i;
	
	/*** Sample ***/
	for(i=0; i<=30; i++){
		printf("%d : %s\n",i,decMinus2bin(str,i));
	}
	printf("%d : %s\n",-1405737207,decMinus2bin(str,-1405737207));
	printf("%d : %s\n",2147483647,decMinus2bin(str,2147483647));
	/**************/
	
	return 0;
}


追記:
main関数内の char str[33] ---> char str[34] に修正。
某社に提出した後に気付く、あとの祭り\(^o^)/
なんでセグメンが起きてくれなかったんだよorz、手元だと[33]でも普通に動いちゃうよ…。